Theory and Applications of Categories, Vol. 12, No. 8, 2004, pp. 262–269.

ON SUBGROUPS OF THE LAMBEK PREGROUP

MICHAEL BARR

Abstract. A pregroup is a partially ordered monoid in which every element has a left and a right adjoint. The main result is that for some well-behaved subgroups of the group of diffeomorphisms of the real numbers, the set of all endofunctions of the integers that are asymptotic at ±∞ to (the restriction to the integers of) a function in the subgroup is a pregroup.

1. Introduction

In [Lambek, 2004], Lambek has described a new kind of not quite algebraic structure. A pregroup is a partially ordered monoid in which multiplication by every element has a left and right adjoint. More precisely, a poset P that is also a monoid and such that for each element x ∈ P there are elements x^{ℓ}, x^{r} ∈ P such that

x^{ℓ}x ≤ 1 ≤ xx^{ℓ} and xx^{r} ≤ x^{r}x

It is easy to see that the underlying functor from pregroups to posets has a left adjoint and is, in fact, tripleable. Thus there is one ready source of pregroups: the free ones generated by a poset.

In addition to the free pregroups (and of course, the groups with the discrete partial order), there are very few known examples. The best known is what we will call the Lambek pregroup after its discoverer. This is the set of all functions Z → Z that are unbounded in both directions, under composition. We will denote this pregroup by L.

If you try to analyze why this works in order to find other examples of the same sort, you appear to hit a blank wall. The problem is not only showing that every function has a left and right adjoint, but also showing that the adjoints have the same properties. Having a right and left adjoint means preserving all infs and sups. In Z only finite non-empty sets have infs and sups and they are in the set and so preserved by every functor. Only a total order in which every bounded set is finite can have that property. For a bounded function (in either direction) some of the infs and sups required for the adjoint will be empty and that does not work. If you had a first (or last element) then it would have to be preserved and there is no way of forcing the adjoint to preserve them. So you need a total order without first or last element in which every bounded set is finite. These properties are easily seen to characterize Z as an ordered set.

This research was supported by the NSERC of Canada

Received by the editors 2004-04-09 and, in revised form, 2004-04-10.

Transmitted by Robert Rosebrugh. Published on 2004-04-12.

2000 Mathematics Subject Classification: 91F20, 18B35.

Key words and phrases: subpregroups of the Lambek pregroup.

\begin{matrix}c \\ ◯ \end{matrix} Michael Barr, 2004. Permission to copy for private use granted.

Since there is no obvious way to generalize the construction of L, we turn instead to finding sub-pregroups of L. One source of functions in L is to take an increasing bijection ϕ : R → R and define f(n) = ⌊ϕ(n)⌋ (this is the floor, or greatest integer, function). In fact, we will see that every element of L has that form and we can even take ϕ to be differentiable. Thus one way to explore sub-pregroups of L is to look at subgroups of the group G of increasing diffeomorphisms of R. Not every subgroup will do; it is necessary to impose a condition that the functions grow at a moderate rate. Exponentials grow too fast and logarithms too slowly, but, for example, polynomials are, like mama bears, just right.

In this paper, we will be comparing the behavior of functions at ±∞. In particular, we will write ϕ ∼ ψ if

lim_{x→ ±∞} \frac{ϕ(x)}{ψ(x)} = 1

For the most part, we will study this only at +∞, since the transformation ϕ ↦ ϕ^{∗} defined by ϕ^{∗}(x) = −ϕ(−x) changes the behavior at −∞ to that at +∞.

I would like to thank the referee for suggesting several improvements in the paper and for saving from making an embarrassing error in the proof of Theorem 3.2.

An extended abstract announcing these results appeared in [Barr, 2004].

2. Preliminary results

In this paper, we will be dealing with functions Z → Z, which we will denote by small Roman letters, such as f and functions R → R that we will denote by small Greek letters, such as ϕ. Unless explicitly mentioned otherwise, the graphs of the real valued functions will be assumed to have tangents everywhere, although they might be vertical. As an example of the latter, for any positive real a, we let ()^{(a)} denote the symmetric ath power function defined by

x^{(a)} = \{ \begin{matrix}x^{a} & if x ≥ 0 \\ −(−x)^{a} & if x < 0 \end{matrix}

which has a vertical tangent at 0 when a < 1.

If x ∈ R, we define, as usual, the floor of x, denoted ⌊x⌋ to be the largest integer not larger than x and the ceiling of x, denoted ⌈x⌉ as the smallest integer not smaller than x. If ϕ : R → R is a function, we let ⌊ϕ⌋ : Z → Z denote the function such that ⌊ϕ⌋(n) = ⌊ϕ(n)⌋. We define ⌈ϕ⌉ similarly.

We let G denote the group of functions R → R that are increasing homomeorphisms that have a tangent everywhere (possibly vertical) and whose inverse does too. If ϕ, ψ ∈ G, we will say that ϕ ∼ ψ if lim_{x→ +∞} ϕ(x)/ψ(x) = lim_{x→ −∞} ϕ(x)/ψ(x) = 1.

Let L denote the Lambek pregroup of unbounded increasing functions Z → Z. If f, g ∈ L, we say that f ∼ g if lim_{n→ +∞} f(n)/g(n) = lim_{n→ −∞} f(n)/g(n) = 1. We will also say that if f ∈ L and ϕ ∈ G, then f ∼ ϕ if f ∼ ⌊ϕ⌋. Since ϕ(x) → ∞ as x does, it is obvious that this is the same as f ∼ ⌈ϕ⌉.

2.1. Proposition. Every f ∈ L has the form ⌊ϕ⌋ for some ϕ ∈ G.

Proof. If n is an integer, suppose that k is the least integer such that f(n) < f(n + k). If k = 1, then for x ∈ [n, n + 1], define ψ(x) = (f(n) + .3)(n + 1 − x) + (f(n + 1) + .3)(x − n). Otherwise, for x ∈ [n, n + k], define

ψ(x) = \frac{(f(n)(n + k − 1 − x) + .3) + (f(n) + .7)(x − n)}{k − 1}

for x ≤ k − 1 and,

ψ(x) = (f(n) + .7)(n + k − x) + (f(n + k) + .3)(x − n − k + 1)

for x ≥ k − 1. What this function does is interpolate linearly between the points (n, f(n)) and (n + k − 1, f(n) + .7) and then between the latter point and (n + k, f(n + k)).

To this point we have constructed a continuous, but not differentiable, function whose integer part at integers is f. It has the additional property that at integers its value differs from the nearest integer by at least .3 and that it is linear between any integer and the next. Now suppose n is an integer and that the slope of ψ before n is m_{1} and after n is m_{2}. Since m_{1} and m_{2} are positive, there is for any ϵ > 0 a smooth spline function in the interval [n − ϵ, n + ϵ] whose values and slopes at n − ϵ and n + ϵ are the same as those of ψ and whose slope in the entire interval is between m_{1} and m_{2}. It follows that such a function remains monotonically increasing. Moreover, if ϵ is chosen sufficiently small, the value at n will differ from ψ(n) by less than .3. Thus the function ϕ can be gotten by replacing all the corners by appropriately chosen splines. For technical reasons, we will always take ϵ ≤ .1.

3. Modest functions

We say that a function ϕ ∈ G is modest if whenever ψ, ρ ∈ G are such that ψ ∼ ρ, then ϕψ ∼ ϕρ.

3.1. Proposition. If ϕ, θ ∈ G are modest, so is ϕ θ.

I would like to thank G.A. Edgar for the elegant proof of the following theorem that replaces my original, much longer, argument.

3.2. Theorem. If ϕ ∈ G is a function for which xϕ′(x)/ϕ(x) is bounded outside a bounded set, then ϕ is modest.

Proof. We consider the situation only at +∞; the transformation ϕ ↦ ϕ^{∗} (which leaves xϕ′(x)/ϕ(x) invariant) takes care of the case at −∞. Since all the functions considered go to ∞ as x does, they are eventually positive. Thus, given ψ and ρ, there is some bounded interval outside of which xϕ′(x)/ϕ(x) is bounded and ψ and ρ are positive. Let σ(x) = log(ψ(x)) and τ(x) = log(ρ(x)). Then lim_{x→ ∞} σ(x) − τ(x) = 0. If we define ϕ̂ by ϕ̂(x) = log(ϕ(exp(x))), we have that

ϕ̂′(x) = \frac{exp(x)ϕ′(exp(x))}{ϕ(exp(x))}

which, if we let y = exp(x), gives

ϕ̂′(x) = \frac{yϕ′(y)}{ϕ(y)}

so that our hypothesis implies that ϕ̂′(x) is bounded. But there is some u between σ(x) and τ(x) for which

ϕ̂(σ(x)) − ϕ̂(τ(x)) = ϕ̂′(u)(σ(x) − τ(x))

Since σ(x) and τ(x) go to infinity when x does, we are eventually in the range where ϕ′(u) is bounded and then it follows that

lim_{x→ ∞} ϕ̂(σ(x)) − ϕ̂(τ(x)) = 0

Take exponentials and replace σ and τ by their definitions to get,

lim_{x→ ∞} \frac{ϕ(ψ(x))}{ϕ(ρ(x))} = 1

3.3. Proposition. Suppose ψ = ϕ^{−1}. Then for u = ψ(x), we have

\frac{xψ′(x)}{ψ(x)} = (\frac{uϕ′(u)}{ϕ(u)})^{−1}

Proof. By differentiating ϕ(ψ(x)) = x, we get that ϕ′(ψ(x))ψ′(x) = 1 or ψ′(x) = 1/ϕ′(ψ(x)). This gives

\frac{ψ′(x)x}{ψ(x)} = \frac{x}{ψ(x)ϕ′(ψ(x))} = \frac{ϕ(ψ(x))}{ψ(x)ϕ′(ψ(x))}

If we now let u = ψ(x), this becomes

\frac{xψ′(x)}{ψ(x)} = \frac{ϕ(u)}{uϕ′(u)}

3.4. Corollary. For ϕ ∈ G, a sufficient condition that both ϕ and ϕ^{−1} be modest is that xϕ′(x)/ϕ(x) be both bounded and bounded away from 0 outside a bounded set.

3.5. Proposition. If ϕ, ψ ∈ G and ϕ is modest, so is ψ.

Proof. Suppose σ ∼ τ. The conclusion can be read off from

\frac{ψσ(x)}{ψτ(x)} = \frac{ψσ(x)}{ϕσ(x)} \frac{ϕσ(x)}{ϕτ(x)} \frac{ϕτ(x)}{ψτ(x)}

3.6. Proposition. Suppose ϕ, ψ ∈ G are such that ϕ ∼ ψ. If ϕ^{−1} is modest, then ϕ^{−1} ∼ ψ^{−1} (and ψ^{−1} is modest).

Proof. Since ψ(x) goes to ∞ when x does, it is sufficient to show that

lim_{x→ ∞} \frac{ϕ^{−1}(ψ(x))}{ψ^{−1}(ψ(x))} = 1

This is the same as

lim_{x→ ∞} \frac{ϕ^{−1}(ψ(x))}{ϕ^{−1}(ϕ(x))} = 1

and the conclusion follows from the modesty of ϕ^{−1}.

Some hypothesis on the growth of ϕ^{−1} is required. If ϕ(x) is any function in G that is log x for x ≥ e and − log(−x) for x ≤ −e, while ψ(x) = 1 + ϕ(x), then ϕ ∼ ψ, while ϕ^{−1} ≁ ψ^{−1}.

4. The main theorem

4.1. Proposition. Suppose that f ∈ L and ϕ, ψ ∈ G. If ϕ and ψ are modest, f = ⌊ϕ⌋, and f ∼ ψ then ϕ ∼ ψ.

Proof. The conditions imply that for n = ⌊x⌋

\frac{ψ(x)}{ϕ(x)} = \frac{ψ(x)}{ψ(n)} \frac{ψ(n)}{f(n)} \frac{f(n)}{ϕ(n)} \frac{ϕ(n)}{ϕ(x)}

all four factors of which go to 1 as x → ∞.

4.2. Proposition. Suppose that f ∈ L and ϕ ∈ G such that f ∼ ϕ. If ϕ^{−1} is modest, then f^{ℓ} ∼ ϕ^{−1} ∼ f^{r}.

Proof. Let ψ ∈ G be such that f = ⌊ψ⌋. By perturbing it slightly, we can suppose that ψ(n) is never an integer when n is. This point is not crucial, but it will simplify things. We have ψ ∼ f ∼ ϕ. Then f^{ℓ}(n) ≤ m if and only if n ≤ f(m) if and only if n ≤ ⌊ψ(m)⌋ if and only if n ≤ ψ(m) if and only if ψ^{−1}(n) ≤ m if and only if ⌈ψ^{−1}(n)⌉ ≤ m. Thus f^{ℓ} = ⌈ψ^{−1}⌉. It follows from Propositions 3.5 and 3.6 that f^{ℓ} = ⌈ψ^{−1}⌉ ∼ ψ^{−1} ∼ ϕ^{−1}. As for f^{r}, just modify our previous constructions to choose ψ so that f = ⌈ψ⌉ and reverse all the inequalities.

4.3. Proposition. Suppose that f, g ∈ L and ϕ, ψ ∈ G are such that f ∼ ϕ and g ∼ ψ. If ϕ is modest, then fg ∼ ϕψ.

Proof. We have

\frac{f(g(n))}{ϕ(ψ(n))} = \frac{f(g(n))}{ϕ(g(n))} \frac{ϕ(g(n))}{ϕ(ψ(n))}

The first term goes to 1 as n → ∞ since ψ grows to infinity. As for the second, just use the same argument as in the proof of Theorem 3.2: Since lim log g(n) − log ψ(n) = 0, it follows that lim ϕ̂(log g(n)) − lim ϕ̂(log ψ(n)) = 0 and then that

lim \frac{ϕ(g(n))}{ϕ(ψ(n))} = 1

By iterating this, we see that all of f^{ℓℓ}, f^{ℓℓℓℓ}, …, f^{rr}, f^{rrrr} are asymptotic to ϕ and all the odd adjoints are asymptotic to ϕ^{−1}. Thus we have,

4.4. Theorem. Suppose that H is a subgroup of G such that every element of H is modest. Then the subset of L consisting of those functions that are asymptotic to an element of H is a subpregroup of L.

If the subgroup H of G is generated by functions ϕ all of which satisfy that xϕ′(x)/ϕ(x) are both bounded and bounded away from 0, then every element of H is modest. For example, the subgroup generated by a symmetric ath power has that property. If we take a set A of such symmetric power functions, the subgroup of G they generate is all the symmetric power functions for which the exponent lies in the multiplicative subgroup of positive reals generated by A (which is dense unless the subgroup is actually cyclic). One can modify this example by taking x^{a} for x ≥ 0 and −(−x)^{b} when x < 0. This will fail to be differentiable at 0 if a and b are different sides of 1, but one can readily smooth that out without changing the behaviour at infinity.

For another example, take the function that for positive x is x^{a} log x and the symmetric function for negative x. Examples of this sort are easily created and we will refrain from describing more.

5. Modesty in L

For f ∈ L, let f′(n) = f(n + 1) − f(n).

5.1. Theorem. Suppose that f ∈ L is such that |nf′(n)/f(n)| is bounded. Then there is a modest function ϕ ∈ G such that f = ⌊ϕ⌋.

Proof. We carry out the argument at +∞; the argument at −∞ is similar. Let B be a bound on |nf′(n)/f(n)|. Begin with a piecewise linear automorphism ψ such that f = ⌊ψ⌋. We can suppose that ψ is chosen so that whenever f(n) = f(n + 1), the slope of ψ in the interval (n, n + 1) is at most Bf(n)/(n + 1) and when f(n) < f(n + 1), then ψ′(x) < 2f′(n) in that interval. Then ϕ is constructed from ψ by using Bezier splines at the corners to smooth things. It is clear that for any x ∈ [n, n + 1], the slope of ϕ will be between that of ψ in the interval in question and the two adjacent ones. Thus the slope of ϕ at a point x ∈ [n, n + 1] is does not exceed the maximum of the following quantities:

\frac{Bf(n − 1)}{n}, \frac{Bf(n)}{n + 1}, \frac{Bf(n + 1)}{n + 2}, 2f′(n − 1), 2f′(n), 2f′(n + 1)

We claim that each of these is less than 4Bf(n)/(n+1) for all sufficiently large n. For the first three, it is sufficient to show that f(n + 1)/n < 4f(n)/(n + 1) for sufficiently large n. We have that

\frac{f(n + 1)}{f(n)} − 1 = \frac{f(n + 1) − f(n)}{f(n)} = \frac{f′(n)}{f(n)} ≤ \frac{B}{n}

which implies that

\frac{f(n + 1)}{f(n)} ≤ 1 + \frac{B}{n} or f(n + 1) ≤ (1 + \frac{B}{n} ) f(n)

This gives that

\frac{f(n + 1)}{n} ≤ (1 + \frac{B}{n} ) \frac{n + 1}{n} \frac{f(n)}{n + 1}

and it is clear that

(1 + \frac{B}{n} ) \frac{n + 1}{n} < 4

for sufficiently large n. The other three quantities have to be handled individually because f′ is not necessarily monotone. From

\frac{(n + 1)f′(n − 1)}{f(n)} ≤ \frac{n + 1}{n − 1} \frac{(n − 1)f′(n − 1)}{f(n − 1)} < 2B

for n ≥ 3, it follows that 2f′(n − 1) ≤ 4Bf(n)/(n + 1). For the second term it suffices to observe that n + 1 ≤ 2n for all n ≥ 1. For the third, it follows from

\frac{(n + 1)f′(n + 1)}{f(n)} = \frac{(n + 1)f′(n + 1)}{f(n + 1)} \frac{f(n + 1)}{f(n)} ≤ B (1 + \frac{B}{n} ) ≤ 2B

for sufficiently large n. This demonstrates that

ϕ′(x) ≤ \frac{4Bf(n)}{n + 1} < \frac{4Bϕ(x)}{x}

which implies that

\frac{xϕ′(x)}{ϕ(x)} ≤ 4B

References

Barr, M. (2004), On subgroups of the Lambek pregroup. In C. Casadio, P.J. Scott, and R.A.G. Seely (eds), Language and Grammar: Studies in Mathematical Linguistics and Natural Language, CSLI Publications.

Lambek, J. (2004), What are pregroups? In C. Casadio, P.J. Scott, and R.A.G. Seely (eds), Language and Grammar: Studies in Mathematical Linguistics and Natural Language, CSLI Publications.

McGill University, Department of Mathematics and Statistics 805 Sherbrooke St. W, Montreal, QC H3A 2K6

Email: barr@barrs.org

This article may be accessed via WWW at http://www.tac.mta.ca/tac/ or by anony-

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/12/8/12-08.{dvi,ps}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods.

Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication.

The method of distribution of the journal is via the Internet tools WWW/ftp. The journal is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive (by e-mail) abstracts of articles as they are published. Full text of published articles is available in .dvi, Postscript and PDF. Details will be e-mailed to new subscribers. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh,

rrosebrugh@mta.ca.

Information for authors. The typesetting language of the journal is TEX, and L^{A}TEX2e is the preferred flavour. TEX source of articles for publication should be submitted by e-mail directly to an appropriate Editor. They are listed below. Please obtain detailed information on submission format and style files from the journal’s WWW server at http://www.tac.mta.ca/tac/. You may also write to tac@mta.ca to receive details by e-mail.

Editorial board.

John Baez, University of California, Riverside: baez@math.ucr.edu Michael Barr, McGill University: barr@barrs.org, Associate Managing Editor Lawrence Breen, Université Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of Wales Bangor: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Palo Alto Research Center: paiva@parc.xerox.com Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, University of Western Sydney: s.lack@uws.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca, Managing Editor Jiri Rosicky, Masaryk University: rosicky@math.muni.cz James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca