# 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?

-
–  Ben Crowell Jun 23 at 15:26
Egreg and Ryan Reich pointed out that it's not associative and not a group. However, if one wishes I think this can be taken as a detail of the implementation rather than as a property of the underlying mathematical structure. After all, floating point multiplication is not associative either. Just as a floating-point number is represented in computer memory with truncation to the $n$ most significant digits, we could think of a glue as being stored with only its most significant part. –  Ben Crowell Jun 23 at 17:58

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.

-
If I do something like \hskip 0pt plus 2fill x \hskip 0pt plus 3fill, then one could argue that tex is dividing one glue by another glue, resulting in a quotient r=2/3, which is then used in positioning the letter x at 1/(1+r) of the way from the right side. Similarly for \hskip 0pt plus 1fill x \hskip 0pt plus 1filll, you could say that the quotient r is infinitesimally small, and then 1/(1+r) only differs infinitesimally from 1. (Internally, I assume r is represented as 1.) –  Ben Crowell Jun 23 at 15:39
\documentclass[a4paper]{amsart}

\newcommand{\numberset}[1]{\mathbf{#1}}
\newcommand{\Z}{\numberset{Z}}

\begin{document}
\title{A mathematical description of \TeX{} glue}
\author{egreg@\TeX.SX}

\maketitle

Let $\Z$ be the additive group of integers. We shall disregard the fact that
\TeX{} can only deal with a finite subset of $\Z$, because this is just
incidental.

Consider the set $\Z^{7}$ and denote the projections on the components
by $n$, $S_1$, $S_2$, $S_3$, $s_1$, $s_2$ and $s_3$ respectively.

The set $G$ of \emph{glues} is defined as the subset of $\Z^{7}$ consisting
of the tuples $x\in\Z^{7}$ such that at most one among $S_1(x)$, $S_2(x)$,
$S_3(x)$ is nonzero and at most one among $s_1(x)$, $s_2(x)$, $s_3(x)$ is
nonzero. An element of $\Z^{7}$ is called a \emph{preglue}.

For $x\in\Z^{7}$, we set
$O(x)= \begin{cases} 0 & \text{if S_1(x)=S_2(x)=S_3(x)=0}\\ 1 & \text{if S_1(x)\ne0, S_2(x)=S_3(x)=0}\\ 2 & \text{if S_2(x)\ne0, S_3(x)=0}\\ 3 & \text{if S_3(x)\ne0} \end{cases}$
and call $O(x)$ the \emph{stretching order} of the glue~$x$. Similarly
$o(x)= \begin{cases} 0 & \text{if s_1(x)=s_2(x)=s_3(x)=0}\\ 1 & \text{if s_1(x)\ne0, s_2(x)=s_3(x)=0}\\ 2 & \text{if s_2(x)\ne0, s_3(x)=0}\\ 3 & \text{if s_3(x)\ne0} \end{cases}$
is the \emph{shrinking order} of the preglue~$x$. We finally define
the function $\gamma\colon\Z^{7}\to G$ by
\begin{enumerate}
\item $n(\gamma(x))=n(x)$;
\item $S_k(\gamma(x))=0$ if $k<O(x)$ or $k>O(x)$ ($k=1,2,3$);
\item $S_k(\gamma(x))=s_k(x)$ if $k=O(x)$ ($k=1,2,3$);
\item $s_k(\gamma(x))=0$ if $k<o(x)$ or $k>o(x)$ ($k=1,2,3$);
\item $s_k(\gamma(x))=s_k(x)$ if $k=o(x)$ ($k=1,2,3$).
\end{enumerate}

We define an operation $\oplus$ on $G$ by defining, for $x,y\in G$,
$x\oplus y=\gamma(x+y)$
where $+$ denotes the componentwise addition in $\Z^{7}$.

The reader should work out the following exercises:
\begin{enumerate}
\item $G$ has a neutral element $0$;
\item for every $x\in G$ there is $y\in G$ such that $x\oplus y=0$;
\item the operation $\oplus$ is commutative;
\item the operation $\oplus$ is not associative.
\end{enumerate}

In spite of the fact that $\oplus$ is not associative, we can define
an action of the integers on $G$; if $a$ is an integer and $x\in G$,
we simply consider $ax$ in the usual sense for the abelian group
$\Z^{7}$, as $\gamma(ax)=ax$.

Final exercise: the set of glues with a fixed stretch order and fixed
shrink order is a group under $\oplus$, isomorphic to $\Z$,
$\Z^{2}$ or $\Z^{3}$.

\end{document}


## Important note

This describes the \advance operation on \skip registers, not what TeX does when it builds a box. For that case the work is different:

When \TeX{} is building a box (vertical or horizontal), it computes
the available natural width, stretching component and shrinking component
by doing
$\gamma(g_1 + g_2 + \dots + g_n)$
not by using the $\oplus$ operation, where $g_1,g_2,\dots,g_n$ are the
available glues in the box.


-
There is also a multiplication (non-commutative). –  Heiko Oberdiek Jun 23 at 10:00
@HeikoOberdiek Are you meaning multiplication by a scalar? –  egreg Jun 23 at 10:23
You can also multiply glues. Then the components of the one glue are multiplied by the projection n of the other glue. –  Heiko Oberdiek Jun 23 at 10:42
@HeikoOberdiek That's a side effect of coercion in TeX's primitive operations. You can also multiply a glue by an arbitrary scalar, but the result is actually a <dimen>. –  egreg Jun 23 at 10:50
@BenCrowell You're right; bad copy-paste-edit. :( –  egreg Jun 23 at 14:37

A glue is a tuple of numbers:

• base value
• shrink component (\glueshrink)
• shrink order (\glueshrinkorder)
• stretch component (\gluestretch)
• stretch order (\gluestretchorder)

The \glue... commands are provided by e-TeX.

TeX stores dimens as numbers with unit sp. Only for printing the value is converted to pt: 1 pt = 216 sp = 65536 sp.

The base value and the shrink and stretch components are stored as dimens.

The order of the shrink and stretch components are encoded as numbers:

• 0 = pt
• 1 = fil
• 2 = fill
• 3 = filll

Example:

\def\msg#{\immediate\write16}
\def\printglue#1{%
\begingroup
\skip0=#1\relax
\msg{skip = \the\skip0}%
\msg{[dimen] \number\skip0 sp = \the\dimexpr\skip0\relax}%
\msg{[minus] \number\glueshrink\skip0 sp = \the\glueshrink\skip0}%
\msg{[minus] order: \the\glueshrinkorder\skip0 \space= %
\printorder{\glueshrinkorder\skip0}}%
\msg{[plus] \space\number\gluestretch\skip0 sp = \the\gluestretch\skip0}%
\msg{[plus] \space order: \the\gluestretchorder\skip0 \space= %
\printorder{\gluestretchorder\skip0}}%
\endgroup
}
\def\printorder#1{%
\ifcase\numexpr(#1)\relax
pt\or fil\or fill\or filll\else unknown\fi
}

\printglue{10pt plus 1.2fill minus 0.7pt}

\csname @@end\endcsname\end


Result:

skip = 10.0pt plus 1.2fill minus 0.7pt
[dimen] 655360sp = 10.0pt
[minus] 45875sp = 0.7pt
[minus] order: 0 = pt
[plus]  78643sp = 1.2pt
[plus]  order: 2 = fill


Thus this value could be considered as tuple of integers: (65536, 45875, 0, 78643, 2).

-
This is helpful, but it doesn't really answer the question. I wasn't asking for a description of the data structure but for a description of the mathematical properties of the data structure, which I imagined might correspond to some previously studied and described mathematical system, such as a certain group or field. Suppose that x=(xc,xo), where xc is the component and xo the order, and similarly y=(yc,yo). Can I form a product xy, e.g., (2fil)(3fil)=(6fill)? Is there a sum, (2fil)+(3fil)=(5fil)? What happens with (2fil)+(3filll)? Is the order limited to 3? –  Ben Crowell Jun 23 at 1:24
TeX doesn't allow such interesting combinations :) The most you can do natively is add or subtract glue. The levels of fil are sort of like infinity: 1fil+1fill=1fill, 1fill+1filll=1filll etc. –  Will Robertson Jun 23 at 5:16