Dickson's lemma

In mathematics, Dickson's lemma states that every set of $n$ -tuples of natural numbers has finitely many minimal elements. This simple fact from combinatorics has become attributed to the American algebraist L. E. Dickson, who used it to prove a result in number theory about perfect numbers.^[1] However, the lemma was certainly known earlier, for example to Paul Gordan in his research on invariant theory.^[2]

Example

Let $K$ be a fixed natural number, and let $S=\{(x,y)\mid xy\geq K\}$ be the set of pairs of numbers whose product is at least $K$ . When defined over the positive real numbers, $S$ has infinitely many minimal elements of the form $(x,K/x)$ , one for each positive number $x$ ; this set of points forms one of the branches of a hyperbola. The pairs on this hyperbola are minimal, because it is not possible for a different pair that belongs to $S$ to be less than or equal to $(x,K/x)$ in both of its coordinates. However, Dickson's lemma concerns only tuples of natural numbers, and over the natural numbers there are only finitely many minimal pairs. Every minimal pair $(x,y)$ of natural numbers has $x\leq K$ and $y\leq K$ , for if x were greater than K then (x − 1, y) would also belong to S, contradicting the minimality of (x, y), and symmetrically if y were greater than K then (x, y − 1) would also belong to S. Therefore, over the natural numbers, $S$ has at most $K^{2}$ minimal elements, a finite number.^{[note 1]}

Formal statement

Let $\mathbb {N}$ be the set of non-negative integers (natural numbers), let n be any fixed constant, and let $\mathbb {N} ^{n}$ be the set of $n$ -tuples of natural numbers. These tuples may be given a pointwise partial order, the product order, in which $(a_{1},a_{2},\dots ,a_{n})\leq (b_{1},b_{2},\dots b_{n})$ if and only if $a_{i}\leq b_{i}$ for every $i$ . The set of tuples that are greater than or equal to some particular tuple $(a_{1},a_{2},\dots ,a_{n})$ forms a positive orthant with its apex at the given tuple.

With this notation, Dickson's lemma may be stated in several equivalent forms:

In every non-empty subset $S$ of $\mathbb {N} ^{n}$ there is at least one but no more than a finite number of elements that are minimal elements of $S$ for the pointwise partial order.^[3]
For every infinite sequence $(x_{i})_{i\in \mathbb {N} }$ of $n$ -tuples of natural numbers, there exist two indices $i<j$ such that $x_{i}\leq x_{j}$ holds with respect to the pointwise order.^[4]
The partially ordered set $(\mathbb {N} ^{n},\leq )$ does not contain infinite antichains nor infinite (strictly) descending sequences of $n$ -tuples.^[4]
The partially ordered set $(\mathbb {N} ^{n},\leq )$ is a well partial order.^[5]
Every subset $S$ of $\mathbb {N} ^{n}$ may be covered by a finite set of positive orthants, whose apexes all belong to $S$ .

Generalizations and applications

Dickson used his lemma to prove that, for any given number $n$ , there can exist only a finite number of odd perfect numbers that have at most $n$ prime factors.^[1] However, it remains open whether there exist any odd perfect numbers at all.

The divisibility relation among the P-smooth numbers, natural numbers whose prime factors all belong to the finite set P, gives these numbers the structure of a partially ordered set isomorphic to $(\mathbb {N} ^{|P|},\leq )$ . Thus, for any set S of P-smooth numbers, there is a finite subset of S such that every element of S is divisible by one of the numbers in this subset. This fact has been used, for instance, to show that there exists an algorithm for classifying the winning and losing moves from the initial position in the game of Sylver coinage, even though the algorithm itself remains unknown.^[6]

The tuples $(a_{1},a_{2},\dots ,a_{n})$ in $\mathbb {N} ^{n}$ correspond one-for-one with the monomials $x_{1}^{a_{1}}x_{2}^{a_{2}}\dots x_{n}^{a_{n}}$ over a set of $n$ variables $x_{1},x_{2},\dots x_{n}$ . Under this correspondence, Dickson's lemma may be seen as a special case of Hilbert's basis theorem stating that every polynomial ideal has a finite basis, for the ideals generated by monomials. Indeed, Paul Gordan used this restatement of Dickson's lemma in 1899 as part of a proof of Hilbert's basis theorem.^[2]

Notes

^ With more care, it is possible to show that one of $x$ and $y$ is at most ${\sqrt {K}}$ , and that there is at most one minimal pair for each choice of one of the coordinates, from which it follows that there are at most $2{\sqrt {K}}$ minimal elements.

References

^ ^a ^b Dickson, L. E. (1913), "Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors", American Journal of Mathematics, 35 (4): 413–422, doi:10.2307/2370405, JSTOR 2370405.
^ ^a ^b Buchberger, Bruno; Winkler, Franz (1998), Gröbner Bases and Applications, London Mathematical Society Lecture Note Series, vol. 251, Cambridge University Press, p. 83, ISBN 9780521632980.
^ Kruskal, Joseph B. (1972). "The theory of well-quasi-ordering: A frequently discovered concept". Journal of Combinatorial Theory. Series A. 13 (3): 298. doi:10.1016/0097-3165(72)90063-5.
^ ^a ^b Figueira, Diego; Figueira, Santiago; Schmitz, Sylvain; Schnoebelen, Philippe (2011), "Ackermannian and primitive-recursive bounds with Dickson's lemma", 26th Annual IEEE Symposium on Logic in Computer Science (LICS 2011), IEEE Computer Soc., Los Alamitos, CA, p. 269, arXiv:1007.2989, doi:10.1109/LICS.2011.39, ISBN 978-1-4577-0451-2, MR 2858898, S2CID 9178090.
^ Onn, Shmuel (2008), "Convex Discrete Optimization", in Floudas, Christodoulos A.; Pardalos, Panos M. (eds.), Encyclopedia of Optimization, Vol. 1 (2nd ed.), Springer, pp. 513–550, arXiv:math/0703575, Bibcode:2007math......3575O, ISBN 9780387747583.
^ Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (2003), "18 The Emperor and his Money", Winning Ways for your Mathematical Plays, Vol. 3, Academic Press, pp. 609–640. See especially "Are outcomes computable", p. 630.

[3] With more care, it is possible to show that one of $x$ and $y$ is at most ${\sqrt {K}}$ , and that there is at most one minimal pair for each choice of one of the coordinates, from which it follows that there are at most $2{\sqrt {K}}$ minimal elements.

[dickson-1] Dickson, L. E. (1913), "Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors", American Journal of Mathematics, 35 (4): 413–422, doi:10.2307/2370405, JSTOR 2370405.

[buchberger-2] Buchberger, Bruno; Winkler, Franz (1998), Gröbner Bases and Applications, London Mathematical Society Lecture Note Series, vol. 251, Cambridge University Press, p. 83, ISBN 9780521632980.

[kruskal-4] Kruskal, Joseph B. (1972). "The theory of well-quasi-ordering: A frequently discovered concept". Journal of Combinatorial Theory. Series A. 13 (3): 298. doi:10.1016/0097-3165(72)90063-5.

[ffss-5] Figueira, Diego; Figueira, Santiago; Schmitz, Sylvain; Schnoebelen, Philippe (2011), "Ackermannian and primitive-recursive bounds with Dickson's lemma", 26th Annual IEEE Symposium on Logic in Computer Science (LICS 2011), IEEE Computer Soc., Los Alamitos, CA, p. 269, arXiv:1007.2989, doi:10.1109/LICS.2011.39, ISBN 978-1-4577-0451-2, MR 2858898, S2CID 9178090.

[6] Onn, Shmuel (2008), "Convex Discrete Optimization", in Floudas, Christodoulos A.; Pardalos, Panos M. (eds.), Encyclopedia of Optimization, Vol. 1 (2nd ed.), Springer, pp. 513–550, arXiv:math/0703575, Bibcode:2007math......3575O, ISBN 9780387747583.

[7] Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (2003), "18 The Emperor and his Money", Winning Ways for your Mathematical Plays, Vol. 3, Academic Press, pp. 609–640. See especially "Are outcomes computable", p. 630.

[1]

[2]

[note 1]

[3]

[4]

[5]

[6]

Example

Formal statement

Generalizations and applications

See also

Notes

References