text:
Gröbner basis

In mathematics, and more specifically in computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating set of an ideal in a polynomial ring $K[x_{1}, ..., x_{n}]$ over a field $K$. A Gröbner basis allows many important properties of the ideal and the associated algebraic variety to be deduced easily, such as the dimension and the number of zeros when it is finite. Gröbner basis computation is one of the main practical tools for solving systems of polynomial equations and computing the images of algebraic varieties under projections or rational maps.

Gröbner basis computation can be seen as a multivariate, non-linear generalization of both Euclid's algorithm for computing polynomial greatest common divisors, and Gaussian elimination for linear systems.

Gröbner bases were introduced by Bruno Buchberger in his 1965 Ph.D. thesis, which also included an algorithm to compute them (Buchberger's algorithm). He named them after his advisor Wolfgang Gröbner. In 2007, Buchberger received the Association for Computing Machinery's Paris Kanellakis Theory and Practice Award for this work. However, the Russian mathematician Nikolai Günther had introduced a similar notion in 1913, published in various Russian mathematical journals. These papers were largely ignored by the mathematical community until their rediscovery in 1987 by Bodo Renschuch et al. An analogous concept for multivariate power series was developed independently by Heisuke Hironaka in 1964, who named them standard bases. This term has been used by some authors to also denote Gröbner bases.

The theory of Gröbner bases has been extended by many authors in various directions. It has been generalized to other structures such as polynomials over principal ideal rings or polynomial rings, and also some classes of non-commutative rings and algebras, like Ore algebras.

Polynomial ring
Gröbner bases are primarily defined for ideals in a polynomial ring $$R=K[x_1,\ldots,x_n]$$ over a field $K$. Although the theory works for any field, most Gröbner basis computations are done either when $K$ is the field of rationals or the integers modulo a prime number.

In the context of Gröbner bases, a nonzero polynomial in $$R=K[x_1,\ldots,x_n]$$ is commonly represented as a sum $$ c_1M_1 +\cdots + c_mM_m,$$ where the $$c_i$$ are nonzero elements of $K$, called coefficients, and the $$M_i$$ are monomials (called power products by Buchberger and some of his followers) of the form $$x_1^{a_1}\cdots x_n^{a_n}, $$ where the $$a_i$$ are nonnegative integers. The vector $$A=[a_1, \ldots ,a_n]$$ is called the exponent vector of the monomial. When the list $$X=[x_1, \ldots, x_n]$$ of the variables is fixed, the notation of monomials is often abbreviated as $$x_1^{a_1}\cdots x_n^{a_n}=X^A.$$

Monomials are uniquely defined by their exponent vectors, and, when a monomial ordering (see below) is fixed, a polynomial is uniquely represented by the ordered list of the ordered pairs formed by an exponent vector and the corresponding coefficient. This representation of polynomials is especially efficient for Gröbner basis computation in computers, although it is less convenient for other computations such as polynomial factorization and polynomial greatest common divisor.

If $$ F=\{f_1,\ldots, f_k\}$$ is a finite set of polynomials in the polynomial ring $R$, the ideal generated by $F$ is the set of linear combinations of elements of $F$ with coefficients in $R$; that is the set of polynomials that can be written $\sum_{i=1}^k g_i f_i$ with $$g_1,\ldots, g_k\in R.$$

Monomial ordering
All operations related to Gröbner bases require the choice of a total order on the monomials, with the following properties of compatibility with multiplication. For all monomials $M$, $N$, $P$, A total order satisfying these condition is sometimes called an admissible ordering.
 * 1) $$M \leq N \Longleftrightarrow MP \leq NP $$
 * 2) $$M \leq MP $$.

These conditions imply that the order is a well-order, that is, every strictly decreasing sequence of monomials is finite.

Although Gröbner basis theory does not depend on a particular choice of an admissible monomial ordering, three monomial orderings are specially important for the applications:
 * Lexicographical ordering, commonly called lex or plex (for pure lexical ordering).
 * Total degree reverse lexicographical ordering, commonly called degrevlex.
 * Elimination ordering, lexdeg.

Gröbner basis theory was initially introduced for the lexicographical ordering. It was soon realised that the Gröbner basis for degrevlex is almost always much easier to compute, and that it is almost always easier to compute a lex Gröbner basis by first computing the degrevlex basis and then using a "change of ordering algorithm". When elimination is needed, degrevlex is not convenient; both lex and lexdeg may be used but, again, many computations are relatively easy with lexdeg and almost impossible with lex.

Leading term, coefficient and monomial
Once a monomial ordering is fixed, the terms of a polynomial (product of a monomial with its nonzero coefficient) are naturally ordered by decreasing monomials (for this order). This makes the representation of a polynomial as a sorted list of pairs coefficient–exponent vector a canonical representation of the polynomials (that is, two polynomials are equal if and only they have the same representation).

The first (greatest) term of a polynomial $p$ for this ordering and the corresponding monomial and coefficient are respectively called the leading term, leading monomial and leading coefficient and denoted, in this article, $lt(p), lm(p)$ and $lc(p)$.

Most polynomial operations related to Gröbner bases involve the leading terms. So, the representation of polynomials as sorted lists make these operations particularly efficient (reading the first element of a list takes a constant time, independently of the length of the list).

Polynomial operations
The other polynomial operations involved by Gröbner basis computations are also compatible with the monomial ordering; that is, they can be performed without reordering the result:
 * The addition of two polynomials consists in a merge of the two corresponding lists of terms, with a special treatment in the case of a conflict (that is, when the same monomial appears in the two polynomials).
 * The multiplication of a polynomial by a scalar consists of multiplying each coefficient by this scalar, without any other change in the representation.
 * The multiplication of a polynomial by a monomial $m$ consists of multiplying each monomial of the polynomial by $m$. This does not change the term ordering by definition of a monomial ordering.

Divisibility of monomials
Let $$M=x_1^{a_1}\cdots x_n^{a_n}$$ and $$N=x_1^{b_1}\cdots x_n^{b_n}$$ be two monomials, with exponent vectors $$A=[a_1,\ldots, a_n]$$ and $$B=[b_1,\ldots, b_n].$$

One says that $M$ divides $N$, or that $N$ is a multiple of $M$, if $$a_i\le b_i$$ for every $i$; that is, if $A$ is componentwise not greater than $B$. In this case, the quotient \frac NM is defined as In other words, the exponent vector of \frac NM is the componentwise subtraction of the exponent vectors of $N$ and $M$.

The greatest common divisor $gcd(M, N)$ of $M$ and $N$ is the monomial $x_1^{\min(a_1,b_1)}\cdots x_n^{\min(a_n,b_n)}$ whose exponent vector is the componentwise minimum of $A$ and $B$. The least common multiple $lcm(M, N)$ is defined similarly with $max$ instead of $min$.

One has
 * $$\operatorname{lcm}(M,N)=\frac {MN}{\gcd(M,N)}.$$

Reduction
The reduction of a polynomial by other polynomials with respect to a monomial ordering is central to Gröbner basis theory. It is a generalization of both row reduction occurring in Gaussian elimination and division steps of the Euclidean division of univariate polynomials. When completed as much as possible, it is sometimes called multivariate division although its result is not uniquely defined.

Lead-reduction is a special case of reduction that is easier to compute. It is fundamental for Gröbner basis computation, since general reduction is needed only at the end of a Gröbner basis computation, for getting a reduced Gröbner basis from a non-reduced one.

Let an admissible monomial ordering be fixed, to which refers every monomial comparison that will occur in this section.

A polynomial $f$ is lead-reducible by another polynomial $g$ if the leading monomial $lm(f)$ is a multiple of $lm(g)$. The polynomial $f$ is reducible by $g$ if some monomial of $f$ is a multiple $lm(g)$. (So, if $f$ is lead-reducible by $g$, it is also reducible, but $f$ may be reducible without being lead-reducible.)

Suppose that $f$ is reducible by $g$, and let $cm$ be a term of $f$ such that the monomial $m$ is a multiple of $lm(g)$. A one-step reduction of $f$ by $g$ consists of replacing $f$ by
 * $$\operatorname{red}_1(f,g)=f-\frac{c}{\operatorname{lc}(g)}\,\frac m{\operatorname{lm}(g)}\, g.$$

This operation removes the monomial $m$ from $f$ without changing the terms with a monomial greater than $m$ (for the monomial ordering). In particular, a one step lead-reduction of $f$ produces a polynomial all of whose monomials are smaller than $lm(f)$.

Given a finite set $G$ of polynomials, one says that $f$ is reducible or lead-reducible by $G$ if it is reducible or lead-reducible, respectively, by at least one element $g$ of $G$. In this case, a one-step reduction (resp. one-step lead-reduction) of $f$ by $G$ is any one-step reduction (resp. one-step lead-reduction) of $f$ by an element of $G$.

The (complete) reduction (resp. lead-reduction) of $f$ by $G$ consists of iterating one-step reductions (respect. one-step lead reductions) until getting a polynomial that is irreducible (resp. lead-irreducible) by $G$. It is sometimes called a normal form of $f$ by $G$. In general this form is not uniquely defined because there are, in general, several elements of $G$ that can be used for reducing $f$; this non-uniqueness is the starting point of Gröbner basis theory.

The definition of the reduction shows immediately that, if $h$ is a normal form of $f$ by $G$, one has
 * $$f=h+\sum_{g\in G} q_g\,g,$$

where $h$ is irreducible by $G$ and the $$q_g$$ are polynomials such that $$\operatorname{lm}(q_g\,g) \leq \operatorname{lm}(f).$$ In the case of univariate polynomials, if $G$ consists of a single element $g$, then $h$ is the remainder of the Euclidean division of $f$ by $g$, and $q_{g}$ is the quotient. Moreover, the division algorithm is exactly the process of lead-reduction. For this reason, some authors use the term multivariate division instead of reduction.

Non uniqueness of reduction
In the example that follows, there are exactly two complete lead-reductions that produce two very different results. The fact that the results are irreducible (not only lead-irreducible) is specific to the example, although this is rather common with such small examples.

In this two variable example, the monomial ordering that is used is the lexicographic order with $$x>y,$$ and we consider the reduction of $$f=2x^3-x^2y+y^3+3y$$, by $$G=\{g_1,g_2\},$$ with $$\begin{align}g_1&=x^2+y^2-1,\\g_2&=xy-2.\end{align}$$

For the first reduction step, either the first or the second term of $f$ may be reduced. However, the reduction of a term amounts to removing this term at the cost of adding new lower terms; if it is not the first reducible term that is reduced, it may occur that a further reduction adds a similar term, which must be reduced again. It is therefore always better to reduce first the largest (for the monomial order) reducible term; that is, in particular, to lead-reduce first until getting a lead-irreducible polynomial.

The leading term $$2x^3$$ of $f$ is reducible by $$g_1$$ and not by $$g_2.$$ So the first reduction step consists of multiplying $$g_1$$ by $–2x$ and adding the result to $f$:
 * $$f\;\xrightarrow{-2xg_1}\; f_1=f-2xg_1=-x^2y-2xy^2+2x+y^3+3y.$$

The leading term $$-x^2y$$ of $$f_1$$ is a multiple of the leading monomials of both $$g_1$$ and $$g_2,$$ So, one has two choices for the second reduction step. If one chooses $$g_2,$$ one gets a polynomial that can be reduced again by $$g_2\colon$$
 * $$f \;\xrightarrow{-2xg_1}\; f_1 \;\xrightarrow{xg_2}\; -2xy^2+y^3+3y \;\xrightarrow{2yg_2}\; f_2=y^3-y.$$

No further reduction is possible, so $$f_2$$ is a complete reduction of $f$.

One gets a different result with the other choice for the second step:
 * $$f\;\xrightarrow{-2xg_1}\; f_1 \;\xrightarrow{yg_1}\; -2xy^2+2x+2y^3+2y \;\xrightarrow{2yg_2}\; f_3=2x+2y^3-2y.$$

Again, the result $$f_3$$ is irreducible, although only lead reductions were done.

In summary, the complete reduction of $f$ can result in either $$f_2=y^3-y$$ or $$f_3=2x+2y^3-2y.$$

It is for dealing with the problems set by this non-uniqueness that Buchberger introduced Gröbner bases and $S$-polynomials. Intuitively, $0 = f − f$ may be reduced to $$f_2-f_3.$$ This implies that $$f_2-f_3$$ belongs to the ideal generated by $G$. So, this ideal is not changed by adding $$f_3-f_2$$ to $G$, and this allows more reductions. In particular, $$f_3$$ can be reduced to $$f_2$$ by $$f_3-f_2$$ and this restores the uniqueness of the reduced form.

Here Buchberger's algorithm for Gröbner bases would begin by adding to $G$ the polynomial
 * $$g_3=yg_1-xg_2=2x+y^3-y.$$

This polynomial, called $S$-polynomial by Buchberger, is the difference of the one-step reductions of the least common multiple $$x^2y$$ of the leading monomials of $$g_1$$ and $$g_2$$, by $$g_2$$ and $$g_1$$ respectively:
 * $$g_3 = \left( x^2 y - \frac{x^2y}{lt(g_2)} g_2 \right) - \left( x^2 y -  \frac{x^2y}{lt(g_1)} g_1 \right) = \frac{x^2y}{lt(g_1)} g_1 - \frac{x^2y}{lt(g_2)} g_2 $$.

In this example, one has $$g_3=f_3-f_2.$$ This does not complete Buchberger's algorithm, as $xy$ gives different results, when reduced by $$g_2$$ or $$g_3.$$

S-polynomial
Given monomial ordering, the S-polynomial or critical pair of two polynomials $f$ and $g$ is the polynomial
 * $$S(f,g) = \operatorname{red}_1 (\mathrm{lcm},g) - \operatorname{red}_1 (\mathrm{lcm},f)$$;

where $lcm$ denotes the least common multiple of the leading monomials of $f$ and $g$. Using the definition of $$\operatorname{red}_1$$, this translates to:
 * $$\begin{align}S(f,g)

&= \left( \mathrm{lcm} - \frac{1}{\operatorname{lc}(g)}\,\frac{\mathrm{lcm}}{\operatorname{lm}(g)}\,g \right) - \left( \mathrm{lcm} - \frac{1}{\operatorname{lc}(f)}\,\frac{\mathrm{lcm}}{\operatorname{lm}(f)}\,f \right)\\ &= \frac{1}{\operatorname{lc}(f)}\,\frac{\mathrm{lcm}}{\operatorname{lm}(f)}\,f - \frac{1}{\operatorname{lc}(g)}\,\frac{\mathrm{lcm}}{\operatorname{lm}(g)}\,g\\ \end{align}.$$ Using the property that relates the $lcm$ and the $gcd$, the S-polynomial can also be written as:
 * $$S(f,g) = \frac 1{\operatorname{lc}(f)}\,\frac{\operatorname{lm}(g)}{\mathrm{gcd}}\,f - \frac 1{\operatorname{lc}(g)}\,\frac{\operatorname{lm}(f)}{\mathrm{gcd}}\,g ;

$$ where $gcd$ denotes the greatest common divisor of the leading monomials of $f$ and $g$.

As the monomials that are reducible by both $f$ and $g$ are exactly the multiples of $lcm$, one can deal with all cases of non-uniqueness of the reduction by considering only the S-polynomials. This is a fundamental fact for Gröbner basis theory and all algorithms for computing them.

For avoiding fractions when dealing with polynomials with integer coefficients, the S polynomial is often defined as
 * $$S(f,g) = \operatorname{lc}(g)\,\frac{\operatorname{lm}(g)}{\mathrm{gcd}}\,f - \operatorname{lc}(f),\frac{\operatorname{lm}(f)}{\mathrm{gcd}}\,g;

$$ This does not changes anything to the theory since the two polynomials are associates.

Definition
Let $$R=F[x_1,\ldots,x_n]$$ be a polynomial ring over a field $F$. In this section, we suppose that an admissible monomial ordering has been fixed.

Let $G$ be a finite set of polynomials in $R$ that generates an ideal $I$. The set $G$ is a Gröbner basis (with respect to the monomial ordering), or, more precisely, a Gröbner basis of $I$ if or, equivalently, 1. the leading monomial of every polynomial in $I$ is a multiple of the leading monomial of some polynomial in $G$.
 * 1) the ideal generated by the leading monomials of the polynomials in $I$ equals the ideal generated by the leading monomials of $G$,

There are many characterizing properties, which can each be taken as an equivalent definition of Gröbner bases. For conciseness, in the following list, the notation "one-word/another word" means that one can take either "one-word" or "another word" for having two different characterizations of Gröbner bases. All the following assertions are characterizations of Gröbner bases: 1. a polynomial $f$ is in $I$, if and only if some/every complete lead-reduction/reduction of $f$ by $G$ produces the zero polynomial;

2. for every $S$-polynomial $s$ of elements of $G$, some/every complete lead-reduction/reduction of $s$ by $G$ produces zero;

3. all complete reductions of an element of $R$ produce the same result;

4. the monomials that are irreducible by $G$ form a basis of the $F$-vector space $R/I.$

Counting the above definition, this provides 12 characterizations of Gröbner bases. The fact that so many characterizations are possible makes Gröbner bases very useful. For example, condition 3 provides an algorithm for testing ideal membership; condition 4 provides an algorithm for testing whether a set of polynomials is a Gröbner basis and forms the basis of Buchberger's algorithm for computing Gröbner bases; conditions 5 and 6 allow computing in $$R/I$$ in a way that is very similar to modular arithmetic.

Existence
For every admissible monomial ordering and every finite set $G$ of polynomials, there is a Gröbner basis that contains $G$ and generates the same ideal. Moreover, such a Gröbner basis may be computed with Buchberger's algorithm.

This algorithm uses condition 4, and proceeds roughly as follows: for any two elements of $G$, compute the complete reduction by $G$ of their S-polynomial, and add the result to $G$ if it is not zero; repeat this operation with the new elements of $G$ included until, eventually, all reductions produce zero.

The algorithm terminates always because of Dickson's lemma or because polynomial rings are Noetherian (Hilbert's basis theorem). Condition 4 insures that the result is a Gröbner basis, and the definitions of S-polynomials and reduction insure that the generated ideal is not changed.

The above method is an algorithm for computing Gröbner bases; however, it is very inefficient. Many improvements of the original Buchberger's algorithm, and several other algorithms have been proposed and implemented, which dramatically improve the efficiency. See, below.

Reduced Gröbner bases
A Gröbner basis is minimal if all leading monomials of its elements are irreducible by the other elements of the basis. Given a Gröbner basis of an ideal $I$, one gets a minimal Gröbner basis of $I$ by removing the polynomials whose leading monomials are multiple of the leading monomial of another element of the Gröbner basis. However, if two polynomials of the basis have the same leading monomial, only one must be removed. So, every Gröbner basis contains a minimal Gröbner basis as a subset.

All minimal Gröbner bases of a given ideal (for a fixed monomial ordering) have the same number of elements, and the same leading monomials, and the non-minimal Gröbner bases have more elements than the minimal ones.

A Gröbner basis is reduced if every polynomial in it is irreducible by the other elements of the basis, and has $1$ as leading coefficient. So, every reduced Gröbner basis is minimal, but a minimal Gröbner basis need not be reduced.

Given a Gröbner basis of an ideal $I$, one gets a reduced Gröbner basis of $I$ by first removing the polynomials that are lead-reducible by other elements of the basis (for getting a minimal basis); then replacing each element of the basis by the result of the complete reduction by the other elements of the basis; and, finally, by dividing each element of the basis by its leading coefficient.

All reduced Gröbner bases of an ideal (for a fixed monomial ordering) are equal. It follows that two ideals are equal if and only if they have the same reduced Gröbner basis.

Sometimes, reduced Gröbner bases are defined without the condition on the leading coefficients. In this case, the uniqueness of reduced Gröbner bases is true only up to the multiplication of polynomials by a nonzero constant.

When working with polynomials over the field $$\Q$$ of the rational numbers, it is useful to work only with polynomials with integer coefficients. In this case, the condition on the leading coefficients in the definition of a reduced basis may be replaced by the condition that all elements of the basis are primitive polynomials with integer coefficients, with positive leading coefficients. This restores the uniqueness of reduced bases.

Special cases
For every monomial ordering, the empty set of polynomials is the unique Gröbner basis of the zero ideal.

For every monomial ordering, a set of polynomials that contains a nonzero constant is a Gröbner basis of the unit ideal (the whole polynomial ring). Conversely, every Gröbner basis of the unit ideal contains a nonzero constant. The reduced Gröbner basis of the unit is formed by the single polynomial $1$.

In the case of polynomials in a single variable, there is a unique admissible monomial ordering, the ordering by the degree. The minimal Gröbner bases are the singletons consisting of a single polynomial. The reduced Gröbner bases are the monic polynomials.

Example and counterexample

Let $$R = \Q[x,y]$$ be the ring of bivariate polynomials with rational coefficients and consider the ideal $$I = \langle f,g\rangle$$ generated by the polynomials

 * $$f=x^2-y$$,
 * $$g=x^3-x$$.

By reducing $g$ by $f$, one obtains a new polynomial $k$ such that $$I=\langle f,k\rangle:$$
 * $$k=g - xf= xy -x.$$

None of $f$ and $k$ is reducible by the other, but $xk$ is reducible by $f$, which gives another polynomial in $I$:
 * $$h=xk-(y-1) f= y^2 -y.$$

Under lexicographic ordering with $$x>y$$ we have

As $lt(f) = x^{2}$ and $h$ belong to $I$, and none of them is reducible by the others, none of $$\{f,k\},$$ $$\{f,h\},$$ and $$\{h,k\}$$ is a Gröbner basis of $I$.

On the other hand, $lt(k) = xy$ is a Gröbner basis of $I$, since the S-polynomials
 * $$\begin{align}

yf-xk&=y(x^2-y)-x(xy-x)=f-h\\ yk-xh&=y(xy-x)-x(y^2-y)=0\\ y^2f-x^2h&= y(yf-xk)+x(yk-xh) \end{align}$$ can be reduced to zero by $lt(h) = y^{2}$ and $h$.

The method that has been used here for finding $h$ and $k$, and proving that $f, k$ is a Gröbner basis is a direct application of Buchberger's algorithm. So, it can be applied mechanically to any similar example, although, in general, there are many polynomials and S-polynomials to consider, and the computation is generally too large for being done without a computer.

Properties and applications of Gröbner bases
Unless explicitly stated, all the results that follow are true for any monomial ordering (see that article for the definitions of the different orders that are mentioned below).

It is a common misconception that the lexicographical order is needed for some of these results. On the contrary, the lexicographical order is, almost always, the most difficult to compute, and using it makes impractical many computations that are relatively easy with graded reverse lexicographic order (grevlex), or, when elimination is needed, the elimination order (lexdeg) which restricts to grevlex on each block of variables.

Equality of ideals
Reduced Gröbner bases are unique for any given ideal and any monomial ordering. Thus two ideals are equal if and only if they have the same (reduced) Gröbner basis (usually a Gröbner basis software always produces reduced Gröbner bases).

Membership and inclusion of ideals
The reduction of a polynomial f by the Gröbner basis G of an ideal $I$ yields 0 if and only if f is in $I$. This allows to test the membership of an element in an ideal. Another method consists in verifying that the Gröbner basis of G∪{f} is equal to G.

To test if the ideal $I$ generated by f1, ..., fk is contained in the ideal $J$, it suffices to test that every $\{f, k, h\}$ is in $J$. One may also test the equality of the reduced Gröbner bases of $J$ and J ∪ {f1, ...,fk}.

Solutions of a system of algebraic equations
Any set of polynomials may be viewed as a system of polynomial equations by equating the polynomials to zero. The set of the solutions of such a system depends only on the generated ideal, and, therefore does not change when the given generating set is replaced by the Gröbner basis, for any ordering, of the generated ideal. Such a solution, with coordinates in an algebraically closed field containing the coefficients of the polynomials, is called a zero of the ideal. In the usual case of rational coefficients, this algebraically closed field is chosen as the complex field.

An ideal does not have any zero (the system of equations is inconsistent) if and only if 1 belongs to the ideal (this is Hilbert's Nullstellensatz), or, equivalently, if its Gröbner basis (for any monomial ordering) contains 1, or, also, if the corresponding reduced Gröbner basis is [1].

Given the Gröbner basis G of an ideal I, it has only a finite number of zeros, if and only if, for each variable x, G contains a polynomial with a leading monomial that is a power of x (without any other variable appearing in the leading term). If this is the case, then the number of zeros, counted with multiplicity, is equal to the number of monomials that are not multiples of any leading monomial of G. This number is called the degree of the ideal.

When the number of zeros is finite, the Gröbner basis for a lexicographical monomial ordering provides, theoretically, a solution: the first coordinate of a solution is a root of the greatest common divisor of polynomials of the basis that depend only on the first variable. After substituting this root in the basis, the second coordinate of this solution is a root of the greatest common divisor of the resulting polynomials that depend only on the second variable, and so on. This solving process is only theoretical, because it implies GCD computation and root-finding of polynomials with approximate coefficients, which are not practicable because of numeric instability. Therefore, other methods have been developed to solve polynomial systems through Gröbner bases (see System of polynomial equations for more details).

Dimension, degree and Hilbert series
The dimension of an ideal I in a polynomial ring R is the Krull dimension of the ring R/I and is equal to the dimension of the algebraic set of the zeros of I. It is also equal to number of hyperplanes in general position which are needed to have an intersection with the algebraic set, which is a finite number of points. The degree of the ideal and of its associated algebraic set is the number of points of this finite intersection, counted with multiplicity. In particular, the degree of a hypersurface is equal to the degree of its definition polynomial.

Both degree and dimension depend only on the set of the leading monomials of the Gröbner basis of the ideal for any monomial ordering.

The dimension is the maximal size of a subset S of the variables such that there is no leading monomial depending only on the variables in S. Thus, if the ideal has dimension 0, then for each variable x there is a leading monomial in the Gröbner basis that is a power of x.

Both dimension and degree may be deduced from the Hilbert series of the ideal, which is the series $\sum_{i=0}^\infty d_i t^i$, where $$d_i$$ is the number of monomials of degree i that are not multiple of any leading monomial in the Gröbner basis. The Hilbert series may be summed into a rational fraction
 * $$\sum_{i=0}^\infty d_it^i=\frac{P(t)}{(1-t)^d},$$

where d is the dimension of the ideal and $$P(t)$$ is a polynomial such that $$P(1)$$ is the degree of the ideal.

Although the dimension and the degree do not depend on the choice of the monomial ordering, the Hilbert series and the polynomial $$P(t)$$ change when one changes the monomial ordering.

Most computer algebra systems that provide functions to compute Gröbner bases provide also functions for computing the Hilbert series, and thus also the dimension and the degree.

Elimination
The computation of Gröbner bases for an elimination monomial ordering allows computational elimination theory. This is based on the following theorem.

Consider a polynomial ring $$K[x_1,\ldots,x_n,y_1,\ldots,y_m]=K[X,Y],$$ in which the variables are split into two subsets X and Y. Let us also choose an elimination monomial ordering "eliminating" X, that is a monomial ordering for which two monomials are compared by comparing first the X-parts, and, in case of equality only, considering the Y-parts. This implies that a monomial containing an X-variable is greater than every monomial independent of X. If G is a Gröbner basis of an ideal I for this monomial ordering, then $$G\cap K[Y]$$ is a Gröbner basis of $$I\cap K[Y]$$ (this ideal is often called the elimination ideal). Moreover, $$G\cap K[Y]$$ consists exactly of the polynomials of $f, k$ whose leading terms belong to $\{f, k, h\}$ (this makes very easy the computation of $$G\cap K[Y]$$, as only the leading monomials need to be checked).

This elimination property has many applications, some described in the next sections.

Another application, in algebraic geometry, is that elimination realizes the geometric operation of projection of an affine algebraic set into a subspace of the ambient space: with above notation, the (Zariski closure of) the projection of the algebraic set defined by the ideal I into the Y-subspace is defined by the ideal $$I\cap K[Y].$$

The lexicographical ordering such that $$x_1>\cdots >x_n$$ is an elimination ordering for every partition $$\{x_1, \ldots, x_k\},\{x_{k+1},\ldots,x_n\}.$$ Thus a Gröbner basis for this ordering carries much more information than usually necessary. This may explain why Gröbner bases for the lexicographical ordering are usually the most difficult to compute.

Intersecting ideals
If $I$ and $J$ are two ideals generated respectively by {f1, ..., fm} and {g1, ..., gk}, then a single Gröbner basis computation produces a Gröbner basis of their intersection $f_{I}$. For this, one introduces a new indeterminate t, and one uses an elimination ordering such that the first block contains only t and the other block contains all the other variables (this means that a monomial containing t is greater than every monomial that does not contain t). With this monomial ordering, a Gröbner basis of $G$ consists in the polynomials that do not contain t, in the Gröbner basis of the ideal
 * $$K=\langle tf_1,\ldots, tf_m, (1-t)g_1, \ldots, (1-t)g_k\rangle.$$

In other words, $K[Y]$ is obtained by eliminating t in K. This may be proven by remarking that the ideal K consists of the polynomials $$(a-b)t+b$$ such that $$a\in I$$ and $$b\in J$$. Such a polynomial is independent of t if and only if $I ∩ J$, which means that $$b\in I\cap J.$$

Implicitization of a rational curve
A rational curve is an algebraic curve that has a set of parametric equations of the form

 * $$\begin{align}

x_1 &= \frac{f_1(t)}{g_1(t)}\\ &\;\;\vdots\\ x_n &= \frac{f_n(t)}{g_n(t)}, \end{align} $$ where $$f_i(t)$$ and $$g_i(t)$$ are univariate polynomials for 1 ≤ i ≤ n. One may (and will) suppose that $$f_i(t)$$ and $$g_i(t)$$ are coprime (they have no non-constant common factors).

Implicitization consists in computing the implicit equations of such a curve. In case of n = 2, that is for plane curves, this may be computed with the resultant. The implicit equation is the following resultant:
 * $$\text{Res}_t(g_1x_1-f_1,g_2x_2-f_2).$$

Elimination with Gröbner bases allows to implicitize for any value of n, simply by eliminating t in the ideal $$\langle g_1x_1-f_1,\ldots, g_nx_n-f_n\rangle.$$ If n = 2, the result is the same as with the resultant, if the map $$t \mapsto (x_1,x_2)$$ is injective for almost every t. In the other case, the resultant is a power of the result of the elimination.

Saturation
When modeling a problem by polynomial equations, it is often assumed that some quantities are non-zero, so as to avoid degenerate cases. For example, when dealing with triangles, many properties become false if the triangle degenerates to a line segment, i.e. the length of one side is equal to the sum of the lengths of the other sides. In such situations, one cannot deduce relevant information from the polynomial system unless the degenerate solutions are ignored. More precisely, the system of equations defines an algebraic set which may have several irreducible components, and one must remove the components on which the degeneracy conditions are everywhere zero.

This is done by saturating the equations by the degeneracy conditions, which may be done via the elimination property of Gröbner bases.

Definition of the saturation
The localization of a ring consists in adjoining to it the formal inverses of some elements. This section concerns only the case of a single element, or equivalently a finite number of elements (adjoining the inverses of several elements is equivalent to adjoining the inverse of their product). The localization of a ring R by an element f is the ring $$R_f=R[t]/(1-ft),$$ where t is a new indeterminate representing the inverse of f. The localization of an ideal $I$ of R is the ideal $$R_fI$$ of $$I_f.$$ When R is a polynomial ring, computing in $$R_f$$ is not efficient because of the need to manage the denominators. Therefore, localization is usually replaced by the operation of saturation.

The saturation with respect to f of an ideal $I$ in R is the inverse image of $$R_f I$$ under the canonical map from R to $$R_f.$$ It is the ideal $$I:f^\infty= \{g\in R \mid (\exists k\in \mathbb N) f^k g\in I\}$$ consisting in all elements of R whose product with some power of f belongs to $I$.

If $J$ is the ideal generated by $I$ and 1−ft in R[t], then $$I:f^\infty = J\cap R.$$ It follows that, if R is a polynomial ring, a Gröbner basis computation eliminating t produces a Gröbner basis of the saturation of an ideal by a polynomial.

The important property of the saturation, which ensures that it removes from the algebraic set defined by the ideal $I$ the irreducible components on which the polynomial f is zero, is the following: The primary decomposition of $$I:f^\infty$$ consists of the components of the primary decomposition of I that do not contain any power of f.

Computation of the saturation
A Gröbner basis of the saturation by f of a polynomial ideal generated by a finite set of polynomials F, may be obtained by eliminating t in $$F\cup\{1-tf\},$$ that is by keeping the polynomials independent of t in the Gröbner basis of $$F\cup\{1-tf\}$$ for an elimination ordering eliminating t.

Instead of using F, one may also start from a Gröbner basis of F. Which method is most efficient depends on the problem. However, if the saturation does not remove any component, that is if the ideal is equal to its saturated ideal, computing first the Gröbner basis of F is usually faster. On the other hand, if the saturation removes some components, the direct computation may be dramatically faster.

If one wants to saturate with respect to several polynomials $$f_1,\ldots, f_k$$ or with respect to a single polynomial which is a product $$f = f_1 \cdots f_k, $$ there are three ways to proceed which give the same result but may have very different computation times (it depends on the problem which is the most efficient).
 * Saturating by $$f = f_1 \cdots f_k $$ in a single Gröbner basis computation.
 * Saturating by $$f_1,$$ then saturating the result by $$f_2,$$ and so on.
 * Adding to F or to its Gröbner basis the polynomials $$1-t_1f_1, \ldots, 1-t_kf_k,$$ and eliminating the $$t_i$$ in a single Gröbner basis computation.

Effective Nullstellensatz
Hilbert's Nullstellensatz has two versions. The first one asserts that a set of polynomials has no common zeros over an algebraic closure of the field of the coefficients, if and only if 1 belongs to the generated ideal. This is easily tested with a Gröbner basis computation, because 1 belongs to an ideal if and only if 1 belongs to the Gröbner basis of the ideal, for any monomial ordering.

The second version asserts that the set of common zeros (in an algebraic closure of the field of the coefficients) of an ideal is contained in the hypersurface of the zeros of a polynomial f, if and only if a power of f belongs to the ideal. This may be tested by saturating the ideal by f; in fact, a power of f belongs to the ideal if and only if the saturation by f provides a Gröbner basis containing 1.

Implicitization in higher dimension
By definition, an affine rational variety of dimension k may be described by parametric equations of the form
 * $$\begin{align}

x_1&=\frac{p_1}{p_0}\\ &\;\;\vdots\\ x_n&=\frac{p_n}{p_0}, \end{align} $$ where $$p_0,\ldots,p_n$$ are n+1 polynomials in the k variables (parameters of the parameterization) $$t_1,\ldots,t_k.$$ Thus the parameters $$t_1,\ldots,t_k$$ and the coordinates $$x_1,\ldots,x_n$$ of the points of the variety are zeros of the ideal
 * $$I=\left\langle p_0x_1-p_1, \ldots, p_0x_n-p_n\right\rangle.$$

One could guess that it suffices to eliminate the parameters to obtain the implicit equations of the variety, as it has been done in the case of curves. Unfortunately this is not always the case. If the $$p_i$$ have a common zero (sometimes called base point), every irreducible component of the non-empty algebraic set defined by the $$p_i$$ is an irreducible component of the algebraic set defined by I. It follows that, in this case, the direct elimination of the $$t_i$$ provides an empty set of polynomials.

Therefore, if k>1, two Gröbner basis computations are needed to implicitize:
 * 1) Saturate $$I$$ by $$p_0$$ to get a Gröbner basis $$G$$
 * 2) Eliminate the $$t_i$$ from $$G$$ to get a Gröbner basis of the ideal (of the implicit equations) of the variety.

Algorithms and implementations
Buchberger's algorithm is the oldest algorithm for computing Gröbner bases. It has been devised by Bruno Buchberger together with the Gröbner basis theory. It is straightforward to implement, but it appeared soon that raw implementations can solve only trivial problems. The main issues are the following ones:
 * 1) Even when the resulting Gröbner basis is small, the intermediate polynomials can be huge. It results that most of the computing time may be spent in memory management. So, specialized memory management algorithms may be a fundamental part of an efficient implementation.
 * 2) The integers occurring during a computation may be sufficiently large for making fast multiplication algorithms and multimodular arithmetic useful. For this reason, most optimized implementations use the GMPlibrary. Also, modular arithmetic, Chinese remainder theorem and Hensel lifting are used in optimized implementations
 * 3) The choice of the S-polynomials to reduce and of the polynomials used for reducing them is devoted to heuristics. As in many computational problems, heuristics cannot detect most hidden simplifications, and if heuristic choices are avoided, one may get a dramatic improvement of the algorithm efficiency.
 * 4) In most cases most S-polynomials that are computed are reduced to zero; that is, most computing time is spent to compute zero.
 * 5) The monomial ordering that is most often needed for the applications (pure lexicographic) is not the ordering that leads to the easiest computation, generally the ordering degrevlex.

For solving 3. many improvements, variants and heuristics have been proposed before the introduction of F4 and F5 algorithms by Jean-Charles Faugère. As these algorithms are designed for integer coefficients or with coefficients in the integers modulo a prime number, Buchberger's algorithm remains useful for more general coefficients.

Roughly speaking, F4 algorithm solves 3. by replacing many S-polynomial reductions by the row reduction of a single large matrix for which advanced methods of linear algebra can be used. This solves partially issue 4., as reductions to zero in Buchberger's algorithm correspond to relations between rows of the matrix to be reduced, and the zero rows of the reduced matrix correspond to a basis of the vector space of these relations.

F5 algorithm improves F4 by introducing a criterion that allows reducing the size of the matrices to be reduced. This criterion is almost optimal, since the matrices to be reduced have full rank in sufficiently regular cases (in particular, when the input polynomials form a regular sequence). Tuning F5 for a general use is difficult, since its performances depend on an order on the input polynomials and a balance between the incrementation of the working polynomial degree and of the number of the input polynomials that are considered. To date (2022), there is no distributed implementation that is significantly more efficient than F4, but, over modular integers F5 has been used successfully for several cryptographic challenges; for example, for breaking HFE challenge.

Issue 5. has been solved by the discovery of basis conversion algorithms that start from the Gröbner basis for one monomial ordering for computing a Gröbner basis for another monomial ordering. FGLM algorithm is such a basis conversion algorithm that works only in the zero-dimensional case (where the polynomials have a finite number of complex common zeros) and has a polynomial complexity in the number of common zeros. A basis conversion algorithm that works is the general case is the Gröbner walk algorithm. In its original form, FGLM may be the critical step for solving systems of polynomial equations because FGML does not take into account the sparsity of involved matrices. This has been fixed by the introduction of sparse FGLM algorithms.

Most general-purpose computer algebra systems have implementations of one or several algorithms for Gröbner bases, often also embedded in other functions, such as for solving systems of polynomial equations or for simplifying trigonometric functions; this is the case, for example, of CoCoA, GAP, Macaulay 2, Magma, Maple, Mathematica, SINGULAR, SageMath and SymPy. When F4 is available, it is generally much more efficient than Buchberger's algorithm. The implementation techniques and algorithmic variants are not always documented, although they may have a dramatic effect on efficiency.

Implementations of F4 and (sparse)-FGLM are included in the library Msolve. Beside Gröbner algorithms, Msolve contains fast algorithms for real-root isolation, and combines all these functions in an algorithm for the real solutions of systems of polynomial equations that outperforms dramatically the other software for this problem (Maple and Magma). Msolve is available on GitHub, and is interfaced with Julia, Maple and SageMath; this means that Msolve can be used directly from within these software environments.

Complexity
The complexity of the Gröbner basis computations is commonly evaluated in term of the number $n$ of variables and the maximal degree $d$ of the input polynomials.

In the worst case, the main parameter of the complexity is the maximal degree of the elements of the resulting reduced Gröbner basis. More precisely, if the Gröbner basis contains an element of a large degree $D$, this element may contain $$\Omega(D^n)$$ nonzero terms whose computation requires a time of $$\Omega(D^n)>D^{\Omega(n)}.$$ On the other hand, if all polynomials in the reduced Gröbner basis a homogeneous ideal have a degree of at most $D$, the Gröbner basis can be computed by linear algebra on the vector space of polynomials of degree less than $I ∩ J$, which has a dimension $$O(D^n).$$ So, the complexity of this computation is $$O(D^n)^{O(1)}= D^{O(n)}.$$

The worst-case complexity of a Gröbner basis computation is doubly exponential in $n$. More precisely, the complexity is upper bounded by a polynomial in $d^{2^n}.$ Using little o notation, it is therefore bounded by $d^{2^{n+o(n)}}.$  On the other hand, examples have been given of reduced Gröbner bases containing polynomials of degree $d^{2^{\Omega(n)}},$ or containing $d^{2^{\Omega(n)}}$ elements. As every algorithm for computing a Gröbner basis must write its result, this provides a lower bound of the complexity.

Gröbner basis is EXPSPACE-complete.

Generalizations
The concept and algorithms of Gröbner bases have been generalized to submodules of free modules over a polynomial ring. In fact, if $L$ is a free module over a ring $R$, then one may consider the direct sum $$R\oplus L$$ as a ring by defining the product of two elements of $L$ to be $I ∩ J$. This ring may be identified with $$R[e_1, \ldots, e_l]/\left\langle \{e_ie_j|1\le i\le j\le l\}\right\rangle$$, where $$e_1, \ldots, e_l$$ is a basis of L. This allows identifying a submodule of $L$ generated by $$g_1, \ldots, g_k$$ with the ideal of $$R[e_1, \ldots, e_l]$$ generated by $$g_1, \ldots, g_k$$ and the products $$e_ie_j$$, $$1\le i\le j\le l$$. If $R$ is a polynomial ring, this reduces the theory and the algorithms of Gröbner bases of modules to the theory and the algorithms of Gröbner bases of ideals.

The concept and algorithms of Gröbner bases have also been generalized to ideals over various rings, commutative or not, like polynomial rings over a principal ideal ring or Weyl algebras.

Error-Correcting Codes
Gröbner basis has been applied in the theory of error-correcting codes for algebraic decoding. By using Gröbner basis computation on various forms of error-correcting equations, decoding methods were developed for correcting errors of cyclic codes, affine variety codes, algebraic-geometric codes and even general linear block codes. Applying Gröbner basis in algebraic decoding is still a research area of channel coding theory.

title: Gröbner basis


text:
Common nighthawk

The common nighthawk or bullbat (Chordeiles minor) is a medium-sized crepuscular or nocturnal bird  of the Americas within the nightjar (Caprimulgidae) family, whose presence and identity are best revealed by its vocalization. Typically dark (gray, black and brown), displaying cryptic colouration and intricate patterns, this bird is difficult to spot with the naked eye during the day. This bird is most conspicuous when in its buoyant and erratic flight. The most remarkable feature of this aerial insectivore is its small beak that belies the massiveness of its mouth. Some claim appearance similarities to owls. With its horizontal stance and short legs, the common nighthawk does not travel frequently on the ground, instead preferring to perch horizontally, parallel to branches, on posts, on the ground or on a roof. The males of this species may roost together but the bird is primarily solitary. The common nighthawk shows variability in territory size.

This caprimulgid has a large, flattened head with large eyes; facially it lacks rictal bristles. The common nighthawk has long slender wings that at rest extend beyond a notched tail. There is noticeable barring on the sides and abdomen, also white wing-patches.

The common nighthawk measures 22 to 25 cm long, displays a wing span of 51 to 61 cm weighs 55 to 98 g, and has a life span of 4 to 5 years.

Names and etymology
The genus name Chordeiles is from Ancient Greek khoreia, a dance with music, and deile, "evening". The specific minor is Latin for "smaller".

The term "nighthawk", first recorded in the King James Bible version of 1611, was originally a local name in England for the European nightjar. Its use in the Americas referring to members of the genus Chordeiles and related genera was first recorded in 1778.

The common nighthawk is sometimes called a "bull-bat", due to its perceived "bat-like" flight, and the "bull-like" boom made by its wings as it pulls from a dive.

They, in addition to other nightjars, are also sometimes called "bugeaters", for their insectivore diet. The common nighthawk is likely the reason that Nebraska's state nickname was once the "Bugeater State", and its people were known as "bugeaters". The Nebraska Cornhuskers college athletic teams were also briefly known the Bugeaters, before adopting their current name, which was also adopted by the state as a whole. A semi-professional soccer team in Nebraska, Nebraska Bugeaters FC, now uses the moniker.

Taxonomy
Within the family Caprimulgidae, the subfamily Chordeilinae (nighthawks) are limited to the New World and are distinguished from the subfamily Caprimulginae, by the lack of rictal bristles.

The American Ornithologists' Union treated the smaller Antillean nighthawk as conspecific with the common nighthawk until 1982.

Up until the early 19th century, the common nighthawk and the whip-poor-will were thought to be one species. The latter's call was explained as the nocturnal expression of the common nighthawk. Alexander Wilson, "The Father of American Ornithology", correctly made the differentiation between the two species.

Subspecies
There are 9 currently recognized subspecies:
 * C. m. panamensis – Eisenmann, 1962 : breeds on the Pacific slope of Panama and north west Costa Rica. It is noted to depart Panama during winter for points in South America
 * C. m. neotropicalis – Selander & Alvarez del Toro, 1955 : breeds in south Mexico and Honduras
 * C. m. howelli – Oberholser, 1914 : breeds in west central United States (north Texas, west Oklahoma, and Kansas to east Colorado, less typical form in central Colorado, north east Utah and Wyoming). It is darker than sennetti and paler and less cinnamon than henryi.
 * C. m. hesperis – Grinnell, 1905 : breeds in south west Canada (British Columbia and Alberta), the western interior of United States (Washington, Montana, Nevada, interior California, Utah, extreme north Colorado, west Wyoming). It is darker than sennetti and paler and less cinnamon than henryi.
 * C. m. aserriensis – Cherrie, 1896 : breeds from south central Texas to north Mexico. It is darker than sennetti and paler and less cinnamon than henryi.
 * C. m. chapmani – Coues, 1888 : breeds from southeast Kansas to east North Carolina and southwards to south east Texas and south Florida. It is the darkest of the subspecies.
 * C. m. sennetti – Coues, 1888 : breeds in the north Great Plains: east Montana, south Saskatchewan, Manitoba, southwards to North Dakota, Minnesota and Iowa. It is the palest of the subspecies.
 * C. m. henryi – Cassin, 1855 : breeds from south east Utah and south west Colorado through mountains of west Texas, Arizona and New Mexico (less north east) to east Sonora, Chihuahua, and Durango. It is unique with ochraceous to deep cinnamon feather edges on upperparts.
 * C. m. minor – (J.R. Forster, 1771) : breeds from south east Alaska to Vancouver Island, British Columbia, Canada, and south Canada/northern United States (Minnesota, Indiana) to Virginia, North Carolina, Georgia and Oklahoma. Considered by some as the darkest subspecies.

History
This species is recorded as widespread during the Late Pleistocene, from Virginia to California and from Wyoming to Texas.

In the late 19th and early 20th centuries, because their name contained the word "hawk", they had habits of diurnal insect hunting, and they travelled in migrating flocks, they were hunted for sport and nourishment and because they were seen as predators.

Field identification
The common nighthawk is distinguished from other caprimulguids by its forked tail (includes a white bar in males); its long, unbarred, pointed wings with distinctive white patches; its lack of rictal bristles, and the key identifier – their unmistakable calls. These birds range from 21 to 25 cm in total length and from 51 to 61 cm in wingspan. Body mass can vary from 55 to 98 g. Among standard measurements, the wing chord is 17.2 to 21.3 cm, the tail is 13 to 15.1 cm, the bill is 0.5 to 0.8 cm and the tarsus is 1.2 to 1.6 cm.

The common nighthawk resembles both the Antillean nighthawk and the lesser nighthawk and occurs at least seasonally in the entire North American range of both of these species. The lesser nighthawk is a smaller bird and displays more buffy on the undertail coverts, where the common nighthawk shows white. Common nighthawks and Antillean nighthawks exhibit entirely dark on the basal portion of the primary feathers, whereas lesser nighthawks have bands of buffy spots. Common and Antillean nighthawks have a longer outermost primary conveying a pointier wing tip than the lesser nighthawk. The common nighthawk forages higher above ground than the lesser nighthawk and has a different call. The only reliable way to distinguish Antillean nighthawk without disturbance is also by the differences in their calls. Visually, they may only be distinguished as different from the common nighthawk once in the hand. Subtle differences are reported to be a challenge in field identification.

Habitat and distribution
The common nighthawk may be found in forests, desert, savannahs, beach and desert scrub, cities, and prairies, at elevations of sea level or below to 3000 m. Nighthawks prefer to nest in edge and early successional habitats, making them one of only a handful of birds which will live and hunt in burned or clearcut patches of forest. The common nighthawk is drawn into urban built-up areas by insects.

The common nighthawk is the only nighthawk occurring over the majority of northern North America.

Food availability is likely a key factor in determining which and when areas are suitable for habitation. The common nighthawk is not well adapted to survive in poor conditions, specifically low food availability. Therefore, a constant food supply consistent with warmer temperatures is a driving force for migration and ultimately survival.

It is thought that the bird is not able to enter torpor, although recent evidence suggests it does.

Migration
During migration, common nighthawks may travel 2500 to 6800 km. They migrate by day or night in loose flocks, frequently numbering in the thousands; flocks have not been observed with a visible leader. The enormous distance travelled between breeding grounds and wintering range is one of the North America's longer migrations. The northbound journey commences at the end of February and the birds reach destinations as late as mid-June. The southbound migration commences mid-July and reaches a close in early October.

While migrating, these birds have been reported travelling through middle America, Florida, the West Indies, Cuba, the Caribbean and Bermuda, finally completing their journey in the wintering grounds of South America, primarily Argentina.

As aerial insectivores, the migrants will feed en route, congregating to hunt in marshes, rivers and on lakeshores. In Manitoba and Ontario, Canada, it is reported that during migration the nighthawks are seen most commonly in the late afternoon, into the evening, with a burst of sunset feeding activities.

Additionally, it has been noted that during migration the birds may fly closer to the ground than normal; possibly foraging for insects. There is speculation that feeding also occurs at higher altitudes.

The common nighthawk winters in southern South America, but distribution in this range is poorly known due to difficulties in distinguishing the bird from the lesser nighthawk and in differentiating between migrants and overwintering birds. In some South and Central American countries, a lack of study has led to restricted and incomplete records of the bird. Records do support wintering in Ecuador, Peru, Bolivia, Brazil, Paraguay, Uruguay and Argentina.

Molt
In the common nighthawk, all bodily plumage and rectrices are replaced in the post-juvenile molt. This moult commences in September at the breeding grounds; the majority of the body plumage is replaced but wing-coverts and rectrices are not completed until January–February, once the bird arrives at the wintering grounds. There is no other molt prior to the annual molt of the adult. Common nighthawk adults have a complete molt that occurs mostly or completely on wintering grounds and is not completed until January or February.

Vocalization
There are no differences between the calls and song of the common nighthawk. The most conspicuous vocalization is a nasal peent or beernt during flight. Peak vocalizations are reported 30 to 45 minutes after sunset.

A croaking auk auk auk is vocalized by males while in the presence of a female during courtship. Another courtship sound, thought to be made solely by the males, is the boom, created by air rushing through the primaries after a quick downward flex of the wings during a daytime dive.

In defense of their nests, the females make a rasping sound, and males clap their wings together. Strongly territorial males will perform dives against fledglings, females, and intruders such as humans or raccoons.

Feeding and diet
Frequent flyers, the long-winged common nighthawk hunts on the wing for extended periods at high altitudes or in open areas. Crepuscular, flying insects are its preferred food source. The hunt ends as dusk becomes night, and resumes when night becomes dawn. Nighttime feeding (in complete darkness) is rare, even on evenings with a full moon. The bird displays opportunistic feeding tendencies, although it may be able to fine-tune its meal choice in the moments before capture. Common nighthawks have been shown to prefer eating Coleopterids (beetles) and Hymenopterids (bees, ants, and wasps), seeking these insects out in their habitats. While the most common type of insects in their diets are Lepidopterans (butterflies and moths), they actively avoid eating Dipterids (flies).

Vision is presumed to be the main detection sense; no evidence exists to support the use of echolocation. The birds have been observed to converge on artificial light sources in an effort to forage for insects enticed by the light. The average flight speed of common nighthawks is 23.4 km/h.

Drinking
The common nighthawk was observed to drink on its winter range by flying extremely low over the surface of the water.

Waste excretion
The common nighthawk is recognized to discharge feces around nest and roosting positions. The bird will sporadically defecate in flight. The defecation is pungent.

Reproduction and nesting
The common nighthawk breeds during the period of mid-March to early October. It most commonly has only one brood per season, however sometimes a second brood is produced. The bird is assumed to breed every year. Reuse of nests by females in subsequent years has been reported. A monogamous habit has also recently been confirmed.

Courting and mate selection occur partially in flight. The male dives and booms (see Vocalization) in an effort to garner female attention; the female may be in flight herself or stationary on the ground.

Copulation occurs when the pair settles on the ground together; the male with his rocking body, widespread tail wagging and bulging throat expresses guttural croaking sounds. This display by the male is performed repeatedly until copulation.

The preferred breeding/nesting habitat is in forested regions with expansive rocky outcrops, in clearings, in burned areas or in small patches of sandy gravel. The eggs are not laid in a nest, but on bare rock, gravel, or sometimes a living substrate such as lichen. Least popular are breeding sites in agricultural settings. As displayed in the latter portion of the 20th century, urban breeding is in decline. If urban breeding sites do occur, they are observed on flat gravel rooftops.

It is a solitary nester, putting great distances between itself and other pairs of the same species, but a nest would more commonly occur in closer proximity to other species of birds.

Females choose the nest site and are the primary incubators of the eggs; males will incubate occasionally. Incubation time varies but is approximately 18 days. The female will leave the nest unattended during the evening in order to feed. The male will roost in a neighbouring tree (the spot he chooses changes daily); he guards the nest by diving, hissing, wing-beating or booming at the sites. In the face of predation, common nighthawks do not abandon the nest easily; instead they likely rely on their cryptic colouration to camouflage themselves. If a departure does occur, the females have been noted to fly away, hissing at the intruder or performing a disturbance display.

Incubation, hatching and young
The eggs are elliptical, strong, and variably coloured with heavy speckling. The common nighthawk lays two 6 – eggs per clutch; the eggs are laid over a period of 1 to 2 days. The female alone displays a brood patch.

The chicks may be heard peeping in the hours before they hatch. Once the chicks have broken out of the shells, the removal of the debris is necessary in order to avoid predators. The mother may carry the eggshells to another location or consume a portion of them. Once hatched, the nestlings are active and have their eyes fully or half open; additionally they display a sparing cover of soft down feathers. The chicks are semi-precocial. By day 2, the hatchlings' bodily mass will double and they will be able to self-propel towards their mother's call. The young will hiss at an intruder.

The young are fed by regurgitation before sunrise and after sunset. The male parent assists in feeding fledglings and will also feed the female during nesting. No records exist to support a parent's ability to physically carry a chick.

On their 18th day, the young will make their first flight; by days 25–30, they are flying proficiently. The young are last seen with their parents on day 30. Complete development is shown between their 45–50th day. At day 52, the juvenile will join the flock, potentially migrating. Juvenile birds, in both sexes, are lighter in colour and have a smaller white wing-patch than adult common nighthawks.

Predators
Like other members of the caprimulgid clan, the nighthawk's ground nesting habits endanger eggs and nestlings to predation by ground carnivores, such as skunks, raccoons and opossums. Confirmed predation on adults is restricted to domestic cats, golden eagles, and great horned owls. Peregrine falcons have also been confirmed to attack nighthawks as prey, although the one recorded predation attempt was unsuccessful. Other suspected predators are likely to attack them, such as dogs, coyotes, foxes, hawks, American kestrels, owls, crows and ravens, and snakes.

Status and conservation
There has been a general decline in the number of common nighthawks in North America, but some population increases also have occurred in other geographical locations. The bird's large range makes individual risk thresholds in specific regions difficult to establish. In Ontario, the common nighthawk is rated as a species of special concern.

The Common nighthawk's trait of being a ground-nesting bird makes it particularly susceptible to predators, some of which include domestic cats, ravens, snakes, dogs, coyotes, falcons and owls.

Lack of flat roofs, pesticides, increased predation and loss of habitat are noted factors of their decline. Further unstudied potential causes of decline include climate change, disease, road kills, man-made towers (posing aerial hazards), and parasites.

The absence of flat roofs (made with gravel) in urban settings is an important cause of decline. In an effort to provide managed breeding areas, gravel pads have been added in the corners of rubberized roofs; this proves acceptable, as nesting has been observed.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Common nighthawk


text:
CCX

CCX may mean:

 * 210 in roman numerals
 * AD 210, the year of the Common Era
 * Chicago Climate Exchange, North American greenhouse gas reduction and trading system
 * Cisco Compatible EXtensions, a specification for 802.11 wireless LAN chip manufacturers
 * Koenigsegg CCX, a sports car
 * CCX, the coal mining company that is controlled by the Brazilian conglomerate EBX Group
 * CCX, the name given to Core Complex, a building block in AMD's Zen microarchitecture and its successor architectures
 * CCX, the Australian Stock Exchange code for City Chic Collective

title: CCX


text:
Oto

Oto, Ōtō, or OTO may refer to:

People

 * Oto (name), including a list of people with the name
 * The Otoe tribe (also spelled Oto), a Native American people

Places

 * Oto, Spain, a village in the Valle de Broto, in Huesca, Aragon

Japan

 * Ōtō, Fukuoka
 * Ōtō, Nara, merged into Gojō in 2005
 * Ōtō, Wakayama, merged into Tanabe in 2005

United States

 * Oto, Iowa
 * Oto, Missouri
 * Oto Reservation, formerly located in southeastern Nebraska
 * OTO Homestead and Dude Ranch, Montana

Other uses

 * Greta oto, a butterfly of family Nymphalidae
 * Ordo Templi Orientis, organization centered on the Law of Thelema
 * Oto (album), the third album by Fluke, released in 1995
 * OTO Awards, a Slovak awards show
 * Otocinclus, a genus of armored catfish
 * Zebra oto
 * Oto-Manguean languages, a large family comprising several families of Native American languages
 * Oto-Pamean languages
 * Oto Melara, an Italian defense company, formerly known as Odero Terni Orlando
 * OTO (Slovenian TV channel), part of media company Pro Plus
 * Seibi Oto, a fictional character in the anime series Sky Girls
 * Osu! Tatakae! Ouendan!, a 2005 rhythm video game

title: Oto


text:
Correctness (computer science)

In theoretical computer science, an algorithm is correct with respect to a specification if it behaves as specified. Best explored is functional correctness, which refers to the input-output behavior of the algorithm: for each input it produces an output satisfying the specification.

Within the latter notion, partial correctness, requiring that if an answer is returned it will be correct, is distinguished from total correctness, which additionally requires that an answer is eventually returned, i.e. the algorithm terminates. Correspondingly, to prove a program's total correctness, it is sufficient to prove its partial correctness, and its termination. The latter kind of proof (termination proof) can never be fully automated, since the halting problem is undecidable.

For example, successively searching through integers 1, 2, 3, … to see if we can find an example of some phenomenon—say an odd perfect number—it is quite easy to write a partially correct program (see box). But to say this program is totally correct would be to assert something currently not known in number theory.

A proof would have to be a mathematical proof, assuming both the algorithm and specification are given formally. In particular it is not expected to be a correctness assertion for a given program implementing the algorithm on a given machine. That would involve such considerations as limitations on computer memory.

A deep result in proof theory, the Curry–Howard correspondence, states that a proof of functional correctness in constructive logic corresponds to a certain program in the lambda calculus. Converting a proof in this way is called program extraction.

Hoare logic is a specific formal system for reasoning rigorously about the correctness of computer programs. It uses axiomatic techniques to define programming language semantics and argue about the correctness of programs through assertions known as Hoare triples.

Software testing is any activity aimed at evaluating an attribute or capability of a program or system and determining that it meets its required results. Although crucial to software quality and widely deployed by programmers and testers, software testing still remains an art, due to limited understanding of the principles of software. The difficulty in software testing stems from the complexity of software: we can not completely test a program with moderate complexity. Testing is more than just debugging. The purpose of testing can be quality assurance, verification and validation, or reliability estimation. Testing can be used as a generic metric as well. Correctness testing and reliability testing are two major areas of testing. Software testing is a trade-off between budget, time and quality.

title: Correctness (computer science)


text:
Hundred (county division)

A hundred is an administrative division that is geographically part of a larger region. It was formerly used in England, Wales, some parts of the United States, Denmark, Southern Schleswig, Sweden, Finland, Norway, the Bishopric of Ösel–Wiek, Curonia, the Ukrainian state of the Cossack Hetmanate and in Cumberland County in the British Colony of New South Wales. It is still used in other places, including in Australia (in South Australia and the Northern Territory).

Other terms for the hundred in English and other languages include wapentake, herred (Danish and Bokmål Norwegian), herad (Nynorsk Norwegian), hérað (Icelandic), härad or hundare (Swedish), Harde (German), hiird (North Frisian), satakunta or kihlakunta (Finnish), kihelkond (Estonian), kiligunda (Livonian), cantref (Welsh) and sotnia (Slavic).

In Ireland, a similar subdivision of counties is referred to as a barony, and a hundred is a subdivision of a particularly large townland (most townlands are not divided into hundreds).

Etymology
The origin of the division of counties into hundreds is described by the Oxford English Dictionary (OED) as "exceedingly obscure". It may once have referred to an area of 100 hides; in early Anglo-Saxon England a hide was the amount of land farmed by and required to support a peasant family, but by the eleventh century in many areas it supported four families. Alternatively the hundred may have been an area originally settled by one "hundred" men at arms, or the area liable to provide one "hundred" men under arms. In this early medieval use, the number term "hundred" can itself be unclear, meaning the "short" hundred (100) or in some contexts the long hundred of 120.

There was an equivalent traditional Germanic system. In Old High German a huntari is a division of a gau, but the OED believes that the link between the two is not established.

Administrative functions
From the 11th century in England, and to a lesser extent from the 16th century in Wales, and until the middle of the 19th century, the annual assemblies had varying degrees of power at a local level in the feudal system. Of chief importance was their more regular use for taxation, and six centuries of taxation returns for the divisions survive to this day.

Groupings of divisions, small shires, were used to define parliamentary constituencies from 1832 to 1885. On the redistribution of seats in 1885 a different county subdivision, the petty sessional division, was used. Hundreds were also used to administer the first five national censuses from 1801 to 1841.

The system of county divisions was not as stable as the system of counties being established at the time, and lists frequently differ on how many hundreds a county had. In many parts of the country, the Domesday Book contained a radically different set of divisions from that which later became established. The numbers of divisions in each county varied widely. Leicestershire had six (up from four at Domesday), whereas Devon, nearly three times the size, had 32.

By the end of the 19th century, several single-purpose subdivisions of counties, such as poor law unions, sanitary districts, and highway districts, had sprung up, which, together with the introduction of urban districts and rural districts in 1894, mostly replaced the role of the parishes, and to a lesser extent the less extensive role of hundreds. The division names gave their name to multiple modern local government districts.

Hundred
In south and western England, a hundred was the division of a shire for military and judicial purposes under the common law, which could have varying extent of common feudal ownership, from complete suzerainty to minor royal or ecclesiastical prerogatives and rights of ownership. Until the introduction of districts by the Local Government Act 1894, hundreds were the only widely used assessment unit intermediate in size between the parish, with its various administrative functions, and the county, with its formal, ceremonial functions.

The term "hundred" is first recorded in the laws of Edmund I (939–46) as a measure of land and the area served by a hundred court. In the Midlands, they often covered an area of about 100 hides, but this did not apply in the south; this may suggest that it was an ancient West Saxon measure that was applied rigidly when Mercia became part of the newly established English kingdom in the 10th century. The Hundred Ordinance, which dates to the middle of the century, provided that the court was to meet monthly, and thieves were to be pursued by all the leading men of the district.

During Norman times, the hundred would pay geld based on the number of hides. To assess how much everyone had to pay, a clerk and a knight were sent by the king to each county; they sat with the shire-reeve (or sheriff), of the county and a select group of local knights. There would be two knights from each hundred. After it was determined what geld had to be paid, the bailiff and knights of the hundred were responsible for getting the money to the sheriff, and the sheriff for getting it to the Exchequer.

Above the hundred was the shire, under the control of a sheriff. Hundred boundaries were independent of both parish and county boundaries, although often aligned, meaning that a hundred could be split between counties, or a parish could be split between hundreds. Exceptionally, in the counties of Kent and Sussex, there was a sub-division intermediate in size between the hundred and the shire: several hundreds were grouped together to form lathes in Kent and rapes in Sussex. At the time of the Norman conquest of England, Kent was divided into seven lathes and Sussex into four rapes.

Hundred courts
Over time, the principal functions of the hundred became the administration of law and the keeping of the peace. By the 12th century, the hundred court was held twelve times a year. This was later increased to fortnightly, although an ordinance of 1234 reduced the frequency to once every three weeks. In some hundreds, courts were held at a fixed place; while in others, courts moved with each sitting to a different location. The main duty of the hundred court was the maintenance of the frankpledge system. The court was formed of twelve freeholders, or freemen. According to a 13th-century statute, freeholders did not have to attend their lord's manorial courts, thus any suits involving them would be heard in a hundred court.

For especially serious crimes, the hundred was under the jurisdiction of the Crown; the chief magistrate was a sheriff, and his circuit was called the sheriff's tourn. However, many hundreds came into private hands, with the lordship of the hundred being attached to the principal manor of the area and becoming hereditary. Helen Cam estimated that even before the Conquest, over 130 hundreds were in private hands; while an inquest of 1316 found that by that date 388 of 628 named hundreds were held, not by the Crown, but by its subjects. Where a hundred was under a lord, a steward, acting as a judge and the chief official of the lord of the manor, was appointed in place of a sheriff.

The importance of the hundred courts declined from the 17th century, and most of their powers were extinguished with the establishment of county courts in 1867. The remaining duty of the inhabitants of a hundred to make good damages caused by riot was ended by the Riot (Damages) Act 1886, when the cost was transferred to the county police rate. The jurisdiction of hundred courts was curtailed by the Administration of Justice Act 1977.

Chiltern Hundreds
The steward of the Chiltern Hundreds is notable as a legal fiction, owing to a quirk of British Parliamentary law. A Crown Steward was appointed to maintain law and order in the area, but these duties ceased to be performed in the 16th century, and the holder ceased to gain any benefits during the 17th century. The position has since been used as a procedural device to allow resignation from the British House of Commons as a (formerly) remunerated office of the Crown.

Wapentake
A wapentake was the equivalent of the Anglo-Saxon hundred in the northern Danelaw. In the Domesday Book, the term is used instead of hundreds in Yorkshire, the Five Boroughs of Derby, Leicester, Lincoln, Nottingham and Stamford, and also sometimes in Northamptonshire. The laws in wapentakes were similar to those in hundreds with minor variations. According to the first-century historian Tacitus, in Scandinavia the wapentake referred to a vote passed at an assembly by the brandishing of weapons. In some counties, such as Leicestershire, the wapentakes recorded at the time of Domesday Book later evolved into hundreds. In others, such as Lincolnshire, the term remained in use.

Although no longer part of local government, there is some correspondence between the rural deanery and the former wapentake or hundred; especially in the East Midlands, the Buckingham Archdeaconry and the York Diocese.

Ward
The term ward is a corresponding county division in the four northern counties of Cumberland, Durham, Northumberland and Westmorland.

Ireland
Irish counties were divided into cantreds after the Norman conquest and baronies after the Tudor reconquest

Wales
In Wales an ancient Celtic system of division called cantrefi (a hundred farmsteads; singular cantref) had existed for centuries and was of particular importance in the administration of the Welsh law. The antiquity of the cantrefi is demonstrated by the fact that they often mark the boundary between dialects. Some were originally kingdoms in their own right; others may have been artificial units created later. With the coming of Christianity, the llan (similar to the parish) based Celtic churches often took the borders of the older cantrefi, and the same happened when Norman 'hundreds' were enforced on the people of Wales.

Each cantref had its own court, which was an assembly of the uchelwyr, the main landowners of the cantref. This would be presided over by the king if he happened to be present, or if he was not present, by his representative. Apart from the judges there would be a clerk, an usher and sometimes two professional pleaders. The cantref court dealt with crimes, the determination of boundaries, and inheritance.

Nordic countries

The term hundare (hundred) was used in Svealand and present-day Finland. The name is assumed to mean an area that should organise 100 men to crew four rowed war boats, which each had 12 pairs of oars and a commander.

Eventually, that division was superseded by introducing the härad or Herred, which was the term in the rest of the Nordic countries. This word was either derived from Proto-Norse *harja-raiðō (warband) or Proto-Germanic *harja-raiða (war equipment, cf. wapentake). Similar to skipreide, a part of the coast where the inhabitants were responsible for equipping and manning a war ship.

Hundreds were not organized in Norrland, the northern sparsely populated part of Sweden. In Sweden, a countryside härad was typically divided in a few socken units (parish), where the ecclesiastical and worldly administrative units often coincided. This began losing its basic significance through the municipal reform of 1862. A härad was originally a subdivision of a landskap (province), but since the government reform of 1634, län ("county") took over all administrative roles of the province. A härad functioned also as electoral district for one peasant representative during the Riksdag of the Estates (Swedish parliament 1436–1866). The häradsrätt (assize court) was the court of first instance in the countryside, abolished in 1971 and superseded by tingsrätt (modern district courts).

Today, the hundreds serve no administrative role in Sweden, although some judicial district courts still bear the name (e.g. Attunda tingsrätt) and the hundreds are occasionally used in expressions, e.g. Sjuhäradsbygden (district of seven hundreds).

It is not entirely clear when hundreds were organised in the western part of Finland. The name of the province of Satakunta, roughly meaning hundred (sata meaning "one hundred" in Finnish), hints at influences from the times before the Northern Crusades, Christianization, and incorporation into Sweden.

As kihlakunta, hundreds remained the fundamental administrative division for the state authorities until 2009. Each was subordinated to a lääni (province/county) and had its own police department, district court and prosecutors. Typically, cities would comprise an urban kihlakunta by themselves, but several rural municipalities would belong to a rural kihlakunta. In a rural hundred the lensmann (chief of local state authorities) was called nimismies ("appointed man"), or archaically vallesmanni (from Swedish). In the Swedish era (up to 1809), his main responsibilities were maintenance of stagecoach stations and coaching inns, supplying traveling government personnel with food and lodging, transport of criminal prisoners, police responsibilities, arranging district court proceedings (tingsrätt), collection of taxes, and sometimes arranging hunts to cull the wolf and bear population. Following the abolition of the provinces as an administrative unit in 2009, the territory for each authority could be demarcated separately, i.e. police districts need not equal court districts in number. The title "härad" survives in the honorary title of herastuomari (Finnish) or häradsdomare (Swedish), which can be given to lay judges after 8–10 years of service.

The term herred or herad was used in Norway between 1863 and 1992 for rural municipalities, besides the term kommune (heradskommune). Today, only four municipalities in western Norway call themselves herad, as Ulvik and Kvam. Some Norwegian districts have the word herad in their name, of historical reasons - among them Krødsherad and Heradsbygd in eastern Norway.

Ukraine
In 17th and 18th century, "sotnia" was an administrative-territorial, judicial, and military unit of a "polk" (Regiment) in the Hetmanate and Sloboda Ukraine. The Encyclopedia of Ukraine translates the term as "company".

United States
Counties in Delaware, New Jersey and Pennsylvania were divided into hundreds in the 17th century, following the English practice familiar to the colonists. They survive in Delaware (see List of hundreds of Delaware), and were used as tax reporting and voting districts until the 1960s, but now serve no administrative role: their only official legal use is in real estate title descriptions.

The hundred was also used as a division of the county in Maryland. Carroll County, Maryland was formed in 1836 by taking the following hundreds from Baltimore County: North Hundred, Pipe Creek Hundred, Delaware Upper Hundred, Delaware Lower Hundred; and from Frederick County: Pipe Creek Hundred, Westminster Hundred, Unity Hundred, Burnt House Hundred, Piney Creek Hundred, and Taneytown Hundred. Maryland's Somerset County, which was established in 1666, was initially divided into six hundreds: Mattapony, Pocomoke, Boquetenorton, Wicomico, and Baltimore Hundreds; later subdivisions of the hundreds added five more: Pitts Creek, Acquango, Queponco, Buckingham, and Worcester Hundreds.

The original borders of Talbot County (founded at some point prior to 12 February 1661 ) contained nine hundreds: Treadhaven Hundred, Bolenbroke Hundred, Mill Hundred, Tuckahoe Hundred, Worrell Hundred, Bay Hundred, Island Hundred, Lower Kent Island Hundred, Chester Hundred. In 1669 Chester Hundred was given to Kent County. In 1707 Queen Anne's County was created from the northern parts of Talbot County, reducing the latter to seven hundreds (Lower Kent Island Hundred becoming a part of the former). Of these, only Bay Hundred legally remains in existence, as a District 5 in Talbot County. The geographic region, which includes several unincorporated communities and part of present-day Saint Michaels, continues to be known by the name Bay Hundred, with state and local governments using the name in ways ranging from water trail guides to community pools, while local newspapers regularly use the name in reporting news.

Following American independence, the term "hundred" fell out of favour and was replaced by "election district". However, the names of the old hundreds continue to show up in deeds for another 50 years.

Some plantations in early colonial Virginia used the term hundred in their names, such as Martin's Hundred, Flowerdew Hundred, and West and Shirley Hundred. Bermuda Hundred was the first incorporated town in the English colony of Virginia. It was founded by Sir Thomas Dale in 1613, six years after Jamestown.

While debating what became the Land Ordinance of 1785, Thomas Jefferson's committee wanted to divide the public lands in the west into "hundreds of ten geographical miles square, each mile containing 6086 and 4-10ths of a foot". The legislation instead introduced the six-mile square township of the Public Land Survey System.

Australia
In South Australia, land titles record in which hundred a parcel of land is located. Similar to the notion of the South Australian counties listed on the system of titles, hundreds are not generally used when referring to a district and are little known by the general population, except when transferring land title. When the land in the region of the present Darwin, in the Northern Territory, was first surveyed, the territory was administered by South Australia, and the surveyed land was divided up into hundreds. The Cumberland County (Sydney) was also allocated hundreds in the nineteenth century, although these were later repealed. A hundred is traditionally one hundred square miles or 64000 acres, although this is often not exact as boundaries often follow local topography.

title: Hundred (county division)