[Tex/LaTex] Mathematical description of TeX’s infinite numbers


TeX has things like infinitely stretchable spaces and infinitely bad penalties. Since Knuth is Knuth, I assume these are a carefully thought-out implementation of some well defined non-Archimedean number system, and that that he had good reasons for picking that particular number system over some other system (e.g. some richer or weaker system).

What number system is it? Does it have a hierarchy of infinities? Does it have invertible infinities, like in the Levi-Civita field?

Best Answer

TeX's glue dimensions, including the infinite dimensions fil, fill, and filll, lack the following structure/properties:

  • Cancellation: since 1pt + 1fil = 1fil according to the rules, glue is not even an additive group. You can of course write 1pt plus 1fil, but that means something entirely different, as Heiko explains.

  • Multiplication: you cannot multiply glue by other glue. Well, you can down-convert a skip into a dimen and, interpreted as a multiple of 1sp, you can multiply another skip (glue) by that integer. Under this interpretation, by the way, 1fil = 0, since an infinite stretch is impossible in the base value of glue, which is what is converted.

I don't know of any mathematical structure including "infinities" that lacks cancellation but allows real numbers as values. For example, hyperreal numbers have infinite quantities but 1 + \omega \neq \omega. Ordinals are closer, but addition is not commutative (though we do have 1 + \omega = \omega), and in the version that is commutative (natural addition) we have 1 + \omega \neq \omega.

One system of, er, quantities that I hesitate to call a structure is the catalog of asymptotics given by big-O notation. It appears that Knuth's glue does adhere to the first four levels of the polynomial hierarchy: pt = O(1), fil = O(n), fill = O(n^2), and filll = O(n^3). We keep track of the multipliers but not of lower-order terms when adding. Under this identification we would have fil * fill = filll, or at least is O(filll), but that and fil^2 are the only products we could take, so it hardly seems worth it.

This is probably the most likely, given Knuth's fame as the pioneer of analysis of algorithms, but I wouldn't overthink it even so. He clearly implemented the grade-school arithmetic of infinity: you know, "infinity = infinity plus one" and "infinity squared > infinity", which are endlessly debated in third-grade cafeterias.

Related Question