Lattice Paths and Submonoids of $\mathbb Z^2$

Abstract

We study a number of combinatorial and algebraic structures arising from walks on the two-dimensional integer lattice. To a given step set $X\subseteq \mathbb Z^2$, there are two naturally associated monoids: $\mathscr {F}_X$, the monoid of all X-walks/paths; and $\mathscr {A}_X$, the monoid of all endpoints of X-walks starting from the origin O. For each ${A\in \mathscr {A}_X}$, write $\pi _X(A)$ for the number of X-walks from O to A. Calculating the numbers $\pi _X(A)$ is a classical problem, leading to Fibonacci, Catalan, Motzkin, Delannoy and Schröder numbers, among many other well-studied sequences and arrays. Our main results give relationships between finiteness properties of the numbers $\pi _X(A)$, geometrical properties of the step set X, algebraic properties of the monoid $\mathscr {A}_X$, and combinatorial properties of a certain bi-labelled digraph naturally associated to X. There is an intriguing divergence between the cases of finite and infinite step sets, and some constructions rely on highly non-trivial properties of real numbers. We also consider the case of walks constrained to stay within a given region of the plane. Several examples are considered throughout to highlight the sometimes-subtle nature of the theoretical results.

1 Introduction

The study of lattice paths is a cornerstone of enumerative combinatorics, and important applications exist in almost all areas of mathematics. The subject arguably goes back at least to the likes of Fermat and Pascal in the 1600s, and it would be impossible to adequately recount here its fascinating development over the subsequent centuries. Fortunately, we may direct the reader to the survey of Humphreys [15] for an excellent historical treatment, and the recent habilitation thesis of Bostan [3], which contains 397 references. The current authors came to the topic through our interest in diagram semigroups and algebras, where an important role is played by Catalan and Motzkin paths, Riordan arrays, meanders and so on; see for example [6,7,8,9, 12].

Many kinds of lattice path problems have been considered in the literature, but the main ones we are interested in are related to the following questions (formal definitions will be given below):

• Suppose we have a subset X of the two-dimensional integer lattice $\mathbb Z^2$. Starting from some designated origin, which points from $\mathbb Z^2$ can we get to by taking a “walk” using “steps” from X?

• Further, given a point from $\mathbb Z^2$, how many such “X-walks” will take us to this point?

Sometimes constraints are also imposed, so that the X-walks must stay within a specified region of the plane (e.g., the first quadrant). In what follows, the set of all endpoints of (unconstrained) X-walks beginning at the origin $O=(0,0)$ will be denoted $\mathscr {A}_X$; this set is always an additive submonoid of $\mathbb Z^2$. For any point $A\in \mathbb Z^2$, we write $\pi _X(A)$ for the number of X-walks from O to A; this number could be anything from 0 to $\infty$.

Answers to the above questions are well known in many special cases, and lead to well-studied number sequences, triangles and arrays, including Fibonacci, Catalan and Motzkin numbers, as well as binomial and multinomial coefficients. These and many more are discussed in the above-mentioned surveys and references therein, as well as of course the Online Encyclopedia of Integer Sequences [1]. Even for (apparently) simple step sets, solving these problems can be very difficult. As noted in [15], infinite step sets are rarely studied, as are boundaries with irrational slope; both feature strongly in the present work.

The current article takes a somewhat meta-level approach to lattice path problems, and addresses broad questions of the following type: Given a certain property, which step sets X possess that property? The kinds of properties we study include the following:

• the monoid $\mathscr {A}_X$ is a group, or

• $\pi _X(A)$ is finite for all $A\in \mathscr {A}_X$, in which case we say X has the Finite Paths Property (FPP), or

• $\pi _X(A)$ is infinite for all $A\in \mathscr {A}_X$, in which case we say X has the Infinite Paths Property (IPP).

One of our main results, Theorem 2.24, states (among other things) that every finite step set has either the FPP or the IPP, and gives a number of equivalent geometric characterisations of both properties. The situation for infinite step sets is far more complicated, and there is a whole spectrum of interesting intermediate behaviours that can occur; the geometric conditions alluded to just above are no longer equivalent, and there are step sets with neither the FPP nor the IPP. Rather, the geometric conditions and finiteness properties fit together into an “implicational hierarchy” that limits the (ostensibly) possible combinations of these conditions/properties. Characterising the combinations that actually do occur is a major part of the paper, and to achieve this we will need to construct some fairly strange step sets; some of these constructions rely on highly non-trivial properties of real numbers. The paper is organised as follows.

Section 2 concerns unconstrained walks. We begin with the basic definitions in Sect. 2.1, and then introduce the above-mentioned finiteness properties and geometric conditions in Sects. 2.2 and 2.3. We classify the algebraic structure of the monoids arising from step sets of size at most 2 in Sect. 2.4, and then pause to consider a number of infinite step sets that will be used in proofs of later theoretical results. The first main result of the paper (Theorem 2.19) is given in Sect. 2.6; it provides geometric, algebraic and combinatorial characterisations of the IPP, showing among other things that X has the IPP if and only if the origin belongs to ${\text {Conv}}(X)$, the convex hull of X. Section 2.7 contains the above-mentioned implicational hierarchy (Theorem 2.24); this simplifies dramatically in the case of finite step sets, leading in particular to the FPP/IPP dichotomy alluded to above (Corollary 2.25). The main result of Sect. 2.8 (Theorem 2.30) states that the monoid $\mathscr {A}_X$ is a non-trivial group if and only if the origin belongs to the relative interior of ${\text {Conv}}(X)$; a number of other equivalent geometric characterisations are also given (Theorem 2.27). Finally, Sect. 2.9 classifies the combinations of finiteness properties and geometric conditions that can be attained by step sets. The above-mentioned Theorem 2.24 (proved in Sect. 2.7) limits the set of ostensibly possible combinations to ten, and these are enumerated in Table 1. Curiously, we will see that exactly one of these combinations can never occur (Proposition 2.36), but that the nine remaining combinations can; this is shown by constructing step sets with the relevant combinations of properties. Some of these constructions are quite involved. One of them utilises an ingenious argument from Stewart Wilcox, which demonstrates the existence of certain sequences of real numbers; the details are given in Appendix A, which is written jointly with Wilcox.

Section 3 gives a somewhat parallel treatment of walks that are constrained to stay within a specified region of the plane. As well as reducing the number of walks, these contraints also typically limit the extent to which general results can be proved. In Sect. 3.1 we give the basic definitions, and then in Sect. 3.2 prove constrained analogues of many of the results from Sect. 2. Theorem 3.4 is a constrained version of the implicational hierarchy (Theorem 2.24); even in the finite case, the situation is more complicated than for unconstrained walks, as for one thing, the FPP/IPP dichotomy no longer holds. Propositions 3.7 and 3.8 are analogues of the above-mentioned Theorems 2.19 and 2.30, respectively. Finally, Sect. 3.3 explores the natural idea of admissible steps, and shows how these allow for some stronger general results on constrained walks, especially in the case that the bounding region contains a lattice cone (Theorems 3.10 and 3.15).

Numerous examples are given throughout the exposition. Some of these are used to illustrate the underlying ideas; for instance, Examples 2.4 and 3.2(iii) show that interesting finite enumeration can arise from infinite step sets. Other examples are crucial in establishing theoretical results. The properties of these step sets, and the combinatorial data associated to them, are displayed conveniently in certain edge- and vertex-labelled digraphs, defined in Sect. 2.1 and 3.1; see for example Figs. 2, 3, 4 and 13, 14, 15, 16. C++ algorithms can be found at [13], which can be used to generate the LaTeX/TikZ code for producing such diagrams. (A previous version of this paper [10] contains many more examples, and an additional section explaining the algorithms at [13].)

Throughout, we assume familiarity with basic linear algebra, number theory, and plane (convex) geometry and topology. We denote by $\mathbb R$, $\mathbb Q$ and $\mathbb Z$ the sets of reals, rationals and integers; we also write $\mathbb N=\{0,1,2,\ldots \}$ and $\mathbb P=\{1,2,3,\ldots \}$ for the sets of natural numbers and positive integers. We use $\lfloor x\rfloor$ to denote the floor of the real number x: i.e., the greatest integer not exceeding x. For three distinct points $A,B,C\in \mathbb R^2$, we write $\angle ABC$ for the angle between the line segments AB and BC; if not otherwise specified, this will always be the non-reflex angle; we write $\overrightarrow{AB}$ for the displacement vector from A to B.

2 Unconstrained Walks

2.1 Definitions and Basic Examples

We write $\mathbb Z_\times ^2=\mathbb Z^2\setminus \{O\}$, where $O=(0,0)$, and we define a step set to be any subset of $\mathbb Z_\times ^2$. We allow step sets to be finite or (countably) infinite. If $X\subseteq \mathbb Z_\times ^2$ is a step set, then we may consider two natural monoids associated to X. The first is the free monoid on X, which we denote by $\mathscr {F}_X$, and which consists of all words over X under the operation of word concatenation. So elements of $\mathscr {F}_X$ are words of the form $u=A_1\cdots A_k$, where $k\in \mathbb N$ and $A_1,\ldots ,A_k\in X$. The length of the word $u=A_1\cdots A_k$ is defined to be k, and is denoted $\ell (u)$; when $k=0$, we interpret u to be the empty word, which we denote by $\varepsilon$, and which is the identity element of $\mathscr {F}_X$. For reasons that will become clear shortly, we will also refer to the elements of $\mathscr {F}_X$ as X-walks.

The second monoid associated to a step set $X\subseteq \mathbb Z_\times ^2$ is the additive submonoid of $\mathbb Z^2$ generated by X, which we will denote by $\mathscr {A}_X$. So $\mathscr {A}_X$ consists of all points of the form $A=A_1+\cdots +A_k$, where $k\in \mathbb N$ and $A_1,\ldots ,A_k\in X$; when $k=0$, we interpret $A=O=(0,0)$, which is the identity element of $\mathscr {A}_X$.

There is a natural monoid surmorphism (surjective homomorphism)

$$\begin{aligned} \alpha _X:\mathscr {F}_X\rightarrow \mathscr {A}_X \qquad \text {defined by}\qquad \alpha _X(A_1\cdots A_k)=A_1+\cdots +A_k. \end{aligned}$$

In particular, note that $\alpha _X(A)=A$ for all $A\in X$. Consider a word $u=A_1\cdots A_k\in \mathscr {F}_X$, and let $B\in \mathbb Z^2$ be an arbitrary lattice point. Then u determines a walk beginning at B, and ending at $B+\alpha _X(u)$. The letters $A_1,\ldots ,A_k$ determine the steps taken in the walk, and the points visited are:

$$\begin{aligned}&B \ \ \rightarrow \ \ B+A_1 \ \ \rightarrow \ \ B+A_1+A_2 \ \ \rightarrow \ \ \cdots \\&\quad \ \ \rightarrow \ \ B+A_1+A_2+\cdots +A_k = B+\alpha _X(u). \end{aligned}$$

We say that u is an X-walk from B to $B+\alpha _X(u)$. In particular, if $B=O$, then u is an X-walk from O to $\alpha _X(u)$; we say that u is an X-walk to $\alpha _X(u)$.

We illustrate these ideas with (arguably) the most commonly studied step set:

Example 2.1

Consider the step set $X=\{E,N\}$, where $E=(1,0)$ and $N=(0,1)$ represent steps of one unit East and North, respectively. So $\mathscr {A}_X=\{ {aE+bN} : {a,b\in \mathbb N} \}=\{ {(a,b)} : {a,b\in \mathbb N} \}=\mathbb N^2$. Consider the two X-walks $u=EENEN$ and $v=NNEEE$ from $\mathscr {F}_X$. Although $u\not =v$, we note that $\alpha _X(u)=\alpha _X(v)=(3,2)$; see Fig. 1. For any $(a,b)\in \mathbb N^2$, there are $\left( {\begin{array}{c}a+b\\ a\end{array}}\right) =\left( {\begin{array}{c}a+b\\ b\end{array}}\right)$ X-walks to (a, b). In fact, this formula is valid for any $(a,b)\in \mathbb Z^2$, as it is standard to interpret a binomial coefficient $\left( {\begin{array}{c}m\\ k\end{array}}\right) =0$ if $m<k$ or if $k<0$.

Fig. 1

Two X-walks from O to (3, 2), where $X=\{(1,0),(0,1)\}$; cf. Example 2.1

Consider a step set $X\subseteq \mathbb Z_\times ^2$. For lattice points $A,B\in \mathbb Z^2$, we define

$$\begin{aligned} \Pi _X(A,B) = \{ {u\in \mathscr {F}_X} : {A+\alpha _X(u)=B} \} \qquad \text {and}\qquad \pi _X(A,B) = |\Pi _X(A,B)|. \end{aligned}$$

So $\Pi _X(A,B)$ is the (possibly empty) set of all X-walks from A to B, and $\pi _X(A,B)$ is the number of such walks. Note that it is possible to have $\pi _X(A,B)=0$ or $\infty$. Also note that we always have $\pi _X(A,A)\ge 1$ for any $A\in \mathbb Z^2$, since the empty word $\varepsilon$ always belongs to $\Pi _X(A,A)$. It is clear that

$$\begin{aligned} \Pi _X(A+C,B+C)=\Pi _X(A,B) \qquad \text {and}\qquad&\pi _X(A+C,B+C)=\pi _X(A,B)\\&\!\qquad \qquad \quad \text {for any } A,B,C\in \mathbb Z^2. \end{aligned}$$

Consequently, the numbers $\pi _X(A,B)$, $A,B\in \mathbb Z^2$, may all be recovered from the values $\pi _X(O,A)$, $A\in \mathbb Z^2$. Accordingly, for any $A\in \mathbb Z^2$, we define

$$\begin{aligned} \Pi _X(A)=\Pi _X(O,A) \qquad \text {and}\qquad \pi _X(A)=\pi _X(O,A) \end{aligned}$$

to be the set and number of X-walks from O to A, respectively; note that $\Pi _X(A)=\alpha _X^{-1}(A)$ for any $A\in \mathbb Z^2$. If $X=\{E,N\}$ is the step set from Example 2.1, then for any $a,b\in \mathbb Z$, we have $\pi _X(a,b) = \left( {\begin{array}{c}a+b\\ a\end{array}}\right) =\left( {\begin{array}{c}a+b\\ b\end{array}}\right)$.

Given a step set X, the values of $\pi _X(A)$ may be conveniently displayed on an edge- and vertex-labelled digraph, which we denote by $\Gamma _X$, and define as follows:

• The vertices of $\Gamma _X$ are the elements of $\mathscr {A}_X$, and each vertex $A\in \mathscr {A}_X$ is labelled by $\pi _X(A)$.

• For each vertex $A\in \mathscr {A}_X$, and for each $B\in X$, $\Gamma _X$ has the labelled edge $A\xrightarrow {\ B\ }A+B$.

Since the vertices of the graph $\Gamma _X$ are actually elements of $\mathbb Z^2$, we generally draw $\Gamma _X$ in the plane $\mathbb R^2$, with the vertices in the specified position. So $\Gamma _X$ is the Cayley graph of $\mathscr {A}_X$ with respect to the generating set X, embedded in the plane, and with each vertex labelled by the number of factorisations in the generators. As an example, Fig. 2 (left) pictures the graph $\Gamma _X$, where $X=\{E,N\}$ is the step set from Example 2.1. This is of course a rotation of Pascal’s Triangle [17].

Fig. 2

The graph $\Gamma _X$, where (left to right): $X=\{(1,0),(0,1)\}$, $X=\{(\pm 1,0),(0,\pm 1)\}$ (left) and $X=\{(1,0),(0,\pm 1)\}$; cf. Examples 2.1 and 2.2

The next pair of examples involve step sets related to that considered in Example 2.1.

Example 2.2

• (i) Let $X=\{N,E,S,W\}$, where $N=(0,1)$, $E=(1,0)$, $S=(0,-1)$ and $W=(-1,0)$. Then $\mathscr {A}_X=\mathbb Z^2$, and $\pi _X(A)=\infty$ for all $A\in \mathbb Z^2$. See Fig. 2 (middle) for an illustration of $\Gamma _X$.

• (ii) If $X=\{N,E,S\}$, then $\mathscr {A}_X=\mathbb N\times \mathbb Z$, and $\pi _X(A)=\infty$ for all $A\in \mathscr {A}_X$; see Fig. 2 (right) for $\Gamma _X$.

We conclude this section by considering a collection of infinite step sets.

Example 2.3

Let $X=\{1\}\times \mathbb Z=\{ {(1,a)} : {a\in \mathbb Z} \}$. Then $\mathscr {A}_X=\{O\}\cup (\mathbb P\times \mathbb Z)=\{O\}\cup \{ {(a,b)\in \mathbb Z^2} : {a\ge 1} \}$. For any $a,b\in \mathbb Z$ we have

$$\begin{aligned} \pi _X(a,b) = {\left\{ \begin{array}{ll} 1 &{}\text {if } (a,b)=O\text { or }a=1\\ \infty &{}\text {if } a\ge 2\\ 0 &{}\text {otherwise.} \end{array}\right. } \end{aligned}$$

The graph $\Gamma _X$ is pictured in Fig. 3 (left). Note that while there are infinitely many X-walks to any $(a,b)\in \mathscr {A}_X$ with $a\ge 2$, any such walk is of length a. Fig. 3 (right) also pictures the graph associated to a different step set, whose steps point in the same direction as the steps from the current one; more details will be given in Example 2.13.

Fig. 3

The graph $\Gamma _X$, where $X=\{1\}\times \mathbb Z$ (left) and $X=\{(1,0)\}\cup \{ {(a,\pm a^2)} : {a\in \mathbb P} \}$ (right); cf. Examples 2.3 and 2.13. All edges are directed to the right

Although the next collection of step sets are also infinite, all values of $\pi _X(A)$ are finite.

Example 2.4

• (i) Let $X=\{1\}\times \mathbb N$. Then $\mathscr {A}_X=\{O\}\cup (\mathbb P\times \mathbb N)$. The graph $\Gamma _X$ is pictured in Fig. 4 (left). It is not hard to show, using standard recursion techniques, that $\pi _X(a,b) = \left( {\begin{array}{c}a+b-1\\ b\end{array}}\right)$ for $(a,b)\in \mathbb P\times \mathbb N$. In particular, we again have a copy of Pascal’s Triangle, but this time with an extra 1 at the origin, and this happens in the next step set as well.

• (ii) Let $X=\{1\}\times \mathbb P$. Then $\mathscr {A}_X=\{O\}\cup \{ {(a,b)\in \mathbb P^2} : {a\le b} \}$. The graph $\Gamma _X$ is pictured in Fig. 4 (middle). This time we have $\pi _X(a,b) = \left( {\begin{array}{c}b-1\\ a-1\end{array}}\right)$ for $(a,b)\in \mathscr {A}_X\setminus \{O\}$.

• (iii) Let $X=\{(0,1)\}\cup (\{1\}\times \mathbb P)$. Then $\mathscr {A}_X=\{ {(a,b)\in \mathbb N^2} : {a\le b} \}$. The graph $\Gamma _X$ is pictured in Fig. 4 (right). This time we have $\pi _X(a,b) = \left( {\begin{array}{c}a+b\\ b-a\end{array}}\right)$ for $(a,b)\in \mathscr {A}_X$.

We leave the reader to investigate the step sets $X=\{0\}\times \mathbb P$ and $X=\mathbb P^2$.

Fig. 4

The graph $\Gamma _X$, where (left to right): $X=\{1\}\times \mathbb N$, $X=\{1\}\times \mathbb P$ and $X=\{(0,1)\}\cup (\{1\}\times \mathbb P)$; cf. Example 2.4. All edges are directed to the right and/or upwards

2.2 Finiteness Properties: FPP, IPP and BPP

Inspired by Examples 2.1 and 2.2 above, we introduce the following two properties that might be satisfied by a step set $X\subseteq \mathbb Z_\times ^2$.

• We say X has the Finite Paths Property (FPP) if ${\pi _X(A)<\infty }$ for all $A\in \mathscr {A}_X$.

• We say X has the Infinite Paths Property (IPP) if ${\pi _X(A)=\infty }$ for all $A\in \mathscr {A}_X$.

Example 2.3 shows that some step sets satisfy neither the FPP nor the IPP; cf. Fig. 3 (left). By contrast, we will see later that finite step sets must satisfy one or the other. Example 2.3 does suggest a third property worthy of attention:

• We say X has the Bounded Paths Property (BPP) if for all $A\in \mathscr {A}_X$, the set $\{ {\ell (w)} : {w\in \Pi _X(A)} \}$ has a maximum element (equivalently, this set is finite).

We begin with a simple result concerning the IPP. Recall that the empty word $\varepsilon$ belongs to $\Pi _X(O)$ for any step set X, so that $\pi _X(O)\ge 1$.

Lemma 2.5

Let $X\subseteq \mathbb Z_\times ^2$ be an arbitrary step set. Then the following are equivalent:

• (i) $X \, \,\mathrm{has} \, \,\mathrm{the} \,\,IPP$,

• (ii) $\pi _X(O)=\infty$,

• (iii) $\pi _X(O)\ge 2$.

Proof

Clearly (i)$\ \Rightarrow \$(ii)$\ \Rightarrow \$(iii). Now assume (iii) holds, and let $A\in \mathscr {A}_X$ be arbitrary. Let $u\in \Pi _X(O)\setminus \{\varepsilon \}$ and $v\in \Pi _X(A)$. Then $u^kv\in \Pi _X(A)$ for all $k\ge 0$, from which it follows that $\pi _X(A)=\infty$. $\square$

Thus, if one was primarily interested in enumeration of lattice paths, one would focus on step sets with $\pi _X(O)=1$. Having $\pi _X(O)=1$ still does not guarantee “interesting” enumeration, however. Indeed, Example 2.3 gave a step set for which the only values of $\pi _X(A)$ are 1 and $\infty$ (cf. Fig. 3). For an even more extreme situation, Example 2.17 below shows that it is possible to have $\pi _X(O)=1$ but $\pi _X(A)=\infty$ for all $A\in \mathscr {A}_X\setminus \{O\}$.

The next result demonstrates a basic relationship between the three finiteness properties, in particular showing that the BPP is an intermediate between the FPP and $\lnot$IPP (the symbol $\lnot$ denotes negation). Specifically, we have FPP$\ \Rightarrow \$BPP$\ \Rightarrow \$ $\lnot$IPP.

Lemma 2.6

Let $X\subseteq \mathbb Z_\times ^2$ be an arbitrary step set.

• (i) If X has the FPP, then X has the BPP.

• (ii) If X has the BPP, then X does not have the IPP.

Proof

• (i). If $\Pi _X(A)$ is finite, then so too is $\{ {\ell (w)} : {w\in \Pi _X(A)} \}$.

• (ii). If the set $\{ {\ell (w)} : {w\in \Pi _X(O)} \}$ is finite, then $\pi _X(O)=1$; cf. Lemma 2.5 and its proof.$\square$

We will see later that the three conditions FPP, BPP and $\lnot$IPP are equivalent for finite step sets.

2.3 Geometric Conditions: CC, SLC and LC

A line splits the plane $\mathbb R^2$ into two open subsets, one on each side of the line; we will call these open sets half-planes, and we will say that they are opposites of each other. By a cone we mean an intersection of two half-planes whose bounding lines are not parallel; the intersection of these bounding lines is called the vertex of the cone; by the opposite of such a cone, we mean the intersection of the opposite half-planes. See Fig. 5. Note that half-planes and cones are always open sets. Note also that half-planes are not cones.

Fig. 5

A pair of opposite half-planes (left) and a pair of opposite cones (right)

Now let $X\subseteq \mathbb Z_\times ^2$ be an arbitrary step set.

• We say X satisfies the Line Condition (LC) if it is contained in a half-plane bounded by a line through the origin.

• We say X satisfies the Strong Line Condition (SLC) if it is contained in a half-plane whose opposite half-plane contains the origin.

• We say X satisfies the Cone Condition (CC) if it is contained in a cone with the origin as its vertex.

We say that a line $\mathscr {L}$ through the origin witnesses the LC (for X) if X is contained in one of the half-planes determined by $\mathscr {L}$. Similarly, we may speak of a line (not through the origin) witnessing the SLC, or of a pair of lines (through the origin) witnessing the CC, or of a cone (with vertex O) witnessing the CC.

The reader may wonder why we have not defined a Strong Cone Condition. For completeness, we do so here (in the obvious way) but show immediately that it is equivalent to the ordinary Cone Condition.

• We say X satisfies the Strong Cone Condition (SCC) if it is contained in a cone whose opposite cone contains the origin.

Lemma 2.7

A step set $X\subseteq \mathbb Z_\times ^2$ satisfies the CC if and only if it satisfies the SCC.

Proof

(SCC$\ \Rightarrow \$CC). Any cone whose opposite cone contains the origin is contained in a cone with O as its vertex.

(CC$\ \Rightarrow \$SCC). Suppose X satisfies the CC, as witnessed by the cone $\mathcal C$. Choose points C and D, one on each bounding line of $\mathcal C$, and both a distance of $\frac{1}{2}$ from O, noting that the triangle $\triangle OCD$ contains no lattice points other than O. If E is any point in the interior of this triangle, then the SCC is witnessed by the line through C and E and the line through D and E. All of this is pictured in Fig. 6. $\square$

Fig. 6

Schematic diagram of the proof of Lemma 2.7. The elements of X are drawn as black dots (color figure online)

Here is the key result of this section:

Lemma 2.8

Let $X\subseteq \mathbb Z_\times ^2$ be an arbitrary step set.

• (i) If X satisfies the CC, then X satisfies the SLC.

• (ii) If X satisfies the SLC, then X satisfies the LC.

• (iii) If X is finite and satisfies the LC, then X satisfies the CC.

Proof

• (i). If X satisfies the CC, then by Lemma 2.7 it satisfies the SCC. If a cone $\mathcal C$ witnesses the SCC, then the bounding lines of $\mathcal C$ both witness the SLC.

• (ii). If the SLC condition is witnessed by $\mathscr {L}$, then the LC is witnessed by the line through O parallel to $\mathscr {L}$.

• (iii). Suppose the LC is witnessed by $\mathscr {L}$, where X is finite and (without loss of generality) non-empty. Let A be an arbitrary point on $\mathscr {L}$ other than O (note that $A\not \in X$). Let $B\in X$ be such that the non-reflex angle $\angle AOB$ is minimal among all points from X; this is well defined because X is finite, and we have $0<\angle AOB<\pi$ because no point from X lies on $\mathscr {L}$. Let $\mathscr {L}'$ be the line that bisects the angle $\angle AOB$. Then $\mathscr {L}$ and $\mathscr {L}'$ witness the CC. This is all shown in Fig. 7.$\square$

Fig. 7

The points A, B and line $\mathscr {L}'$ constructed during the proof of Lemma 2.8(iii)

It follows from Lemma 2.8 that the three conditions CC, SLC and LC are equivalent for finite step sets. The step sets from Examples 2.1 and 2.4 satisfy all three conditions, and those from Example 2.2 satisfy none of them. The step set from Example 2.3 satisfies the SLC (and hence also the LC) but not the CC. Example 2.17 below shows it is possible to satisfy the LC but not the SLC (and hence also not the CC).

It will also be convenient to prove the following technical result, which will be used on many occasions.

Lemma 2.9

Let $X\subseteq \mathbb Z_\times ^2$ be a step set with the LC witnessed by a unique line $\mathscr {L}$. Then

• (i) X does not satisfy the CC,

• (ii) if X satisfies the SLC, then this can only be witnessed by lines parallel to $\mathscr {L}$.

Proof

(i). If some cone witnessed the CC, then the two bounding lines would both witness the LC.

(ii). If a line $\mathscr {L}'$ witnesses the SLC, then (as in the proof of Lemma 2.8(ii)) the LC is witnessed by the line through the origin parallel to $\mathscr {L}'$. By assumption, this must be $\mathscr {L}$.$\square$

2.4 Step Sets of Size at Most 2

In this section, we give a complete description of the additive monoids $\mathscr {A}_X$, and the numbers $\pi _X(A)$, when $X\subseteq \mathbb Z_\times ^2$ is a step set of size at most 2. Parts of the classification will be used in subsequent sections. One could readily classify step sets of size 3, although there are several more cases to consider.

We begin with a lemma describing certain 2-generated submonoids of the additive group $(\mathbb Z,+)$; it follows from [11, Corollary II.4.2], or is easily proved directly. For $a_1,\ldots ,a_k\in \mathbb Z$, we write ${\text {Mon}}\langle a_1,\ldots ,a_k\rangle$ for the submonoid of $\mathbb Z$ generated by $a_1,\ldots ,a_k$. If $a,b\in \mathbb Z$, we write $a\mid b$ to indicate that a divides b; if a and b are not both zero, we write $\gcd (a,b)$ for their greatest common divisor. Throughout this section, we use elementary number theoretic facts, as found for example in [14].

Lemma 2.10

Let $a,b\in \mathbb P$, and put $d=\gcd (a,b)$. Then ${\text {Mon}}\langle a,-b\rangle ={\text {Mon}}\langle \pm d\rangle$. In particular, ${\text {Mon}}\langle a,-b\rangle$ is a non-trivial subgroup of $\mathbb Z$, and is therefore isomorphic to $(\mathbb Z,+)$. $\square$

For the next proof, recall Euclid’s Lemma: If $a,b,c\in \mathbb Z$ and $\gcd (a,b)=1$, then ${a\mid bc \ \Rightarrow \ a\mid c}$.

Proposition 2.11

Consider a step set $X\subseteq \mathbb Z_\times ^2$.

• (i) If $X=\{A\}$, then $\mathscr {A}_X\cong (\mathbb N,+)$.

• (ii) If $X=\{A,B\}$ where $A\not =B$ and $\angle AOB=0$, then $\mathscr {A}_X$ is isomorphic to a 2-generated submonoid of $(\mathbb N,+)$.

• (iii) If $X=\{A,B\}$ where $\angle AOB=\pi$, then $\mathscr {A}_X\cong (\mathbb Z,+)$.

• (iv) If $X=\{A,B\}$ where $0<\angle AOB<\pi$, then $\mathscr {A}_X\cong (\mathbb N\times \mathbb N,+)$.

Proof

The first part being clear, for the duration of the proof, let $A=(a,b)$ and $B=(c,d)$ be distinct points from $\mathbb Z_\times ^2$.

(ii). Suppose $\angle AOB=0$. So A and B both lie on the same side of the origin on a straight line, $\mathscr {L}$. If the line $\mathscr {L}$ is $y=0$, then clearly $\mathscr {A}_X = {\text {Mon}}\langle (a,0),(c,0)\rangle$ is isomorphic to the submonoid ${\text {Mon}}\langle a,c\rangle$ of $\mathbb N$ if $a,c>0$, or to ${\text {Mon}}\langle -a, -c\rangle$ if $a,c<0$. A similar argument covers the case in which $\mathscr {L}$ is $x=0$. So suppose instead that $\mathscr {L}$ has finite and non-zero gradient. Since the lattice points A, B lie on $\mathscr {L}$, its gradient must be rational, so we may assume $\mathscr {L}$ has equation $y=\frac{m}{n}x$, where $m,n\in \mathbb Z$, $n\not =0$ and $\gcd (m,n)=1$. Since $\angle AOB=0$, we may further assume that n has the same sign as a and c. Since $A=(a,b)$ is on $\mathscr {L}$, we see (using Euclid’s Lemma) that

$$\begin{aligned} b=\tfrac{m}{n}a \ \Rightarrow \ n\mid ma \ \Rightarrow \ n\mid a \ \Rightarrow \ a=kn \quad \text { for some } k\in \mathbb P. \end{aligned}$$

So $A=(a,b)=k(n,m)$. Similarly, $B=l(n,m)$ for some $l\in \mathbb P$. But then clearly $\mathscr {A}_X={\text {Mon}}\langle A,B\rangle$ is isomorphic to the submonoid ${\text {Mon}}\langle k,l\rangle$ of $(\mathbb N,+)$ generated by k, l.

(iii). Suppose $\angle AOB=\pi$. As in the previous case, the result is trivial if A, B both lie on $x=0$ or $y=0$. Otherwise, we may similarly show that $A=k(n,m)$ and $B=l(n,m)$ for some $m,n\in \mathbb Z$ with $\gcd (m,n)=1$ and some non-zero $k,l\in \mathbb Z$, but this time k, l have opposite sign. It follows that $\mathscr {A}_X={\text {Mon}}\langle A,B\rangle$ is isomorphic to $M={\text {Mon}}\langle k,l\rangle$, the submonoid of $(\mathbb Z,+)$ generated by k, l, and the proof in this case concludes after applying Lemma 2.10.

(iv). Finally, suppose $0<\angle AOB<\pi$. Since $\mathscr {A}_X={\text {Mon}}\langle A,B\rangle =\{ {kA+lB} : {k,l\in \mathbb N} \}$, there is a surmorphism $\phi :\mathbb N\times \mathbb N\rightarrow \mathscr {A}_X$ defined by $\phi (k,l)=kA+lB$. Injectivity of $\phi$ follows quickly from the linear independence of A and B.$\square$

Remark 2.12

Proposition 2.11 has implications for the numbers $\pi _X(C)$, $C\in \mathscr {A}_X$, when $|X|\le 2$:

• (i) If $X=\{A\}$, then $\mathscr {A}_X\cong (\mathbb N,+)$, and $\pi _X(C)=1$ for all $C\in \mathscr {A}_X$.

• (ii) If $X=\{A,B\}$ where $A\not =B$ and $\angle AOB=0$, then as in the above proof, we may assume that $A=kC$ and $B=lC$, where $k,l\in \mathbb P$, and $C\in \mathbb Z_\times ^2$ is some fixed point. The numbers $a_n=\pi _X(nC)$, $n\in \mathbb Z$, satisfy

  $$\begin{aligned} a_n=0\ (n<0) ,\qquad a_0=1 ,\qquad a_n=a_{n-k}+a_{n-l}\ (n>0). \end{aligned}$$

  Thus, for example, we obtain the Fibonacci sequence when $(k,l)=(1,2)$, the Narayana’s Cows sequence when $(k,l)=(1,3)$, the Padovan sequence when $(k,l)=(2,3)$, and so on; see [1, A000045, A000930 and A000931]. The study of submonoids of $\mathbb N$ is a considerable topic, known as numerical semigroup theory; see for example [2, 18]. Submonoids of $\mathbb N^2$ (and more generally $\mathbb N^k$, $k\ge 2$) have been studied for example in [5], where the situation is rather more complicated. For example, every submonoid of $\mathbb N$ is finitely generated, so there are only countably many of them; by contrast, even $\mathbb N^2$ contains uncountably many pairwise non-isomorphic subdirect products [5, Theorem C].

• (iii) If $X=\{A,B\}$ where $\angle AOB=\pi$, then $\mathscr {A}_X\cong (\mathbb Z,+)$, and so $\pi _X(C)=\infty$ for all $C\in \mathscr {A}_X$.

• (iv) Finally, if $X\!=\!\{A,B\}$ where $0\!<\!\angle AOB\!<\!\pi$, then $\mathscr {A}_X\!=\!\{ {xA\!+\!yB} : {x,y\in \mathbb N} \}\cong (\mathbb N\times \mathbb N,+)$, and $\pi _X(xA+yB)=\left( {\begin{array}{c}x+y\\ x\end{array}}\right) =\left( {\begin{array}{c}x+y\\ y\end{array}}\right)$; cf. Example 2.1.

2.5 Three More Infinite Step Sets

We now take a brief pause from the theoretical development to consider three further examples, each involving infinite step sets. These will be crucial in establishing the main results of Sect. 2.7, and will also be used to highlight some subtleties in the main results of Sect. 2.6.

Example 2.13

Let $X=\{(1,0)\}\cup \{ {(a,\pm a^2)} : {a\in \mathbb P} \}$. Note that the steps in X point in the same directions as those from the step set of Example 2.3. Here it is not so easy to give a uniform description of the elements of the monoid $\mathscr {A}_X$, or to draw the graph $\Gamma _X$, but see Fig. 3 (right) for the first few columns. Clearly X satisfies the SLC.

Less trivially, we claim that X does not satisfy the CC. To see this, consider some line $\mathscr {L}$ given by $y=mx$. Let n be an arbitrary integer with $n>|m|$. Then the points $(n,n^2)$ and $(n,-n^2)$ from X lie on opposite sides of $\mathscr {L}$, meaning that $\mathscr {L}$ does not witness the LC. Thus, $x=0$ is the unique line witnessing the LC, so the claim follows from Lemma 2.9(i).

It is also the case that X has the FPP. Indeed, one may easily prove this directly, but it also follows from Lemma 2.23(i) below, so we will not provide any further details.

Example 2.14

If $X=\{(0,-1)\}\cup \{ {(a,a^2)} : {a\in \mathbb P} \}$, then

$$\begin{aligned} \mathscr {A}_X=\{ {(a,b)\in \mathbb Z^2} : {a\ge 0,\ b\le a^2} \}. \end{aligned}$$

This X does not satisfy the LC: indeed, the line $x=0$ contains $(0,-1)$, and any other line through the origin has $(0,-1)$ below it and infinitely many points from X above it. As in the previous example, X has the FPP, as also follows from Lemma 2.23 below.

The next example involves lines of irrational slope. It is first necessary to prove the following lemma, which is a strengthening of a classical result of Kempner [16, Theorem 2]. The additional strength is not needed immediately, but will be useful later.

Lemma 2.15

Let R be an arbitrary positive real number. Between any two parallel lines of irrational slope, there exist lattice points $(a,b),(c,d)\in \mathbb Z^2$ with $a> R$ and $c< -R$.

Proof

By symmetry, we just show the existence of (a, b). Let the lines have equations $y=\alpha x+\gamma$ and $y=\alpha x+\delta$, where $\alpha$ is irrational, and $\gamma <\delta$. We must show that there exists $(a,b)\in \mathbb Z^2$ such that $a>R$ and $\alpha a+\gamma< b < \alpha a+\delta$: i.e., $\gamma< b-\alpha a<\delta$.

Consider the set $M=\{ {v-\alpha u} : {u\in \mathbb P,\ v\in \mathbb Z} \}$. First we make the following claim:

• For any $\varepsilon >0$ there exists $s,t\in M$ such that $-\varepsilon<s<0<t<\varepsilon$.

To prove the claim, let $\varepsilon >0$ be arbitrary; clearly we may assume that $\varepsilon <1$. By Dirichlet’s Theorem (see for example [19, Theorem 1A]), there exist $u\in \mathbb P$ and $v\in \mathbb Z$ such that $|v-\alpha u|<\varepsilon$. Since $\alpha$ is irrational and $u\not =0$, we have $v-\alpha u\not =0$. We assume $v-\alpha u>0$, the other case being symmetrical. Put $t=v-\alpha u$, noting that $t\in M$ and $0<t<\varepsilon$. Now consider the numbers $t,2t,3t,\ldots$; since $0<t<\varepsilon$, at least one of these belongs to the interval $1-\varepsilon<x<1$, say $1-\varepsilon<kt<1$ where $k\in \mathbb P$. Then put $s=kt-1=(kv-1)-\alpha (ku)$.

Returning to the main proof now, we consider three cases.

Case 1. If $\gamma<0<\delta$, then by the claim (with $\varepsilon =\frac{\delta }{R}$) there exists $u\in \mathbb P$ and $v\in \mathbb Z$ such that $0<v-\alpha u<\frac{\delta }{R}$. Since $\gamma <0$ it follows that $\frac{\gamma }{R}<v-\alpha u<\frac{\delta }{R}$. We then take $(a,b)=(Ru,Rv)$.

Case 2. If $0\le \gamma <\delta$, then we put $\varepsilon =\frac{\delta -\gamma }{R}$. By the claim there exists $u\in \mathbb P$ and $v\in \mathbb Z$ such that $t=v-\alpha u$ satisfies $0<t<\varepsilon$. Again one of the numbers $t,2t,3t,\ldots$ must lie in the interval $\frac{\gamma }{R}<x<\frac{\delta }{R}$, say $\frac{\gamma }{R}<kt<\frac{\delta }{R}$ where $k\in \mathbb P$. We then take $(a,b)=(Rku,Rkv)$.

Case 3. The case in which $\gamma <\delta \le 0$ is symmetrical. $\square$

Remark 2.16

Consider two parallel lines of irrational slope, say $\mathscr {L}$ and $\mathscr {L}_0$. By Lemma 2.15 there is a lattice point $A_1=(x_1,y_1)$ between $\mathscr {L}$ and $\mathscr {L}_0$ with $x_1\ge 1$. Now let $\mathscr {L}_1$ be the line parallel to $\mathscr {L}$ through $A_1$. By Lemma 2.15 again, there is a lattice point $A_2=(x_2,y_2)$ between $\mathscr {L}$ and $\mathscr {L}_1$ with $x_2\ge x_1+1$. Continuing in this way, we obtain a sequence of lattice points $A_i=(x_i,y_i)$, $i\in \mathbb P$, satisfying $1\le x_1<x_2<x_3<\cdots$. Moreover, if we write $\delta _i$ ($i\in \mathbb P$) for the distance from $\mathscr {L}$ to $A_i$, then we have $\delta _i>0$ for all i, $\delta _1>\delta _2>\delta _3>\cdots$, and $\lim _{i\rightarrow \infty }\delta _i=0$.

Example 2.17

Let $\mathscr {L}$ be any line through the origin of irrational slope, let H be one of the (open) half-planes bounded by $\mathscr {L}$, and let $X=H\cap \mathbb Z^2$ be the set of all lattice points contained in H. Since H, and hence X, is closed under addition, we have $\mathscr {A}_X=\{O\}\cup X$, and also $\pi _X(O)=1$. We claim that for any $A\in X=\mathscr {A}_X\setminus \{O\}$, there are arbitrarily long X-walks from O to A.

To prove the claim, let $A\in X$, and let $k\ge 2$ be arbitrary. We will show that there is an X-walk from O to A of length k (this is obviously true for $k=1$ as well). Let $\mathscr {L}_0=\mathscr {L}$, let $\mathscr {L}_k$ be the line parallel to $\mathscr {L}$ through A, and let $\mathscr {L}_1,\ldots ,\mathscr {L}_{k-1}$ be a sequence of distinct lines each parallel to $\mathscr {L}$ such that $\mathscr {L}_i$ is between $\mathscr {L}_{i-1}$ and $\mathscr {L}_{i+1}$ for each $1\le i\le k-1$. All of this (and more information to follow) is pictured in Fig. 8. By Lemma 2.15, we may choose lattice points $A_1,\ldots ,A_{k-1}\in \mathbb Z^2$ such that $A_i$ is between $\mathscr {L}_{i-1}$ and $\mathscr {L}_i$ for each $1\le i\le k-1$. Also define $A_0=O$ and $A_k=A$. Let $B_i=A_i-A_{i-1}$ for each $1\le i\le k$. The claim will be established if we can show that $B_1\cdots B_k$ is an X-walk from O to A. Indeed, we certainly have $B_1+\cdots +B_k=A$, so it just remains to check that $B_i\in X$ for each i. But if $\mathbf{u}$ is a vector perpendicular to $\mathscr {L}$ pointing into H, we have $\mathbf{u}\cdot \overrightarrow{OA}_{i-1}<\mathbf{u}\cdot \overrightarrow{OA}_i$ for each $1\le i\le k$ (by construction), from which it follows that $\mathbf{u}\cdot \overrightarrow{OB}_i=\mathbf{u}\cdot (\overrightarrow{OA}_i-\overrightarrow{OA}_{i-1})>0$ for each such i, giving $B_i\in H$, and so $B_i\in X$.

With the claim now established, there are two immediate consequences:

• $\pi _X(A)=\infty$ for all $A\in \mathscr {A}_X\setminus \{O\}$, and

• X does not have the BPP.

Since $\pi _X(O)=1$, as mentioned above, it follows also that:

• X has neither the IPP nor the FPP.

In terms of the geometric conditions, first note that X satisfies the LC, as witnessed by $\mathscr {L}$ itself. But, since there are points from X arbitrarily close to $\mathscr {L}$ (by Lemma 2.15), it follows that no line parallel to $\mathscr {L}$ witnesses the SLC. Since it is also clear that no other line (through the origin) witnesses the LC, it follows from both parts of Lemma 2.9 that X satisfies neither the CC nor the SLC.

Fig. 8

Schematic diagram of the proof of the claim in Example 2.17 (with $k=5$)

2.6 Geometric, Algebraic and Combinatorial Characterisations of the IPP

Recall that a convex combination of a finite collection of points $A_1,\ldots ,A_k\in \mathbb R^2$ is a point of the form ${\lambda _1A_1+\cdots +\lambda _kA_k}$ where ${\lambda _1,\ldots ,\lambda _k\ge 0}$ and $\lambda _1+\cdots +\lambda _k=1$. The convex hull of a (finite or infinite) subset $X\subseteq \mathbb R^2$, denoted ${\text {Conv}}(X)$, is the set of all convex combinations of (finite collections of) points from X. For background on basic convex geometry, see for example [4, Section 2].

The main result of this section shows that a step set X has the IPP if and only if the origin O is in the convex hull of X; see Theorem 2.19 below, which also gives algebraic and combinatorial characterisations of the IPP in terms of the monoid $\mathscr {A}_X$ and the graph $\Gamma _X$. First we need a lemma.

Lemma 2.18

Suppose $A,B,C\in \mathbb R^2\setminus \{O\}$ are such that A, B, C and O are not all collinear. If there exist scalars $\alpha ,\beta ,\gamma \in \mathbb R$ such that $\alpha +\beta +\gamma =1$ and $\alpha A+\beta B+\gamma C=O$, then there exist unique such scalars.

Proof

Write $\mathbf{a},\mathbf{b},\mathbf{c},\mathbf{0}$ for the position vectors of A, B, C, O, respectively, noting that $\alpha \mathbf{a}+\beta \mathbf{b}+\gamma \mathbf{c}=\mathbf{0}$. By the non-collinear assumption, and renaming the points A, B, C if necessary, we may assume that $\mathbf{a}$ and $\mathbf{b}$ are linearly independant. First note that we must have $\gamma \not =0$; otherwise, we would have $\alpha \mathbf{a}+\beta \mathbf{b}=\mathbf{0}$, giving $\alpha =\beta =0$ (by linear independance), contradicting $\alpha +\beta +\gamma =1$. It then follows that $\mathbf{c}=-\tfrac{\alpha }{\gamma }\mathbf{a}-\tfrac{\beta }{\gamma }\mathbf{b}$. Suppose now that $\alpha ' A+\beta ' B+\gamma ' C=O$ where $\alpha '+\beta '+\gamma '=1$. Then

$$\begin{aligned} \alpha '\mathbf{a}+\beta '\mathbf{b}=-\gamma '\mathbf{c}=-\gamma '\big ({-\tfrac{\alpha }{\gamma }\mathbf{a}-\tfrac{\beta }{\gamma }\mathbf{b}}\big )=\tfrac{\alpha \gamma '}{\gamma }\mathbf{a}+\tfrac{\beta \gamma '}{\gamma }\mathbf{b}. \end{aligned}$$

It then follows (by linear independence) that $\alpha '=\tfrac{\alpha \gamma '}{\gamma }$ and $\beta '=\tfrac{\beta \gamma '}{\gamma }$. But then

$$\begin{aligned} 1=\alpha '+\beta '+\gamma ' = \tfrac{\alpha \gamma '}{\gamma }+ \tfrac{\beta \gamma '}{\gamma }+ \tfrac{\gamma \gamma '}{\gamma }= \tfrac{\gamma '}{\gamma }(\alpha +\beta +\gamma )= \tfrac{\gamma '}{\gamma }, \end{aligned}$$

so that $\gamma '=\gamma$. We deduce also that $\alpha '=\tfrac{\alpha \gamma '}{\gamma }=\alpha$ and $\beta '=\tfrac{\beta \gamma '}{\gamma }=\beta$.$\square$

Recall that an element of a monoid is a unit if it is invertible with respect to the identity of the monoid; the set of all units is a subgroup. Here are the promised characterisations of the IPP.

Theorem 2.19

Let $X\subseteq \mathbb Z_\times ^2$ be an arbitrary step set. Then the following are equivalent:

• (i) X has the IPP,

• (ii) $O\in {\text {Conv}}(X)$,

• (iii) $\mathscr {A}_X$ has non-trivial units,

• (iv) $\Gamma _X$ has non-trivial directed cycles.

Proof

(i)$\ \Rightarrow \$(ii). If X has the IPP, then $O=A_1+\cdots +A_k$ for some $k\ge 1$ and some $A_1,\ldots ,A_k\in X$, in which case $O=\frac{1}{k}A_1+\cdots +\frac{1}{k}A_k\in {\text {Conv}}(X)$.

(ii)$\ \Rightarrow \$(iii). Suppose $O\in {\text {Conv}}(X)$. So O is a convex combination of some non-empty collection of points $A_1,\ldots ,A_k$ from X, and we assume that k is minimal, noting that $k\ge 2$.

If $k=2$, then $\angle A_1OA_2=\pi$, so $\pi _X(O)\ge \pi _{\{A_1,A_2\}}(O)=\infty$; cf. Remark 2.12(iii). It follows that $O=xA_1+yA_2$ for some $x,y\ge 1$, and so $A_1$ is a unit of $\mathscr {A}_X$ (with inverse $(x-1)A_1+yA_2$).

For the rest of the proof we assume that $k\ge 3$. By minimality of k, ${\text {Conv}}(A_1,\ldots ,A_k)$ is a non-degenerate convex k-gon in $\mathbb R^2$; relabelling if necessary, we may assume the vertices of this polygon taken clockwise are $A_1,\ldots ,A_k$. Since the triangles $\triangle A_1A_2A_3,\triangle A_1A_3A_4,\ldots ,\triangle A_1A_{k-1}A_k$ make up the whole polygon, we see that O lies in one of these triangles, say $\triangle A_1A_{m-1}A_m$; since $k\ge 3$ is minimal, O is not on the boundary of this triangle. (Incidentally, this shows that $k=3$; cf. Carathéodory’s Theorem [4, Corollary 2.4].) Write $A=A_1$, $B=A_{m-1}$ and $C=A_m$. Since $O\in {\text {Conv}}(A,B,C)$, we have

$$\begin{aligned} O = \alpha A + \beta B + \gamma C \qquad&\text {for some\,\,}\alpha ,\beta ,\gamma \in \mathbb R\nonumber \\&\hbox {with} \quad \alpha ,\beta ,\gamma \ge 0\hbox { and }\alpha +\beta +\gamma =1. \end{aligned}$$

(2.1)

By the minimality of $k\ge 3$, it follows that $\alpha ,\beta ,\gamma$ are all non-zero. Write $A=(a,b)$, $B=(c,d)$, $C=(e,f)$. So (2.1) gives

$$\begin{aligned} a\alpha +c\beta +e\gamma =0 ,\qquad b\alpha +d\beta +f\gamma =0 ,\qquad \alpha +\beta +\gamma =1. \end{aligned}$$

That is, $(x,y,z)=(\alpha ,\beta ,\gamma )$ is a solution to the system of linear equations

$$\begin{aligned} ax+cy+ez =0 ,\qquad bx+dy+fz =0 ,\qquad x+y+z =1. \end{aligned}$$

(2.2)

Since $\triangle ABC$ is a non-degenerate triangle, certainly A, B, C, O are not all collinear, so Lemma 2.18 says that (2.2) has a unique solution. Since the solution is unique, it may be found by inverting the coefficient matrix $\left[ {\begin{matrix}a&{}c&{}e\\ b&{}d&{}f\\ 1&{}1&{}1\end{matrix}}\right]$; since this matrix has integer entries, its inverse has rational entries, and so the solution to (2.2) is rational; that is, $\alpha ,\beta ,\gamma$ are rational. Since we already know that $\alpha ,\beta ,\gamma >0$, there exists $\delta \in \mathbb P$ such that $x=\alpha \delta$, $y=\beta \delta$ and $z=\gamma \delta$ are all (positive) integers. But then (2.1) gives $O =xA+yB+zC$, and since $x>0$, it follows that A is a unit (with inverse $(x-1)A+yB+zC$).

(iii)$\ \Rightarrow \$(iv). Suppose $A\in \mathscr {A}_X$ is a non-trivial unit, and let $B\in \mathscr {A}_X$ be its inverse. Write $A=A_1+\cdots +A_k$ and $B=B_1+\cdots +B_l$ where $k,l\ge 1$ and the $A_i,B_i$ belong to X. Since $O=A+B$, the edges $A_1,\ldots ,A_k,B_1,\ldots ,B_l$ determine a directed cycle from O to O in $\Gamma _X$.

(iv)$\ \Rightarrow \$(i). If $A\xrightarrow {\ B_1\ }A+B_1\xrightarrow {\ B_2\ }\cdots \xrightarrow {\ B_k\ }A$ is a non-trivial directed cycle in $\Gamma _X$, then $A=A+B_1+\cdots +B_k$, which implies $O=B_1+\cdots +B_k$, and so $B_1\cdots B_k\in \Pi _X(O)\setminus \{\varepsilon \}$; Lemma 2.5 then says that X has the IPP.$\square$

Remark 2.20

Theorem 2.19 implies that $\Gamma _X$ is a directed acyclic graph (DAG) if and only if X does not have the IPP.

Remark 2.21

One may compare Theorem 2.19 with the various examples considered in Sects. 2.1 and 2.5 (and later in the paper). Of these, only the two step sets from Example 2.2 have the IPP, and these are of course the only step sets containing O in their convex hulls. The step sets considered in Examples 2.14 and 2.17 are such that O is in the closure of their convex hulls. Despite having this feature in common, however, the two step sets have very different finiteness properties: the step set from Example 2.14 has the FPP (as far away from the IPP as possible), while that from Example 2.17 has $\pi _X(A)=\infty$ for all $A\in \mathscr {A}_X\setminus \{O\}$ (as close to the IPP as possible without actually attaining it).

2.7 An Implicational Hierarchy

We have now seen several examples of step sets in this paper. These satisfy a range of combinations of the finiteness properties (FPP, IPP, BPP) and geometric conditions (CC, SLC, CC) defined in Sects. 2.2 and 2.3. A natural problem then arises, namely to try and classify all possible combinations. As a first step, Theorem 2.24 below establishes an “implicational hierarchy” of these properties and conditions. This leads to a limit of ten (ostensibly) possible combinations; in Sect. 2.9 we complete the classification by showing that nine of these combinations can be realised by a step set, and proving that the tenth cannot.

We begin with two lemmas.

Lemma 2.22

Let $X\subseteq \mathbb Z_\times ^2$ be an arbitrary step set.

• (i) If X satisfies the LC, then X does not have the IPP.

• (ii) If X satisfies the SLC, then X has the BPP.

• (iii) If X satisfies the CC, then X has the FPP.

Proof

(i). Let $\mathscr {L}$ be a line witnessing the LC, and let $\mathbf{u}$ be a vector perpendicular to $\mathscr {L}$ pointing into the half-plane containing X. So $\mathbf{u}\cdot \overrightarrow{OA}>0$ for all $A\in X$. By linearity, it follows that $\mathbf{u}\cdot \overrightarrow{OA}>0$ whenever $A=A_1+\cdots +A_k$ with $k\ge 1$ and $A_1,\ldots ,A_k\in X$. Thus, there are no non-empty X-walks to O, and so $\pi _X(O)=1$.

(ii). Let $\mathscr {L}$ be a line witnessing the SLC, and let $\mathbf{u}$ be a unit vector perpendicular to $\mathscr {L}$ pointing towards the side of $\mathscr {L}$ containing X. Let $\delta$ be the (perpendicular) distance from O to $\mathscr {L}$, noting that $\mathbf{u}\cdot \overrightarrow{OB}>\delta$ for all $B\in X$. Now let $A\in \mathscr {A}_X$ be arbitrary, and write $\lambda =\mathbf{u}\cdot \overrightarrow{OA}$. Consider an X-walk $w=B_1\cdots B_k$ to A, where $B_1,\ldots ,B_k\in X$. Since $A=B_1+\cdots +B_k$, we have

$$\begin{aligned} \lambda =\mathbf{u}\cdot \overrightarrow{OB}_1+\cdots +\mathbf{u}\cdot \overrightarrow{OB}_k. \end{aligned}$$

(2.3)

Since $\mathbf{u}\cdot \overrightarrow{OB}_i>\delta$ for each i, it follows from (2.3) that $\lambda \ge k\delta$ (with equality only when $k=0$), and so $k\le \frac{\lambda }{\delta }$. We have shown that the length of any X-walk to A is bounded by $\frac{\lambda }{\delta }$. Since $A\in \mathscr {A}_X$ was arbitrary, it follows that X has the BPP.

(iii). Let $\mathcal C$ be a cone witnessing the CC, and suppose $\mathcal C$ is bounded by the lines $\mathscr {L}_1$ and $\mathscr {L}_2$. Let $C\in \mathscr {L}_1$ and $D\in \mathscr {L}_2$ be the points constructed during the proof of Lemma 2.7; cf. Fig. 6. Let $\mathscr {L}$ be the line through C and D, and note that $\mathscr {L}$ witnesses the SLC. Let $\mathbf{u}$ and $\delta$ be as in the proof of (ii) above, defined with respect to $\mathscr {L}$. Further, for $\mu \ge 0$ define the set $X_\mu =\{ {A\in X} : {\mathbf{u}\cdot \overrightarrow{OA}\le \mu } \}$. Now let $A\in \mathscr {A}_X$ be arbitrary. We must show that $\pi _X(A)<\infty$. Let $\lambda =\mathbf{u}\cdot \overrightarrow{OA}$, and suppose $w=B_1\cdots B_k$ is an X-walk to A, where $B_1,\ldots ,B_k\in X$. It follows from (2.3), and the fact that each $\mathbf{u}\cdot \overrightarrow{OB}_i>0$, that $\mathbf{u}\cdot \overrightarrow{OB}_i\le \lambda$ for each i. That is, we must have $B_i\in X_\lambda$ for each i. As in the proof of (ii), we must also have $k\le \frac{\lambda }{\delta }$. The proof of this part will therefore be complete if we can show that $X_\lambda$ is finite. But if we write $\mathscr {L}'$ for the line parallel to $\mathscr {L}$ and $\lambda$ units from O, then $X_\lambda$ is contained in the triangle bounded by the lines $\mathscr {L}_1$, $\mathscr {L}_2$ and $\mathscr {L}'$; since this triangle has finite area, it follows that $X_\lambda$ is finite, as required.$\square$

The next technical lemma concerns a special type of step set, namely one with no steps to the left of the y-axis. It will be used in the proof of the theorem following it, and also in Sect. 2.9. The first part of the lemma has already been used to establish the FPP in Examples 2.13 and 2.14.

Lemma 2.23

Consider a step set $X\subseteq \mathbb N\times \mathbb Z$. For $k\in \mathbb N$ define the sets $Y_k=\{ {y\in \mathbb Z} : {(k,y)\in X} \}$, $Y_k^+=Y_k\cap \mathbb P$ and $Y_k^-=Y_k\cap (-\mathbb P)$.

• (i) If $Y_0^+=\emptyset$, and if $Y_k^+$ is finite for each $k\in \mathbb P$, then X has the FPP.

• (ii) If $Y_0^-\not =\emptyset$, and if $Y_k^+$ is infinite for some $k\in \mathbb P$, then X does not have the BPP.

Proof

(i). For $k\in \mathbb N$, let $X_k=\{k\}\times Y_k$ be the set of all steps from X with x-coordinate k. Let $A=(a,b)\in \mathscr {A}_X$ be arbitrary. Fix some $w\in \Pi _X(A)$, and write $w=A_1\cdots A_l$, where each $A_i=(x_i,y_i)$ belongs to X. For all i, we have $a=x_1+\cdots +x_l\ge x_i\ge 0$, so that each $A_i$ belongs to the subset $Z=X_0\cup X_1\cup \cdots \cup X_a$ of X. This means that $\Pi _X(A)=\Pi _Z(A)$. Let $m=\max (Y_1^+\cup \cdots \cup Y_a^+)$; this is well defined, by the finiteness assumption on the $Y_k^+$. Then the lines with equations $y=(m+1)x$ and $y=(m+2)x$ both witness the LC for Z (see Fig. 9, which only pictures the line $y=(m+1)x$); hence, these lines together witness the CC for Z; it follows from Lemma 2.22(iii) that Z has the FPP. Thus, $\pi _X(A)=\pi _Z(A)<\infty$, as required.

(ii). Let $A=(0,-n)$ where $-n\in Y_0^-$ with $n\in \mathbb P$, and fix some $k\in \mathbb P$ such that $Y_k^+$ is infinite. For each $i\in \{0,1,\ldots ,n-1\}$, let $Y_{k,i}^+=\big \{ {y\in Y_k^+}: {y\equiv i \ ({\text {mod}}n)} \big \}$. Since $Y_k^+$ is infinite, at least one of these subsets must be infinite, say $Y_{k,i}^+$. Write $Y_{k,i}^+ = \{i+b_1n,i+b_2n,\ldots \}$, where $b_1<b_2<\cdots$. For each $q\in \mathbb N$, let $B_q=(k,i+b_qn)\in X$. Then for any $q\in \mathbb N$ we have $B_q+b_qA=(k,i)$, meaning that $B_qA^{b_q}\in \Pi _X(k,i)$. Since $\ell (B_qA^{b_q})=1+b_q$, and since $b_1<b_2<\cdots$, this shows that X does not have the BPP.$\square$

Fig. 9

Schematic diagram of the proof of Lemma 2.23(i). The (closed) blue region contains Z, and the line $y=(m+1)x$ is indicated in red (color figure online)

Here is the main result of this section:

Theorem 2.24

• (i) For an arbitrary step set $X\subseteq \mathbb Z_\times ^2$, we have:

  

  (2.4)

• (ii) For an arbitrary finite step set $X\subseteq \mathbb Z_\times ^2$, all of the implications in (2.4) are reversible; that is, we have:

• (iii) In general, none of the implications in (2.4) are reversible.

Proof

(i). These implications were proved in Lemmas 2.6, 2.8 and 2.22.

(ii). Let $X\subseteq \mathbb Z_\times ^2$ be a finite step set. In light of the previous part, it suffices to show that $\lnot$IPP$\ \Rightarrow \$CC; in fact, by Lemma 2.8(iii), it is enough to show that $\lnot$IPP$\ \Rightarrow \$LC. With this in mind, suppose X does not have the IPP. We must show that X satisfies the LC. This is obvious if X is empty, so suppose otherwise.

Pick an arbitrary point $A\in X$, and let $\mathscr {L}_1$ be the line through O and A; note that O splits $\mathscr {L}_1$ into two open half-lines, $\mathscr {L}_1'$ and $\mathscr {L}_1''$ say, where $A\in \mathscr {L}_1'$. Since X does not have the IPP, Theorem 2.19 gives $X\cap \mathscr {L}_1''=\emptyset$. If X is contained in $\mathscr {L}_1$, then X is contained in $\mathscr {L}_1'$ and so clearly X satisfies the LC. Thus, for the remainder of the proof we assume X is not contained in $\mathscr {L}_1$, and we fix some $B\in X\setminus \mathscr {L}_1$. Let $\mathscr {L}_2$ be the line through O and B, and let $\mathscr {L}_2'$ and $\mathscr {L}_2''$ be the half-lines split by O, with $B\in \mathscr {L}_2'$, and note again that $X\cap \mathscr {L}_2''=\emptyset$. All this is shown in Fig. 10 (left).

The lines $\mathscr {L}_1$ and $\mathscr {L}_2$ define four (open) cones, which we label $\mathcal C_i$ ($i=1,2,3,4$) as also indicated in Fig. 10 (left). If $X\cap \mathcal C_3\not =\emptyset$, say with $C\in X\cap \mathcal C_3$, then we would have $O\in {\text {Conv}}\{A,B,C\}\subseteq {\text {Conv}}(X)$, contradicting Theorem 2.19, so we have $X\cap \mathcal C_3=\emptyset$.

If $X\cap \mathcal C_2$ and $X\cap \mathcal C_4$ are both empty, then clearly X satisfies the LC, so suppose this is not the case. By symmetry, we assume that $X\cap \mathcal C_2\not =\emptyset$. Let $C\in X\cap \mathcal C_2$ be such that $\angle BOC$ is maximal among all points from $X\cap \mathcal C_2$. Let $\mathscr {L}_3$ be the line through O and C, again split into two half-lines $\mathscr {L}_3'$ and $\mathscr {L}_3''$ by O, with $C\in \mathscr {L}_3'$. Again we have $X\cap \mathscr {L}_3''=\emptyset$. The line $\mathscr {L}_3$ splits $\mathcal C_2$ and $\mathcal C_4$ into (open) cones $\mathcal C_2',\mathcal C_2''$ and $\mathcal C_4',\mathcal C_4''$ as shown in Fig. 10 (middle).

By the maximality of $\angle BOC$, we have $X\cap \mathcal C_2''=\emptyset$. If $X\cap \mathcal C_4''\not =\emptyset$, say with $D\in X\cap \mathcal C_4''$, then we would have $O\in {\text {Conv}}\{B,C,D\}\subseteq {\text {Conv}}(X)$, again contradicting Theorem 2.19, so we have $X\cap \mathcal C_4''=\emptyset$. If also $X\cap \mathcal C_4'=\emptyset$, then clearly X satisfies the LC, so suppose this is not the case. Let $D\in X\cap \mathcal C_4'$ be such that $\angle AOD$ is maximal among all points from $X\cap \mathcal C_4'$. Then the line $\mathscr {L}$ bisecting $\mathscr {L}_3''$ and $\overrightarrow{OD}$ witnesses the LC; see Fig. 10 (right).

(iii). The step set considered in Example 2.13 satisfies the SLC but not the CC; this shows that SLC$\ \not \Rightarrow \$CC in general. Similarly, Example 2.17 shows that LC$\ \not \Rightarrow \$SLC and also that $\lnot$IPP$\ \not \Rightarrow \$BPP, while Example 2.3 shows that BPP$\ \not \Rightarrow \$FPP. This takes care of the “horizontal” implications in (2.4). The “vertical” implications may be treated all at once by noting that the step set from Example 2.14 has the FPP (as follows from Lemma 2.23(i)) but does not satisfy the LC.$\square$

Fig. 10

The points A, B, C, D and lines $\mathscr {L}_1,\mathscr {L}_2,\mathscr {L}_3,\mathscr {L}$ constructed during the proof of Theorem 2.24(ii)

The following simple consequence of Theorem 2.24(ii) seems worth singling out; it gives a natural dichotomy for finite step sets.

Corollary 2.25

If $X\subseteq \mathbb Z_\times ^2$ is an arbitrary finite step set, then X has either the FPP or the IPP. $\square$

2.8 Groups

Theorem 2.19 shows (among other things) that for a step set $X\subseteq \mathbb Z_\times ^2$, the monoid $\mathscr {A}_X$ contains non-trivial units if and only if the origin O is contained in ${\text {Conv}}(X)$, the convex hull of X. In the current section we consider the situation of when $\mathscr {A}_X$ is a group (i.e., all elements of $\mathscr {A}_X$ are units). Note that $\mathscr {A}_X$ can contain non-trivial units without being a group; for instance, if X is the step set from Example 2.2(ii), then $\mathscr {A}_X=\mathbb N\times \mathbb Z$ has group of units $\{0\}\times \mathbb Z$ (cf. Fig. 2 (right)), but note that O is on the boundary of ${\text {Conv}}(X)$ in this example. This suggests that there might be a subtle topological condition at play, and indeed Theorem 2.30 below demonstrates that this is the case. But first we prove Theorem 2.27, which has a more geometrical flavour, and involves a Weak Line Condition, defined below.

In what follows, for an arbitrary subset U of $\mathbb R^2$, we write $\overline{U}$ and ${\text {Rel-Int}}(U)$ for the closure and relative interior of U, respectively. The latter is the (ordinary) interior of U relative to the smallest affine subspace of $\mathbb R^2$ containing U; when $|U|\ge 2$, this subspace is either $\mathbb R^2$ or a line. We use the relative interior, because we wish to speak of sets such as ${\text {Rel-Int}}({\text {Conv}}(A,B))$ for distinct points $A,B\in \mathbb R^2$, which consists of all points on the line segment strictly between A and B, whereas the interior of ${\text {Conv}}(A,B)$ is empty.

Lemma 2.26

Let $X\subseteq \mathbb Z_\times ^2$ be an arbitrary step set, and let $A\in X$. If there exist (not necessarily distinct) points $B,C\in X$ such that $O\in {\text {Rel-Int}}({\text {Conv}}(A,B,C))$, then A is a unit of $\mathscr {A}_X$.

Proof

First we consider the case that $B=C$. Since $O\in {\text {Rel-Int}}({\text {Conv}}(A,B))$, we have $\angle AOB=\pi$. By Proposition 2.11(iii), the submonoid of $\mathscr {A}_X$ generated by $\{A,B\}$ is a group; in particular, A is invertible in this submonoid, and hence in $\mathscr {A}_X$ itself.

From now on, we assume that $B\not =C$. Following the proof of Theorem 2.19, we have ${O=xA+yB+zC}$ where $x,y,z\in \mathbb N$ are not all zero. If $x\not =0$, then it immediately follows that A is invertible (with inverse $(x-1)A+yB+zC$). If $x=0$, then $O\in {\text {Rel-Int}}({\text {Conv}}(B,C))$, and so B and C must be on a line $\mathscr {L}$ through O, with O in between; in this case, since $O\in {\text {Rel-Int}}({\text {Conv}}(A,B,C))$, A must also lie on $\mathscr {L}$ (or else O would be on the boundary of ${\text {Conv}}(A,B,C)$). But then O belongs either to ${\text {Rel-Int}}({\text {Conv}}(A,B))$ or to ${\text {Rel-Int}}({\text {Conv}}(A,C))$. As in the first paragraph it follows that A is a unit.$\square$

For the next statement, and for later use, we say a step set $X\subseteq \mathbb Z_\times ^2$ satisfies the Weak Line Condition (WLC) if it is contained in the closure of a half-plane determined by a line through the origin. Clearly the LC implies the WLC, but the converse does not hold in general; cf. Example 2.2(ii).

Theorem 2.27

Let $X\subseteq \mathbb Z_\times ^2$ be an arbitrary step set.

• (i) If X is empty, then $\mathscr {A}_X$ is a trivial group.

• (ii) If X is non-empty, and is contained in a line $\mathscr {L}$ through the origin, then $\mathscr {A}_X$ is a group if and only if X contains points from $\mathscr {L}$ on both sides of the origin; in this case, $\mathscr {A}_X$ is isomorphic to $(\mathbb Z,+)$.

• (iii) If X is not contained in any line through the origin, then $\mathscr {A}_X$ is a group if and only if X does not satisfy the WLC; in this case, $\mathscr {A}_X$ is isomorphic to $(\mathbb Z^2,+)$.

Proof

By standard algebraic facts, any subgroup G of $(\mathbb Z^2,+)$ is isomorphic to $(\mathbb Z^d,+)$, where d is the dimension of the vector space spanned by G. Thus, with (i) being clear, it suffices to prove the “if and only if” statements in (ii) and (iii).

(ii). Suppose $X\not =\emptyset$ is contained in a line $\mathscr {L}$ through O, which splits $\mathscr {L}$ into two open half-lines $\mathscr {L}'$ and $\mathscr {L}''$.

If X is contained in $\mathscr {L}'$ say, then X clearly satisfies the LC, and hence does not have the IPP, by Theorem 2.24(i); but then Theorem 2.19 says that $\mathscr {A}_X$ has no non-trivial units; since $X\not =\emptyset$, it follows that $\mathscr {A}_X$ is not a group.

To prove the other implication, suppose X contains points from both $\mathscr {L}'$ and $\mathscr {L}''$. To prove $\mathscr {A}_X$ is a group, it suffices to show that all elements of X are invertible. So let $A\in X$ be arbitrary. Renaming if necessary, we may assume that $A\in \mathscr {L}'$. By assumption, there exists $B\in X\cap \mathscr {L}''$. But then $O\in {\text {Rel-Int}}({\text {Conv}}(A,B))$, and hence A is a unit by Lemma 2.26.

(iii). Suppose X is not contained in any line through the origin.

First suppose X satisfies the WLC, as witnessed by a line $\mathscr {L}$ through the origin. Let $\mathbf{u}$ be a vector perpendicular to $\mathscr {L}$, pointing towards the half-plane containing points from X (exactly one such half-plane does contain points from X, as X is not contained in $\mathscr {L}$). The WLC says that $\mathbf{u}\cdot \overrightarrow{OA}\ge 0$ for all $A\in X$; by linearity, it follows that $\mathbf{u}\cdot \overrightarrow{OA}\ge 0$ for all $A\in \mathscr {A}_X$. Since X is not contained in $\mathscr {L}$, there exists $B\in X$ such that $\mathbf{u}\cdot \overrightarrow{OB}>0$. But then for any $A\in \mathscr {A}_X$, we have $\mathbf{u}\cdot (\overrightarrow{OA}+\overrightarrow{OB})\ge \mathbf{u}\cdot \overrightarrow{OB}>0$, so that $A+B\not =O$; this shows that B is not invertible, and hence $\mathscr {A}_X$ is not a group.

Conversely, suppose X does not satisfy the WLC. To show that $\mathscr {A}_X$ is a group, it suffices to show that each element of X is a unit. With this in mind, fix some $A\in X$. Let $\mathscr {L}$ be the line through O and A, split by O into two open half-lines $\mathscr {L}'$ and $\mathscr {L}''$ with $A\in \mathscr {L}'$. If $X\cap \mathscr {L}''\not =\emptyset$, then again $O\in {\text {Rel-Int}}({\text {Conv}}(A,B))$ for any $B\in X\cap \mathscr {L}''$, and Lemma 2.26 says that A is invertible. From now on we assume that $X\cap \mathscr {L}''=\emptyset$.

Let the two (open) half-planes bounded by $\mathscr {L}$ be $H_1$ and $H_2$, as shown in Fig. 11 (left). Since X does not satisfy the WLC, $X\cap H_1$ and $X\cap H_2$ are both non-empty. Let

$$\begin{aligned} \beta = \sup \{ {\angle AOB} : {B\in X\cap H_1} \} \qquad \text {and}\qquad \gamma = \sup \{ {\angle AOC} : {C\in X\cap H_2} \}. \end{aligned}$$

Here $\angle AOB$ and $\angle AOC$ denote non-reflex angles, and we note that $\beta ,\gamma$ are well defined since the relevant sets are bounded above by $\pi$; this also guarantees that $0<\beta ,\gamma \le \pi$. Either there exists $B\in X\cap H_1$ such that $\angle AOB=\beta$ or else there is a sequence of points $B_1,B_2,\ldots \in X\cap H_1$ such that $\lim _{n\rightarrow \infty }\angle AOB_n=\beta$; if $\beta =\pi$, then the latter must be the case. A similar statement holds for $\gamma$.

Fix arbitrary points $P\in H_1\cup \mathscr {L}''$ and $Q\in H_2\cup \mathscr {L}''$ such that $\angle AOP=\beta$ and $\angle AOQ=\gamma$. (Note that P and Q need not belong to X, or even to $\mathbb Z^2$. Note also that we would need $P\in \mathscr {L}''$ if $\beta =\pi$, with a similar statement for Q.) Let $\mathscr {L}_1$ be the line through O and P, split by O into open half-lines $\mathscr {L}_1'$ and $\mathscr {L}_1''$ with $P\in \mathscr {L}_1'$. Let $\mathscr {L}_2$ be the line through O and Q, split by O into open half-lines $\mathscr {L}_2'$ and $\mathscr {L}_2''$ with $Q\in \mathscr {L}_2'$. This is all shown in Fig. 11 (middle). The half-lines $\mathscr {L}',\mathscr {L}_1',\mathscr {L}_2'$ bound three open regions, which we denote by $R_1,R_2,R_3$ as also indicated in Fig. 11 (middle). (These regions are either cones or half-planes, depending on whether $\beta$ and/or $\gamma$ equals $\pi$; note that $R_3=\emptyset$ if $\beta =\gamma =\pi$.)

By construction, X is contained in $\mathbb R^2\setminus R_3$. Thus, since X does not satisfy the WLC, we must have $\beta +\gamma >\pi$. For convenience, let $\delta =(\beta +\gamma )-\pi$, so $\delta >0$. As noted above, there exist points $B\in X\cap (R_1\cup \mathscr {L}_1')$ and $C\in X\cap (R_2\cup \mathscr {L}_2')$ such that $\angle AOB>\beta -\frac{\delta }{2}$ and $\angle AOC>\gamma -\frac{\delta }{2}$; write $\beta '=\angle AOB$ and $\gamma '=\angle AOC$. This is all pictured in Fig. 11 (right). Then $\beta '+\gamma '>\beta +\gamma -\delta =\pi$. Together with $\beta '<\pi$ and $\gamma '<\pi$ (which follow from $B\in H_1$ and $C\in H_2$), it follows that $O\in {\text {Rel-Int}}({\text {Conv}}(A,B,C))$, and so A is a unit by Lemma 2.26.$\square$

Fig. 11

The points A, B, C, P, Q and lines $\mathscr {L},\mathscr {L}_1,\mathscr {L}_2$ constructed during the proof of Theorem 2.27(iii)

Remark 2.28

For an arbitrary step set X, the implications from Theorem 2.24(i) may be extended as follows:

Indeed:

• (i) LC$\ \Rightarrow \$WLC has already been mentioned and is obvious.

• (ii) $\lnot$IPP$\ \Rightarrow \$ $\mathscr {A}_X\not \cong (\mathbb Z^2,+)$ follows from Theorem 2.19.

• (iii) WLC$\ \Rightarrow \$ $\mathscr {A}_X\not \cong (\mathbb Z^2,+)$ follows from all three parts of Theorem 2.27: if X satisfies the WLC, then either X is empty, or is non-empty but contained in a line through O, or is not contained in any such line; in these cases, $\mathscr {A}_X$ is either a trivial group, a group isomorphic to $(\mathbb Z,+)$, or not a group at all.

• (iv) $\lnot$WLC$\ \Rightarrow \$ $\mathscr {A}_X\cong (\mathbb Z^2,+)$ holds, since if X does not satisfy the WLC, then certainly X is not contained in any line through O, in which case Theorem 2.27(iii) says that $\mathscr {A}_X\cong (\mathbb Z^2,+)$.

The implications (i) and (ii) are not reversible in general, even for finite X; cf. Example 2.2(ii).

Remark 2.29

If a step set X satisfies the WLC but not the LC, and is not contained in a line through O, then the structure of $\mathscr {A}_X$ could be simple or complicated. For example, if $X=\{N,E,S\}$ as in Example 2.2(ii), then $\mathscr {A}_X=\mathbb N\times \mathbb Z$. But if $U\subseteq \mathbb P$ is arbitrary, then with $X=\{N,S\}\cup \{ {(u,0)} : {u\in U} \}$ we have $\mathscr {A}_X=M\times \mathbb Z$ where $M={\text {Mon}}\langle U\rangle$ is the submonoid of $\mathbb N$ generated by U; we have already noted that the study of such monoids is a considerable topic [2, 18]. It is not hard to devise more complicated examples.

Here is an alternative characterisation of step sets X for which $\mathscr {A}_X$ is a group. In the proof, we write ${\text {Int}}(U)$ for the (ordinary) interior of a subset U of $\mathbb R^2$. It is a basic fact that $U_1\subseteq U_2$ implies ${\text {Int}}(U_1)\subseteq {\text {Int}}(U_2)$, although the analogous implication does not hold for relative interiors.

Theorem 2.30

Let $X\subseteq \mathbb Z_\times ^2$ be an arbitrary non-empty step set. Then $\mathscr {A}_X$ is a group if and only if ${O\in {\text {Rel-Int}}({\text {Conv}}(X))}$.

Proof

We split the proof up into three cases.

Case 1. Suppose first that X is contained in some line $\mathscr {L}$ through O. Then by Theorem 2.27(ii), $\mathscr {A}_X$ is a group if and only if X contains points from $\mathscr {L}$ on both sides of O; since $X\subseteq \mathscr {L}$, this latter condition is clearly equivalent to ${O\in {\text {Rel-Int}}({\text {Conv}}(X))}$.

Case 2. Next suppose X is contained in some line $\mathscr {L}$ not through O. Then the line through O parallel to $\mathscr {L}$ witnesses the LC. It follows from Theorem 2.24(i) that X does not have the IPP, and then from Theorem 2.19 that $\mathscr {A}_X$ contains no non-trivial units; since X is non-empty we deduce that $\mathscr {A}_X$ is not a group. Since X does not have the IPP, Theorem 2.19 also tells us that $O\not \in {\text {Conv}}(X)$, so certainly $O\not \in {\text {Rel-Int}}({\text {Conv}}(X))$.

Case 3. Finally, suppose X is not contained in any line. This means that X is two-dimensional, and so too therefore is ${\text {Conv}}(X)$; consequently, we have ${\text {Rel-Int}}({\text {Conv}}(X))={\text {Int}}({\text {Conv}}(X))$.

Suppose first that $\mathscr {A}_X$ is not a group. Then by Theorem 2.27(iii), X satisfies the WLC, so that $X\subseteq \overline{H}$ for some (open) half-plane H bounded by a line through O. But then

$$\begin{aligned} {\text {Rel-Int}}({\text {Conv}}(X))={\text {Int}}({\text {Conv}}(X))\subseteq {\text {Int}}({\text {Conv}}(\overline{H}))={\text {Int}}(\overline{H})=H. \end{aligned}$$

Since $O\not \in H$, it follows that $O\not \in {\text {Rel-Int}}({\text {Conv}}(X))$.

Conversely, suppose $\mathscr {A}_X$ is a group. Then by Theorem 2.27(iii), X does not satisfy the WLC. Let $A\in X$ be arbitrary, and let $\mathscr {L}$ be the line through O and A, split into $\mathscr {L}'$ and $\mathscr {L}''$ by O, with $A\in \mathscr {L}'$. If $X\cap \mathscr {L}''=\emptyset$, then as in the proof of Theorem 2.27(iii), O is in the interior of the (non-degenerate) triangle $\triangle ABC={\text {Conv}}(A,B,C)$ for some $B,C\in X$, and so

$$\begin{aligned} O\in {\text {Int}}({\text {Conv}}(A,B,C))\subseteq {\text {Int}}({\text {Conv}}(X))={\text {Rel-Int}}({\text {Conv}}(X)). \end{aligned}$$

Suppose now that $X\cap \mathscr {L}''\not =\emptyset$, say with $D\in X\cap \mathscr {L}''$; see Fig. 12. Let the half-planes bounded by $\mathscr {L}$ be $H_1$ and $H_2$. Since X does not satisfy the WLC, there exist $E\in X\cap H_1$ and $F\in X\cap H_2$. But then the (non-degenerate) triangles $\triangle ADE={\text {Conv}}(A,D,E)$ and $\triangle ADF={\text {Conv}}(A,D,F)$ are both contained in ${\text {Conv}}(A,D,E,F)$. Since O is on the common side of these two triangles, we have

$$\begin{aligned} O\in {\text {Int}}({\text {Conv}}(A,D,E,F))\subseteq {\text {Int}}({\text {Conv}}(X))={\text {Rel-Int}}({\text {Conv}}(X)). \end{aligned}$$

$\square$

Fig. 12

The points A, D, E, F and line $\mathscr {L}$ constructed during the proof of Theorem 2.30

Remark 2.31

One may compare Theorems 2.27 and 2.30 with the various examples considered in Sects. 2.1 and 2.5. In particular, for the step set X from Example 2.2(ii), O belongs to ${\text {Conv}}(X)$ but not to ${\text {Rel-Int}}({\text {Conv}}(X))$; the monoid $\mathscr {A}_X$ has non-trivial units but is not a group, and X satisfies the WLC.

2.9 Possible Combinations of Finiteness Properties and Geometric Conditions

Theorem 2.24(i) describes a hierarchy among the various geometric conditions (CC, SLC, LC) and finiteness properties (FPP, BPP, $\lnot$IPP) associated to step sets. Specifically, the implications in (2.4) restrict the possible combinations of these conditions/properties that a given step set could have. For a step set $X\subseteq \mathbb Z_\times ^2$, consider the $2\times 3$ matrix of Y’s and N’s indicating whether X has each of these conditions/properties:

(2.5)

Ostensibly, by Theorem 2.24(i), there are ten possibilities, and these are all enumerated in Table 1. Of course (I) and (X) are the only combinations that can actually occur for finite step sets, by Theorem 2.24(ii). Intriguingly, it turns out that for infinite X, all but one of combinations (I)–(X) can occur. We show in Proposition 2.36 below that combination (VIII) never occurs. The remaining combinations are exemplified in various step sets, as listed in the final column of Table 1.

Combination (V) provided the greatest challenge, and for a long time, we were unable to determine whether or not a step set could actually have this combination. We were able to show that the existence of such step sets was equivalent to the existence of certain sequences of real numbers, but were unable to determine whether such sequences could exist either. In Appendix A, we present an ingenious construction due to Stewart Wilcox showing that such sequences, and hence such step sets, do indeed exist.

Table 1 The combinations of finiteness properties and geometric conditions on step sets that are ostensibly possible after taking Theorem 2.24(i) into account; cf. (2.5)

Here is a step set with combination (IX):

Example 2.32

It is easy to check that the step set $X=\{(0,-1)\}\cup (\{1\}\times \mathbb N)$ does not satisfy the LC. By Lemma 2.23(ii) X does not have the BPP, and by Theorem 2.19 it does not have the IPP.

Here is a step set with combination (IV):

Example 2.33

For $p\in \mathbb N$, let $\mathscr {L}_p$ and $\mathscr {L}'_p$ be the lines with equations $y=\sqrt{2}(x-\sqrt{2}p)$ and $y=-\sqrt{2}p$, respectively. (Any irrational number greater than 1 could be used in place of $\sqrt{2}$.) For $p\in \mathbb N$, let $R_p$ be the open region bounded by the lines $\mathscr {L}_p$ and $\mathscr {L}_{p+1}$. For $p,q\in \mathbb N$, let $R_{p,q}$ be the open region bounded by the lines $\mathscr {L}_p$, $\mathscr {L}_{p+1}$, $\mathscr {L}_q'$ and $\mathscr {L}_{q+1}'$. So the sets $R_{p,q}$, $p,q\in \mathbb N$, are congruent (open) rhombuses, and they each contain at least one lattice point (as their height and base-length are both greater than 1); for each $p,q\in \mathbb N$ we fix one such point $A_{p,q}\in \mathbb Z^2\cap R_{p,q}$. We now define the step set

$$\begin{aligned} X = X_1\cup X_2 \qquad \text {where}\qquad X_1 = R_0\cap \mathbb P^2 \quad \text {and}\quad X_2 = \{ {A_{p,p^2}} : {p\in \mathbb N} \}. \end{aligned}$$

This is all shown in Fig. 13, which is drawn to scale. We claim that:

• (i) X satisfies the LC,

• (ii) X does not satisfy the SLC,

• (iii) X has the FPP.

Clearly $\mathscr {L}_0$ witnesses the LC, so (i) is true. For (ii), first note that the line $x=0$ obviously does not witness the LC (note that $A_{2,4}=(-1,-6)$ is to the left of $x=0$; cf. Fig. 13). Now consider the line $\mathscr {L}$ with equation $y=\alpha x$, where $\alpha$ is any real number other than $\sqrt{2}$. If $\alpha >\sqrt{2}$, then all of $X_1$ is to the right of $\mathscr {L}$, and infinitely many points from $X_2$ are to the left (as the points from $X_2$ approximately trace a kind of “skew parabola”). If $0\le \alpha <\sqrt{2}$, then all of $X_2$ is below $\mathscr {L}$, and infinitely many points from $X_1$ are above (cf. Lemma 2.15 and Remark 2.16). If $\alpha <0$, then all of $X_1$ is above $\mathscr {L}$, and infinitely many points from $X_2$ are below. It follows that $\mathscr {L}_0$ is the only line witnessing the LC. Since $X_1$ contains points arbitrarily close to $\mathscr {L}_0$ (again, cf. Lemma 2.15 and Remark 2.16) no line parallel to $\mathscr {L}_0$ witnesses the SLC. Together with Lemma 2.9(ii), it therefore follows that X does not satisfy the SLC, completing the proof of (ii).

To prove (iii), we first introduce some more notation. Let $\mathbf{u}$ be a vector perpendicular to $\mathscr {L}_0$, pointing into the half-plane containing X (see Fig. 13). Since $\mathbf{u}\cdot \overrightarrow{OA}>0$ for all $A\in X$, this is also true of all $A\in \mathscr {A}_X\setminus \{O\}$. For $p\in \mathbb N$, let $\lambda _p=\mathbf{u}\cdot \overrightarrow{OA}_{p,p^2}$. By construction (cf. Fig. 13) we have

$$\begin{aligned} 0<\lambda _0<\lambda _1<\lambda _2<\cdots \qquad \text {and}\qquad \lim _{p\rightarrow \infty }\lambda _p=\infty . \end{aligned}$$

(2.6)

Now let $A\in \mathscr {A}_X$ be arbitrary. We must show that $\pi _X(A)<\infty$. Because X satisfies the LC, we have $\pi _X(O)=1$ (cf. Theorem 2.24(i) and Lemma 2.5), so we will assume that $A\not =O$. Define $\lambda =\mathbf{u}\cdot \overrightarrow{OA}>0$, and let $q={\max \{ {p\in \mathbb N} : {\lambda _p\le \lambda } \}}$; this is well defined because of (2.6). Fix some $w\in \Pi _X(A)$, and write $w=B_1\cdots B_k$, where $B_1,\ldots ,B_k\in X$. Also write $B_i=(x_i,y_i)$ for each i. Let $I=\{ {i\in \{1,\ldots ,k\}} : {B_i\in X_1} \}$ and $J=\{ {j\in \{1,\ldots ,k\}} : {B_j\in X_2} \}$, and write $I=\{i_1,\ldots ,i_l\}$ and $J=\{j_1,\ldots ,j_m\}$ where $i_1<\cdots <i_l$ and $j_1<\cdots <j_m$. Define the words

$$\begin{aligned} s=B_{i_1}\cdots B_{i_l} \qquad \text {and}\qquad t=B_{j_1}\cdots B_{j_m}. \end{aligned}$$

We will show that:

• (iv) there are only finitely many possibilities for t, and

• (v) given some such t, there are only finitely many possibilities for s.

Since w is obtained by “shuffling” s and t together, and since there are only finitely many ways to do this, it will follow that there are only finitely many possibilities for w: i.e., that $\pi _X(A)$ is finite. That is, the proof of (iii) above will be complete if we can prove (iv) and (v).

We begin with (iv). For each $j\in J$, let $p_j\in \mathbb N$ be such that $B_j=A_{p_j,p_j^2}$. Now,

$$\begin{aligned} \lambda&= \mathbf{u}\cdot \overrightarrow{OA} .0= \mathbf{u}\cdot (\overrightarrow{OB}_1 +\cdots +\overrightarrow{OB}_k) \\&\qquad \qquad \quad \ge \mathbf{u}\cdot (\overrightarrow{OB}_{j_1}+\cdots +\overrightarrow{OB}_{j_m}) = \lambda _{p_{j_1}}+\cdots +\lambda _{p_{j_m}} \ge m\lambda _0, \end{aligned}$$

so that $\ell (t) = m\le \frac{\lambda }{\lambda _0}$. But also for any $j\in J$, we have

$$\begin{aligned} \lambda \ge \lambda _{p_{j_1}}+\cdots +\lambda _{p_{j_m}} \ge \lambda _{p_j}, \end{aligned}$$

so that $p_j\le q$ for all $j\in J$ (q was defined just after (2.6)). The previous two conclusions show that t has length at most $\frac{\lambda }{\lambda _0}$, and is a word over $\{A_{0,0},A_{1,1},\ldots ,A_{q,q^2}\}$. Since $\lambda$, $\lambda _0$ and q depend only on A (and X), this completes the proof of item (iv).

To prove (v), first define the points

$$\begin{aligned} S=\alpha _X(s)=B_{i_1}+\cdots +B_{i_l} \qquad \text {and}\qquad T=\alpha _X(t)=B_{j_1}+\cdots +B_{j_m}, \end{aligned}$$

noting that $A=S+T$. Write $A=(a,b)$, $S=(c,d)$ and $T=(e,f)$. Now, $d=y_{i_1}+\cdots +y_{i_l}\ge l$, as the y-coordinate of each element from $X_1$ is at least 1. Let r be the minimum y-coordinate of all the points from $\{A_{0,0},A_{1,1},\ldots ,A_{q,q^2}\}$; since q depends only on A, so too does r. Then since each $B_j$ ($j\in J$) belongs to $\{A_{0,0},A_{1,1},\ldots ,A_{q,q^2}\}$, we have $f =y_{j_1}+\cdots +y_{j_m}\ge mr$. Together with $d\ge l$ and $b=d+f$, it follows that

$$\begin{aligned} l\le d=b-f\le b-mr. \end{aligned}$$

Since b depends only on the point A, and m and r only on the word t, it follows that the length of s is bounded above by a constant depending only on A and t. Also, since $(a-e,b-f)=A-T=S=B_{i_1}+\cdots +B_{i_l}$, and since $y_i\ge 1$ for each $i\in I$ (as $B_i\in X_1$), it follows that $b-f=y_{i_1}+\cdots +y_{i_l}\ge y_i$ for each $i\in I$. Since there are only finitely many elements of $X_1$ with y-coordinate at most $b-f$, it follows that t is a word over the finite subset $\{ {B\in X_1} : {\text {the}~y\text {-coordinate of}~B~\text {is at most}~b-f} \}$. Since we have already shown that the length of t is bounded above by $b-mr$, this completes the proof of (v), and indeed (as noted above) of (iii).

Fig. 13

The step set $X=X_1\cup X_2$ from Example 2.33 (drawn to scale). Points from $X_1$ and $X_2$ are in the regions shaded red and blue, respectively

With combination (V) being dealt with in Appendix A, our final task for this section is to show that combination (VIII) is impossible. This will be achieved in Proposition 2.36 below, where we show that any step set $X\subseteq \mathbb Z_\times ^2$ with the BPP but not the LC must also have the FPP; we first demonstrate this in the special case that X contains no steps to the left of the y-axis.

Lemma 2.34

If a step set $X\subseteq \mathbb N\times \mathbb Z$ does not satisfy the LC but does have the BPP, then X has the FPP.

Proof

Suppose $X\subseteq \mathbb N\times \mathbb Z$ does not satisfy the LC but does have the BPP. Define the sets $Y_k$, $Y_k^+$ and $Y_k^-$, for each $k\in \mathbb N$, as in Lemma 2.23. Since X does not satisfy the LC, X must contain at least one point from the y-axis; by symmetry, we assume this point is on the negative part of the y-axis. If X also contained a point from the positive part of the y-axis, then X would have the IPP by Theorem 2.19, so this must not be the case (as BPP$\ \Rightarrow \$ $\lnot$IPP, by Theorem 2.24(i)). So far we have shown that $Y_0^-\not =\emptyset$ and $Y_0^+=\emptyset$. If $Y_k^+$ was infinite for some $k\in \mathbb P$, then X would not have the BPP, by Lemma 2.23(ii), a contradiction; so it follows that $Y_k^+$ is finite for all $k\in \mathbb P$. But then Lemma 2.23(i) now tells us that X has the FPP. $\square$

To extend Lemma 2.34 to arbitrary step sets (in Proposition 2.36), we need the next lemma, which characterises the lines with a given rational slope and containing lattice points. In the proof, and later, we use the well-known fact that the (perpendicular) distance of a point (u, v) to the line with equation $ax+by+c=0$ is equal to

$$\begin{aligned} \frac{|au+bv+c|}{\sqrt{a^2+b^2}}. \end{aligned}$$

(2.7)

Lemma 2.35

Let $\mathscr {L}$ be the line with equation $ax+by=0$, where $a,b\in \mathbb Z$ are not both zero and $\gcd (a,b)=1$. Then the lines parallel to $\mathscr {L}$ containing lattice points are precisely the lines parallel to $\mathscr {L}$ whose (perpendicular) distance from $\mathscr {L}$ is an integer multiple of $\frac{1}{\sqrt{a^2+b^2}}$.

Proof

Throughout the proof, we write $\delta =\frac{1}{\sqrt{a^2+b^2}}$. First suppose $\mathscr {L}'$ is parallel to $\mathscr {L}$ and contains some lattice point $(u,v)\in \mathbb Z^2$. By (2.7), the distance from (u, v) to $\mathscr {L}$ (and hence the distance from $\mathscr {L}'$ to $\mathscr {L}$) is equal to $\frac{|au+bv|}{\sqrt{a^2+b^2}}$, which is an integer multiple of $\delta$.

Conversely, let $k\in \mathbb P$ be arbitrary; there are two lines parallel to $\mathscr {L}$ a distance of $k\delta$ from $\mathscr {L}$; to show these both contain lattice points, it suffices to show that there are lattice points on both sides of $\mathscr {L}$ a distance of $k\delta$ from $\mathscr {L}$. Since $\gcd (a,b)=1$, there exist integers $u,v\in \mathbb Z$ such that $au+bv=1$. Using (2.7) again, we see that the points $\pm (ku,kv)$ are both a distance of $k\delta$ from $\mathscr {L}$, as required. $\square$

Here is the promised result showing that combination (VIII) is impossible; cf. Table 1.

Proposition 2.36

If a step set $X\subseteq \mathbb Z_\times ^2$ does not satisfy the LC but does have the BPP, then X has the FPP.

Proof

Suppose $X\subseteq \mathbb Z_\times ^2$ does not satisfy the LC but does have the BPP. Because of the BPP, Theorem 2.24(i) says that X does not have the IPP.

First note that X satisfies the WLC, as defined in Section 2.8; indeed, if it did not, then as in Remark 2.28, $\mathscr {A}_X$ would be a group isomorphic to $(\mathbb Z^2,+)$, in which case $\mathscr {A}_X$ would contain non-trivial units, and so X would satisfy the IPP by Theorem 2.19, a contradiction. So let $\mathscr {L}_0$ be a line witnessing the WLC, and let H be the half-plane bounded by $\mathscr {L}_0$ such that $X\subseteq \overline{H}$. Since X does not satisfy the LC, we must have $X\cap \mathscr {L}_0\not =\emptyset$. See Fig. 14, which displays this, and all the coming information about X.

Since $\mathscr {L}_0$ also contains the origin, it has rational (or vertical) slope, so we may assume its equation is $ax+by=0$, where $a,b\in \mathbb Z$ are not both zero and $\gcd (a,b)=1$. Put $\delta =\frac{1}{\sqrt{a^2+b^2}}$. Let $\mathbf{u}$ be a vector of length $\delta$ perpendicular to $\mathscr {L}_0$ and pointing into H. For $p\in \mathbb P$, let $\mathscr {L}_p$ be the line defined by $\mathscr {L}_p=p\mathbf{u}+\mathscr {L}_0$; so $\mathscr {L}_p$ is parallel to $\mathscr {L}$, is contained in H, and is a distance of $p\delta$ from $\mathscr {L}_0$. By Lemma 2.35, and since $X\subseteq \overline{H}\cap \mathbb Z^2$, every element of X is contained in one of the lines $\mathscr {L}_p$ ($p\in \mathbb N$).

Let $\mathscr {L}_0'$ be the line through O perpendicular to $\mathscr {L}_0$; so $\mathscr {L}_0'$ has equation $bx-ay=0$. Let $\mathbf{v}$ be a vector of length $\delta$ and perpendicular to $\mathscr {L}_0'$ (pointing in either of the two possible directions). For $q\in \mathbb Z$, let $\mathscr {L}_q'$ be the line defined by $\mathscr {L}_q'=\mathscr {L}_0'+q\mathbf{v}$. Again, by Lemma 2.35, each element of X lies on one of the lines $\mathscr {L}_q'$ ($q\in \mathbb Z$).

So far we have seen that every step from X is on the intersection of $\mathscr {L}_p$ and $\mathscr {L}_q'$ for some $p\in \mathbb N$ and $q\in \mathbb Z$; this point is $pU+qV$, where $U,V\in \mathbb R^2$ are such that $\mathbf{u}=\overrightarrow{OU}$ and $\mathbf{v}=\overrightarrow{OV}$. (The points U and V do not necessarily belong to X, or even to $\mathbb Z^2$.) Write

$$\begin{aligned} Y=\big \{ {(p,q)\in \mathbb N\times \mathbb Z}: {pU+qV\in X} \big \}, \end{aligned}$$

and define the linear transformation $\phi :\mathbb R^2\rightarrow \mathbb R^2$ by $\phi (U)=(1,0)$ and $\phi (V)=(0,1)$. Note that $\phi$ acts geometrically on $\mathbb R^2$ by first rotating $\mathscr {L}_0$ and $\mathscr {L}_0'$ onto the y- and x-axes, respectively, and then scaling down by a factor of $\delta$ (and then possibly reflecting in the x-axis, depending on the direction chosen for $\mathbf{v}$). Also, $\phi$ maps X bijectively onto Y, and $\mathscr {A}_X$ isomorphically onto $\mathscr {A}_Y$; further, it is clear that the induced isomorphism $\mathscr {F}_X\rightarrow \mathscr {F}_Y$ maps $\Pi _X(A)$ bijectively onto $\Pi _Y(\phi (A))$ for all $A\in \mathscr {A}_X$; it follows that Y has the BPP (since X does), and that X has the FPP if and only if Y does. Moreover, given the above geometric interpretation of $\phi$, it is clear that if a line $\mathscr {L}$ witnessed the LC for Y, then the line $\phi ^{-1}(\mathscr {L})$ would witness the LC for X; since X does not satisfy the LC, it follows that Y does not either. Thus, since $Y\subseteq \mathbb N\times \mathbb Z$, it follows from Lemma 2.34 that Y has the FPP; as noted above, it follows that X too has the FPP.$\square$

Fig. 14

Schematic diagram of the proof of Proposition 2.36

3 Constrained Walks

3.1 Definitions and Basic Examples

Suppose now that we have a step set $X\subseteq \mathbb Z_\times ^2$, and that we wish to enumerate X-walks that stay within a certain region of the plane. For any word $w=A_1\cdots A_k\in \mathscr {F}_X$, and for any $0\le m\le k$, we write $\sigma _m(w)=A_1\cdots A_m$ for the initial subword consisting of the first m letters of w. Note that $\sigma _0(w)=\varepsilon$ and $\sigma _{\ell (w)}(w)=w$ for any word w. Considering the letters $A_1,\ldots ,A_k$ as steps in a walk from O to $\alpha _X(w)=A_1+\cdots +A_k$, we see that the points visited during the walk are

$$\begin{aligned} O=\alpha _X(\sigma _0(w)) \ \ \rightarrow \ \ \alpha _X(\sigma _1(w)) \ \ \rightarrow \ \ \alpha _X(\sigma _2(w)) \ \ \rightarrow \ \ \cdots \ \ \rightarrow \ \ \alpha _X(\sigma _k(w)) =\alpha _X(w).\nonumber \\ \end{aligned}$$

(3.1)

(The surmorphism $\alpha _X:\mathscr {F}_X\rightarrow \mathscr {A}_X$ was defined in Sect. 2.1.)

Now fix a subset $\mathscr {C}$ of $\mathbb Z^2$ with $O\in \mathscr {C}$. Consider a word $w=A_1\cdots A_k\in \mathscr {F}_X$; so w is an X-walk from O to $\alpha _X(w)$, visiting the points listed in (3.1). We are interested in the walks that are constrained in such a way that all of these points belong to $\mathscr {C}$; we call such a walk an $(X,\mathscr {C})$-walk. Accordingly, we define

$$\begin{aligned}&\qquad \qquad \mathscr {F}_X^\mathscr {C}= \big \{ {w\in \mathscr {F}_X}: {\alpha _X(\sigma _m(w))\in \mathscr {C}\text { for all } 0\le m\le \ell (w)} \big \} \\&\quad \text {and}\quad \mathscr {A}_X^\mathscr {C}= \alpha _X(\mathscr {F}_X^\mathscr {C}) = \{ {\alpha _X(w)} : {w\in \mathscr {F}_X^\mathscr {C}} \}. \end{aligned}$$

So $\mathscr {F}_X^\mathscr {C}$ is the set of all $(X,\mathscr {C})$-walks, and $\mathscr {A}_X^\mathscr {C}$ is the set of all endpoints of such walks. Note that ${\mathscr {A}_X^\mathscr {C}\subseteq \mathscr {A}_X\cap \mathscr {C}}$, but that this inclusion may be strict; consider $X=\{(1,0)\}$ and $\mathscr {C}=2\mathbb N\times \{0\}$. Note also that $\varepsilon \in \mathscr {F}_X^\mathscr {C}$ and $O\in \mathscr {A}_X^\mathscr {C}$ for any X and $\mathscr {C}$, but that neither $\mathscr {F}_X^\mathscr {C}$ nor $\mathscr {A}_X^\mathscr {C}$ need be monoids in general; consider $X=\{(1,0)\}$ and $\mathscr {C}=\{(0,0),(1,0)\}$. However, we do have the following general result.

Lemma 3.1

If $X\subseteq \mathbb Z_\times ^2$ is a step set, and if $\mathscr {C}$ is a submonoid of $\mathbb Z^2$, then $\mathscr {F}_X^\mathscr {C}$ and $\mathscr {A}_X^\mathscr {C}$ are submonoids of $\mathscr {F}_X$ and $\mathscr {A}_X$, respectively.

Proof

Since $\mathscr {A}_X^\mathscr {C}=\alpha _X(\mathscr {F}_X^\mathscr {C})$, and since $\alpha _X$ is a homomorphism, it suffices to prove the statement concerning $\mathscr {F}_X^\mathscr {C}$. With this in mind, let $u,v\in \mathscr {F}_X^\mathscr {C}$, and write $k=\ell (u)$ and $l=\ell (v)$. We must show that $\alpha _X(\sigma _m(uv))\in \mathscr {C}$ for all $0\le m\le \ell (uv)=k+l$. Now, if $0\le m\le k$, then $\alpha _X(\sigma _m(uv))=\alpha _X(\sigma _m(u))\in \mathscr {C}$ since $u\in \mathscr {F}_X^\mathscr {C}$. If $k\le m\le k+l$, then

$$\begin{aligned} \alpha _X(\sigma _m(uv))=\alpha _X(u\sigma _{m-k}(v))=\alpha _X(u)+\alpha _X(\sigma _{m-k}(v))\in \mathscr {C}\end{aligned}$$

since $u,v\in \mathscr {F}_X^\mathscr {C}$ and since $\mathscr {C}$ is a submonoid. $\square$

Consider a step set $X\subseteq \mathbb Z_\times ^2$ and a subset $\mathscr {C}\subseteq \mathbb Z^2$ with $O\in \mathscr {C}$. Analogously to the case of unconstrained walks, for $A\in \mathbb Z^2$, we define

$$\begin{aligned} \Pi _X^\mathscr {C}(A) = \{ {w\in \mathscr {F}_X^\mathscr {C}} : {\alpha _X(w)=A} \} \qquad \text {and}\qquad \pi _X^\mathscr {C}(A)=|\Pi _X^\mathscr {C}(A)|. \end{aligned}$$

So $\Pi _X^\mathscr {C}(A)$ is the set of all $(X,\mathscr {C})$-walks from O to A, and $\pi _X^\mathscr {C}(A)$ is the number of such walks. Clearly $\pi _X^\mathscr {C}(A)\le \pi _X(A)$ for all A. If $\mathscr {A}_X\subseteq \mathscr {C}$, then $\Pi _X^\mathscr {C}(A)=\Pi _X(A)$ and $\pi _X^\mathscr {C}(A)=\pi _X(A)$ for all A; in particular, this occurs when $\mathscr {C}=\mathbb Z^2$, in which case we are dealing with unconstrained walks; cf. Sect. 2.

As in Sect. 2, the combinatorial data corresponding to the pair $(X,\mathscr {C})$ may be conveniently displayed in a bi-labelled digraph, $\Gamma _X^\mathscr {C}$, defined as follows:

• The vertex set of $\Gamma _X^\mathscr {C}$ is $\mathscr {A}_X^\mathscr {C}$; a vertex $A\in \mathscr {A}_X^\mathscr {C}$ is drawn in the appropriate position in the plane, and is labelled $\pi _X^\mathscr {C}(A)$.

• If $A\in \mathscr {A}_X^\mathscr {C}$ and $B\in X$ are such that $A+B\in \mathscr {C}$, then $\Gamma _X^\mathscr {C}$ has the labelled edge $A\xrightarrow {\ B\ }A+B$.

We noted in Sect. 2.1 that $\Gamma _X$ is the Cayley graph of the monoid $\mathscr {A}_X$ with respect to the generating set X (with additional vertex labels showing the numbers $\pi _X(A)$). It is important to note, however, that even when $\mathscr {A}_X^\mathscr {C}$ is a monoid, $\Gamma _X^\mathscr {C}$ is generally not a Cayley graph of $\mathscr {A}_X^\mathscr {C}$; in fact, X is not even a subset of $\mathscr {A}_X^\mathscr {C}$ in general, let alone a generating set.

At this point we consider some basic examples.

Example 3.2

(cf. Examples 2.1, 2.2 and 2.4) For the following examples, let $\mathscr {C}=\{ {(a,b)\in \mathbb N^2} : {b\le a} \}$, and also define the points $N=(0,1)$, $E=(1,0)$, $S=(0,-1)$ and $W=(-1,0)$.

• (i) For $X=\{N,E\}$, we have $\mathscr {A}_X^\mathscr {C}=\mathscr {C}$, and the numbers $\pi _X^\mathscr {C}(A)$ form the Catalan Triangle; see [1, A009766, A033184 or A053121]. Fig. 15 shows the graph $\Gamma _X^\mathscr {C}$.

• (ii) For $X=\{N,E,S,W\}$, we again have $\mathscr {A}_X^\mathscr {C}=\mathscr {C}$, but this time $\pi _X^\mathscr {C}(A)=\infty$ for all $A\in \mathscr {C}$; cf. Fig. 15.

• (iii) For the infinite step set $X=\{1\}\times \mathbb N$, we still have $\mathscr {A}_X^\mathscr {C}=\mathscr {C}$, and the numbers $\pi _X^\mathscr {C}(A)$ produced are the same as for the finite step set $\{N,E\}$ considered above (the Catalan Triangle); cf. Fig 15.

• (iv) Let $X=\{N,E,S,W,U\}$, where $U=(1,1)$. The graphs $\Gamma _X^{\mathscr {C}_1}$, $\Gamma _X^{\mathscr {C}_2}$ and $\Gamma _X^{\mathscr {C}_3}$ are pictured in Fig. 16, for the three submonoids

  $$\begin{aligned} \mathscr {C}_1=\{ {(a,a)} : {a\in \mathbb Z} \} ,\qquad \mathscr {C}_2=\mathbb N^2 ,\qquad \mathscr {C}_3=\{O\}\cup \mathbb P^2. \end{aligned}$$

  The pair $(X,\mathscr {C}_1)$ shows that it is possible for $\mathscr {A}_X$ and $\mathscr {C}$ both to be groups, but $\mathscr {A}_X^\mathscr {C}$ not to be.

Fig. 15

The graph $\Gamma _X^\mathscr {C}$, where $\mathscr {C}=\{ {(a,b)\in \mathbb N^2} : {b\le a} \}$, and (left to right): $X=\{(1,0),(0,1)\}$, $X=\{(\pm 1,0),(0,\pm 1)\}$ and $X=\{1\}\times \mathbb N$; cf. Example 3.2(i)–(iii)

Fig. 16

The graphs $\Gamma _X^{\mathscr {C}_1}$ (left), $\Gamma _X^{\mathscr {C}_2}$ (middle) and $\Gamma _X^{\mathscr {C}_3}$ (right), where $X=\{(\pm 1,0),(0,\pm 1),(1,1)\}$, $\mathscr {C}_1=\{ {(a,a)} : {a\in \mathbb Z} \}$, $\mathscr {C}_2=\mathbb N^2$ and $\mathscr {C}_3=\{O\}\cup \mathbb P^2$; cf. Example 3.2(iv)

Remark 3.3

Consider a step set $X\subseteq \mathbb Z_\times ^2$ and a submonoid $\mathscr {C}$ of $\mathbb Z^2$. Above, we have only spoken of $(X,\mathscr {C})$-walks from the origin O to a point A, but it is possible to speak of $(X,\mathscr {C})$-walks from A to B for arbitrary $A,B\in \mathbb Z^2$. These would be X-walks $w\in \Pi _X(A,B)$ such that $A+\alpha _X(\sigma _m(w))\in \mathscr {C}$ for all $0\le m\le \ell (w)$; for such a walk to exist, it must of course be the case that $A,B\in \mathscr {C}$. Let $\Pi _X^\mathscr {C}(A,B)$ and $\pi _X^\mathscr {C}(A,B)$ denote the set and number of $(X,\mathscr {C})$-walks from A to B. Then one may easily show that

$$\begin{aligned} \Pi _X^\mathscr {C}(A,B)\subseteq \Pi _X^\mathscr {C}(A+C,B+C) \qquad \text {and}\qquad \pi _X^\mathscr {C}(A,B)&\le \pi _X^\mathscr {C}(A+C,B+C) \\&\qquad \text {for any}~C\in \mathscr {C}, \end{aligned}$$

though these can be strict. (Indeed, if X and $\mathscr {C}$ are as in Example 3.2(i), then with $A=(0,0)$, $B=(1,1)$ and $C=(1,0)$, we have $NE\in \Pi _X^\mathscr {C}(A+C,B+C)\setminus \Pi _X^\mathscr {C}(A,B)$; cf. Fig. 15.) Thus, the $(X,\mathscr {C})$-walks from the origin alone do not generally capture all information about $(X,\mathscr {C})$-walks between arbitrary points, in contrast to the situation with unconstrained walks. It is possible to define a structure that incorporates all such $(X,\mathscr {C})$-walks, namely the category with object set $\mathscr {C}$, and morphism sets ${\text {Hom}}(A,B)=\Pi _X^\mathscr {C}(A,B)$ for each $A,B\in \mathscr {C}$. We believe it would be interesting to study such categories, but it is beyond the scope of the current work.

3.2 Geometric Conditions and Finiteness Properties for Constrained Walks

This section and the next concern constrained versions of the finiteness properties given in Sect. 2.2, and their relationships to the geometric conditions introduced in Sect. 2.3.

Consider a step set $X\subseteq \mathbb Z_\times ^2$, and a subset $\mathscr {C}$ of $\mathbb Z^2$ containing O.

• We say $(X,\mathscr {C})$ has the Finite Paths Property (FPP) if $\pi _X^\mathscr {C}(A)<\infty$ for all $A\in \mathscr {A}_X^\mathscr {C}$.

• We say $(X,\mathscr {C})$ has the Infinite Paths Property (IPP) if $\pi _X^\mathscr {C}(A)=\infty$ for all $A\in \mathscr {A}_X^\mathscr {C}$.

• We say $(X,\mathscr {C})$ has the Bounded Paths Property (BPP) if for all $A\in \mathscr {A}_X^\mathscr {C}$, the set $\big \{ {\ell (w)}: {w\in \Pi _X^\mathscr {C}(A)} \big \}$ has a maximum element (equivalently, this set is finite).

The proof of Lemma 2.5 works essentially unchanged to show that for any step set X, and for any submonoid $\mathscr {C}$ of $\mathbb Z^2$,

$$\begin{aligned} (X,\mathscr {C}) \text { has the IPP} \ \Leftrightarrow \ \pi _X^\mathscr {C}(O)=\infty \ \Leftrightarrow \ \pi _X^\mathscr {C}(O)\ge 2. \end{aligned}$$

(3.2)

We also have the following constrained version of Theorem 2.24. To make the statement clearer, we write $P\ {\models }\ Q$ to mean “P satisfies Q”.

Theorem 3.4

• (i) For an arbitrary step set $X\subseteq \mathbb Z_\times ^2$, and for an arbitrary submonoid $\mathscr {C}$ of $\mathbb Z^2$, we have:

  

  (3.3)

• (ii) For finite X, some but not all of the implications in (3.3) are reversible; these are indicated as follows:

• (iii) In general, none of the implications in (3.3) are reversible.

Proof

(i). The top row of “horizontal” implications have already been proven in Lemma 2.8. The “vertical” implications follow from Theorem 2.24(i) and the obvious facts that

$$\begin{aligned}&X\ {\models }\ \text {FPP} \ \Rightarrow \ (X,\mathscr {C})\ {\models }\ \text {FPP} ,\qquad X\ {\models }\ \text {BPP} \ \Rightarrow \ (X,\mathscr {C})\ {\models }\ \text {BPP},\qquad \\&X\ {\not \models }\ \text {IPP} \ \Rightarrow \ (X,\mathscr {C})\ {\not \models }\ \text {IPP} . \end{aligned}$$

The bottom row of “horizontal” implications are proved in analogous fashion to Lemma 2.6.

(ii). Suppose X is finite. We begin with the non-reversible implications. The pair $(X,\mathscr {C}_3)$ from Example 3.2(iv) satisfies neither the IPP nor the BPP; this shows that the implication $(X,\mathscr {C})\ {\models }\$BPP $\ \Rightarrow \$ $(X,\mathscr {C})\ {\not \models }\$IPP is not reversible in general (even for finite X). The pair $(X,\mathscr {C}_1)$ from the same example satisfies the FPP, but X does not satisfy the LC; this takes care of all the “vertical” (non-)implications.

The two “horizontal” implications on the top row are reversible because of Lemma 2.8(iii). The only remaining implication to demonstrate is $(X,\mathscr {C})\ {\models }\$BPP $\ \Rightarrow \$ $(X,\mathscr {C})\ {\models }\$FPP. So suppose $(X,\mathscr {C})$ satisfies the BPP. Let $A\in \mathscr {A}_X^\mathscr {C}$ be arbitrary. Writing $L={\max }\big \{ {\ell (w)}: {w\in \Pi _X^\mathscr {C}(A)} \big \}$, we see that $\Pi _X^\mathscr {C}(A)$ is contained in the set $\{ {w\in \mathscr {F}_X} : {\ell (w)\le L} \}$; since the latter is finite (as X is finite), so too is $\Pi _X^\mathscr {C}(A)$.

(iii). The proof of Theorem 2.24(iii) remains valid here, upon taking $\mathscr {C}=\mathbb Z^2$. $\square$

Remark 3.5

With different formatting, perhaps the implications in Theorem 3.4(ii) appear clearer as:

$$\begin{aligned}&\big [X\ {\models }\ \text {CC} \ \Leftrightarrow \ X\ {\models }\ \text {SLC} \ \Leftrightarrow \ X\ {\models }\ \text {LC}\big ] \\&\ \ \Rightarrow \ \ \ \big [(X,\mathscr {C})\ {\models }\ \text {FPP}\ \Leftrightarrow \ (X,\mathscr {C})\ {\models }\ \text {BPP}\big ] \ \ \ \Rightarrow \ \ \ (X,\mathscr {C})\ {\models }\ \text {IPP}, \end{aligned}$$

for finite X.

There are also analogues of Theorems 2.19 and 2.30 for constrained walks, although these are somewhat more subtle than the unconstrained versions. We begin with a lemma that motivates the discussion to follow; it shows that the conditions $O\in {\text {Conv}}(X)$ and $O\in {\text {Rel-Int}}({\text {Conv}}(X))$ considered in Theorems 2.19 and 2.30 are equivalent to ostensibly weaker conditions.

Lemma 3.6

Let $X\subseteq \mathbb Z_\times ^2$ be an arbitrary step set. Then

• (i) $O\in {\text {Conv}}(X) \ \Leftrightarrow \ O\in {\text {Conv}}(\mathscr {A}_X\setminus \{O\})$,

• (ii) $O\in {\text {Rel-Int}}({\text {Conv}}(X)) \ \Leftrightarrow \ O\in {\text {Rel-Int}}({\text {Conv}}(\mathscr {A}_X\setminus \{O\}))$.

Proof

Write $Y=\mathscr {A}_X\setminus \{O\}$, noting that $\mathscr {A}_Y=\mathscr {A}_X$. For part (i) we have

$$\begin{aligned} O\in {\text {Conv}}(X)&\ \Leftrightarrow \ \mathscr {A}_X \text { has non-trivial units}&\text {by Theorem 2.19}\\&\ \Leftrightarrow \ \mathscr {A}_Y \text { has non-trivial units}&\text {as}\quad \mathscr {A}_X=\mathscr {A}_Y\\&\ \Leftrightarrow \ O\in {\text {Conv}}(Y)&\text {by Theorem 2.19 again.} \end{aligned}$$

Part (ii) is treated in similar fashion, using Theorem 2.30 instead of Theorem 2.19. $\square$

In light of Theorem 2.19 and Lemma 3.6(i), we see that for any step set $X\subseteq \mathbb Z_\times ^2$,

$$\begin{aligned} X\ {\models }\ \text {IPP} \ \Leftrightarrow \ O\in {\text {Conv}}(X)&\ \Leftrightarrow \ O\in {\text {Conv}}(\mathscr {A}_X\setminus \{O\}) \\&\ \Leftrightarrow \ \mathscr {A}_X \text { has non-trivial units}. \end{aligned}$$

The next result considers the analogous conditions for pairs $(X,\mathscr {C})$.

Proposition 3.7

Let $X\subseteq \mathbb Z_\times ^2$ be an arbitrary step set, and let $\mathscr {C}$ be a submonoid of $\mathbb Z^2$. Consider the following statements:

• (i) $(X,\mathscr {C})$ has the IPP,

• (ii) $O\in {\text {Conv}}(X)$,

• (iii) $O\in {\text {Conv}}(\mathscr {A}_X^\mathscr {C}\setminus \{O\})$,

• (iv) $\mathscr {A}_X^\mathscr {C}$ has non-trivial units.

Then the implications that hold among (i)–(iv) are precisely those inferrable from the following:

$$\begin{aligned} (iii) \ \Leftrightarrow \ (iv) \ \Rightarrow \ (i) \ \Rightarrow \ (ii) . \end{aligned}$$

Proof

We begin with the stated implications.

(iii)$\ \Leftrightarrow \$(iv). Put $Y=\mathscr {A}_X^\mathscr {C}\setminus \{O\}$. Since $\mathscr {A}_X^\mathscr {C}=\mathscr {A}_Y$, this equivalence follows from Theorem 2.19.

(iv)$\ \Rightarrow \$(i). Suppose $O=A+B$, where $A,B\in \mathscr {A}_X^\mathscr {C}\setminus \{O\}$. Then by definition, we have $A=\alpha _X(u)$ and $B=\alpha _X(v)$ for some $u,v\in \mathscr {F}_X^\mathscr {C}\setminus \{\varepsilon \}$. It quickly follows that $uv\in \Pi _X^\mathscr {C}(O)\setminus \{\varepsilon \}$, and so $\pi _X^\mathscr {C}(O)\ge 2$. But then $(X,\mathscr {C})$ has the IPP by (3.2).

(i)$\ \Rightarrow \$(ii). This is exactly the same as the corresponding part of Theorem 2.19.

We now treat the non-implications. It suffices to show that (ii)$\ \not \Rightarrow \$(i) and (i)$\ \not \Rightarrow \$(iv).

(ii)$\ \not \Rightarrow \$(i). The pair $(X,\mathscr {C}_1)$ from Example 3.2(iv) satisfies (ii) but not (i).

(i)$\ \not \Rightarrow \$(iv). The pair $(X,\mathscr {C}_2)$ from Example 3.2(iv) satisfies (i) but not (iv).

$\square$

In light of Theorem 2.30 and Lemma 3.6(ii), for any step set $X\subseteq \mathbb Z_\times ^2$, the monoid $\mathscr {A}_X$ is a non-trivial group if and only if $O\in {\text {Rel-Int}}({\text {Conv}}(\mathscr {A}_X\setminus \{O\}))$. The next result is a direct analogue of this last statement for constrained walks, and in fact follows quickly from the unconstrained version.

Proposition 3.8

Let $X\subseteq \mathbb Z_\times ^2$ be an arbitrary step set, and let $\mathscr {C}$ be a submonoid of $\mathbb Z^2$. Then $\mathscr {A}_X^\mathscr {C}$ is a non-trivial group if and only if $O\in {\text {Rel-Int}}({\text {Conv}}(\mathscr {A}_X^\mathscr {C}\setminus \{O\}))$.

Proof

Let $Y=\mathscr {A}_X^\mathscr {C}\setminus \{O\}$, noting that $\mathscr {A}_Y=\mathscr {A}_X^\mathscr {C}$. Then by Theorem 2.30,

$$\begin{aligned} \mathscr {A}_X^\mathscr {C}\text { is a non-trivial group}&\ \Leftrightarrow \ \mathscr {A}_Y \text { is a non-trivial group}\\&\ \Leftrightarrow \ O\in {\text {Rel-Int}}({\text {Conv}}(Y)). \square \end{aligned}$$

Remark 3.9

The condition $O\in {\text {Rel-Int}}({\text {Conv}}(X))$ neither implies nor is implied by $\mathscr {A}_X^\mathscr {C}$ being a (non-trivial) group. For example:

• If $X=\{(1,0),(-1,0),(0,1)\}$ and $\mathscr {C}=\mathbb Z\times \{0\}$, then $\mathscr {A}_X^\mathscr {C}=\mathscr {C}$ is a group, yet $O\not \in {\text {Rel-Int}}({\text {Conv}}(X))$.

• If $(X,\mathscr {C}_1)$ is as in Example 3.2(iv), then $O\in {\text {Rel-Int}}({\text {Conv}}(X))$, yet $\mathscr {A}_X^{\mathscr {C}_1}$ is not a group.

But of course $\mathscr {A}_X^\mathscr {C}$ being a non-trivial group implies $O\in {\text {Conv}}(X)$ because of Proposition 3.7.

3.3 Admissible Steps, and Constraint Sets Containing Lattice Cones

Consider a pair $(X,\mathscr {C})$, where $X\subseteq \mathbb Z_\times ^2$ is a step set, and $\mathscr {C}$ a submonoid of $\mathbb Z^2$. We say a step $A\in X$ is $(X,\mathscr {C})$-admissible if there exist words $u,v\in \mathscr {F}_X$ such that $uAv\in \mathscr {F}_X^\mathscr {C}$. So the $(X,\mathscr {C})$-admissible steps are those that may actually be used in $(X,\mathscr {C})$-walks. Since any initial subword of an $(X,\mathscr {C})$-walk is clearly an $(X,\mathscr {C})$-walk (i.e., since $\mathscr {F}_X^\mathscr {C}$ is prefix-closed), $A\in X$ is $(X,\mathscr {C})$-admissible if and only if there exists a word $u\in \mathscr {F}_X$ such that $uA\in \mathscr {F}_X^\mathscr {C}$, and then we also have $u\in \mathscr {F}_X^\mathscr {C}$ for any such u.

Note that if Y is the set of all $(X,\mathscr {C})$-admissible steps, then we have $\mathscr {A}_X^\mathscr {C}=\mathscr {A}_Y^\mathscr {C}$, $\Gamma _X^\mathscr {C}=\Gamma _Y^\mathscr {C}$, and so on. In general, determining Y, given X and $\mathscr {C}$, is not always easy; however, it is easy in at least one special case we treat below. This section gives a number of strengthenings of results from previous sections based on admissible steps.

Theorem 3.10

Let $X\subseteq \mathbb Z_\times ^2$ be a step set, let $\mathscr {C}$ be a submonoid of $\mathbb Z^2$, and let $Y\subseteq X$ be the set of $(X,\mathscr {C})$-admissible steps. If Y is finite, then the following are equivalent:

(i) $(X,\mathscr {C})$ has the FPP, (ii) $O\not \in {\text {Conv}}(Y)$, (iii) Y satisfies the LC.

Proof

(i)$\ \Rightarrow \$(ii). We prove the contrapositive (and we note that for this implication we do not need to assume Y is finite). Suppose $O\in {\text {Conv}}(Y)$. As in the proof of Theorem 2.19, we have $O=xA+yB+zC$ for some $A,B,C\in Y$ and $x,y,z\in \mathbb N$ with x, y, z not all zero. (At this point it is worth noting that, in contrast to the unconstrained case, we may not simply deduce that $A^xB^yC^z$ belongs to $\Pi _X^\mathscr {C}(O)$.) Since A, B, C are $(X,\mathscr {C})$-admissible, there exist $u,v,w\in \mathscr {F}_X$ such that $uA,vB,wC\in \mathscr {F}_X^\mathscr {C}$. As noted above, we also have $u,v,w\in \mathscr {F}_X^\mathscr {C}$. For convenience, we write $U=\alpha _X(u)$, $V=\alpha _X(v)$ and $W=\alpha _X(w)$. For $k\in \mathbb N$, define the word

$$\begin{aligned} g_k = u^xv^yw^z(A^xB^yC^z)^k. \end{aligned}$$

Let $D=xU+yV+zW$. The proof will be complete if we can show that $g_k\in \Pi _X^\mathscr {C}(D)$ for all $k\in \mathbb N$, as then $\pi _X^\mathscr {C}(D)=\infty$. With this in mind, fix some $k\in \mathbb N$. Note that

$$\begin{aligned} \alpha _X(g_k) = xU+yV+zW+k(xA+yB+zC)=D+kO=D, \end{aligned}$$

so that $g_k\in \Pi _X(D)$, so it remains to show that $g_k\in \mathscr {F}_X^\mathscr {C}$. To do so, we must show that $\alpha _X(\sigma _i(g_k))\in \mathscr {C}$ for all $0\le i\le \ell (g_k)$, so consider some such i. Note that

$$\begin{aligned} \ell (g_k) = \lambda +k\mu , \qquad \text {where} \lambda =x\ell (u)+y\ell (v)+z\ell (w)\text { and }\mu =x+y+z. \end{aligned}$$

If $i\le \lambda$, then $\sigma _i(g_k)=\sigma _i(u^xv^yw^z)$, and since $u^xv^yw^z\in \mathscr {F}_X^\mathscr {C}$ (as u, v, w belong to the monoid $\mathscr {F}_X^\mathscr {C}$), it follows that $\alpha _X(\sigma _i(g_k))\in \mathscr {C}$. So now suppose ${i>\lambda }$. By the division algorithm, we may write $i-\lambda =q\mu +r$, where $q,r\in \mathbb N$ and $0\le r<\mu$. Then since $xA+yB+zC=O$, we have

$$\begin{aligned}&\alpha _X(\sigma _i(g_k)) = (xU+yV+zW) + q(xA+yB+zC) + \alpha _X(\sigma _r(A^xB^yC^z)) \\&= (xU+yV+zW) + \alpha _X(\sigma _r(A^xB^yC^z)) \\&= {\left\{ \begin{array}{ll} (xU+yV+zW) + rA &{}\qquad \qquad \qquad \qquad \quad \text {if}~0\le r\le x\\ (xU+yV+zW) + xA+(r-x)B &{}\qquad \qquad \qquad \qquad \quad \text {if}~x\le r\le x+y\\ (xU+yV+zW) + xA+yB+(r-x-y)C &{}\qquad \qquad \qquad \qquad \quad \text {if}~x+y\le r<x+y+z \end{array}\right. }\\&= {\left\{ \begin{array}{ll} r(U+A) + (x-r)U +yV+zW &{}\text {if}~0\le r\le x\\ x(U+A) + (r-x)(V+B) + (x+y-r)V + zW &{}\text {if} ~x\le r\le x+y\\ x(U+A)+y(V+B)+(r-x-y)(W+C) +(x+y+z-r)W &{}\text {if} ~x+y\le r<x+y+z. \end{array}\right. } \end{aligned}$$

Since U, V, W, $U+A$, $V+B$ and $W+C$ all belong to the monoid $\mathscr {C}$, so too does $\alpha _X(\sigma _i(g_k))$ in all of the above cases.

(ii)$\ \Rightarrow \$(iii). Since Y is finite, Theorems 2.19 and 2.24(ii) give

$$\begin{aligned} O\not \in {\text {Conv}}(Y) \ \Rightarrow \ Y\ {\not \models }\ \text {IPP} \ \Rightarrow \ Y\ {\models }\ \text {LC}. \end{aligned}$$

(iii)$\ \Rightarrow \$(i). Here we have

$$\begin{aligned} Y\ {\models }\ \text {LC} \ \Rightarrow \ Y\ {\models }\ \text {FPP} \ \Rightarrow \ (Y,\mathscr {C})\ {\models }\ \text {FPP} \ \Rightarrow \ (X,\mathscr {C})\ {\models }\ \text {FPP}. \end{aligned}$$

Indeed, the first implication follows from Theorem 2.24(ii), the second is obvious, and the third follows from the fact that the $(X,\mathscr {C})$-walks are precisely the $(Y,\mathscr {C})$-walks. $\square$

Remark 3.11

In light of the finiteness assumption on Y in Theorem 3.10, several more equivalent conditions could be listed; cf. Theorems 2.19 and 2.24(ii).

Remark 3.12

In the notation of Theorem 3.10, we have $(X,\mathscr {C})\ {\models }\$FPP$\ \Leftrightarrow \$ $O\not \in {\text {Conv}}(Y)$. While this certainly entails that $(X,\mathscr {C})\ {\models }\$IPP$\ \Rightarrow \$ $O\in {\text {Conv}}(Y)$, the converse does not hold in general (even for finite X), as shown by the pair $(X,\mathscr {C}_3)$ from Example 3.2(iv) (cf. Figure 16). Consequently, we could not have listed “$(X,\mathscr {C})$ does not have the IPP” as one of the equivalent conditions in Theorem 3.10. In particular, there is no FPP/IPP dichotomy for constrained walks with finite step sets; cf. Corollary 2.25.

Many examples of constrained walks considered in the literature (and throughout the current paper) involve a special kind of constraint set $\mathscr {C}$ that is suitably “thick”, in the sense that $\mathscr {C}$ contains $\mathcal C\cap \mathbb Z^2$ where $\mathcal C$ is some (open) cone with vertex O. It turns out that Theorem 3.10 may be strengthened in certain such cases, as shown in Theorem 3.15 below. First we need the following lemma.

Lemma 3.13

Let $X\subseteq \mathbb Z_\times ^2$ be an arbitrary step set, and let $\mathscr {C}$ be a submonoid of $\mathbb Z^2$. Suppose also that there is an (open) cone $\mathcal C$ with vertex O such that $\mathcal C\cap \mathbb Z^2\subseteq \mathscr {C}$ and $\mathcal C\cap \mathscr {A}_X^\mathscr {C}\not =\emptyset$. Then every step from X is $(X,\mathscr {C})$-admissible.

Proof

Let $A\in X$ be arbitrary. By assumption, there exists some point $B\in \mathcal C\cap \mathscr {A}_X^\mathscr {C}$. We note also that B is an interior point of $\mathcal C$ (as the latter is an open set). It follows that there exists $n\in \mathbb N$ such that the circle of radius |OA| centred at nB (including the boundary and interior) is contained in $\mathcal C$. But then we have $nB+A\in \mathcal C\cap \mathbb Z^2\subseteq \mathscr {C}$. Thus, for any word $w\in \Pi _X^\mathscr {C}(B)$, we have $w^nA\in \mathscr {F}_X^\mathscr {C}$, showing that A is indeed $(X,\mathscr {C})$-admissible. All of this is shown in Figure 17.$\square$

Remark 3.14

The assumption that $\mathcal C\cap \mathscr {A}_X^\mathscr {C}\not =\emptyset$ is crucial in proving Lemma 3.13. For example, consider $X=\{(1,0),(0,-1)\}$ and $\mathscr {C}=\mathbb N^2$, noting that $\mathscr {A}_X^\mathscr {C}=\mathbb N\times \{0\}$. Then $\mathscr {C}$ contains $\mathcal C\cap \mathbb Z^2$, where $\mathcal C$ is the cone $\{ {(x,y)\in \mathbb R^2} : {\frac{x}{3}<y<\frac{x}{2}} \}$, yet $(0,-1)$ is not $(X,\mathscr {C})$-admissible. In fact, every (open) cone $\mathcal C$ with vertex O satisfying $\mathcal C\cap \mathbb Z^2\subseteq \mathscr {C}$ is contained in the first quadrant, so for any such cone we have $\mathcal C\cap \mathscr {A}_X^\mathscr {C}=\emptyset$.

Fig. 17

Verification that $nB+A\in \mathscr {C}$, from the proof of Lemma 3.13. Edges are coloured red (A) and blue (B). Note that $A\in X$ and $B\in \mathscr {A}_X^\mathscr {C}$, so that a blue edge represents an $(X,\mathscr {C})$-walk from O to B; such a walk might step outside of the cone $\mathcal C$ (but not outside of the region $\mathscr {C}$)

Theorem 3.15

Let $X\subseteq \mathbb Z_\times ^2$ be an arbitrary finite step set, and let $\mathscr {C}$ be a submonoid of $\mathbb Z^2$. Suppose also that there is an (open) cone $\mathcal C$ with vertex O such that $\mathcal C\cap \mathbb Z^2\subseteq \mathscr {C}$ and $\mathcal C\cap \mathscr {A}_X^\mathscr {C}\not =\emptyset$. Then the following are equivalent:

• (i) $(X,\mathscr {C})$ has the FPP,

• (ii) $O\not \in {\text {Conv}}(X)$,

• (iii) X satisfies the LC.

Proof

This follows immediately from Theorem 3.10 and Lemma 3.13.$\square$

Remark 3.16

As in Remark 3.12, we could not include “$(X,\mathscr {C})$ does not have the IPP” among the listed conditions in Theorem 3.15. On the other hand, any of the equivalent conditions from Theorem 2.24(ii) could have been added. In particular, it seems noteworthy that $(X,\mathscr {C})\ {\models }\$FPP$\ \Leftrightarrow \ X\ {\models }\$FPP for such pairs $(X,\mathscr {C})$. The corresponding statement for the IPP is false, as shown by $(X,\mathscr {C}_3)$ from Example 3.2(iv).

Remark 3.17

While the $(X,\mathscr {C})$-admissible steps have been useful in this section for characterising the FPP in certain situations (Theorems 3.10 and 3.15), we cannot use them to improve Propositions 3.7 or 3.8. For example, with $X\subseteq \mathbb Z_\times ^2$ a step set, $\mathscr {C}$ a submonoid of $\mathbb Z^2$, and Y the set of $(X,\mathscr {C})$-admissible steps, one might hope to prove that

• $(X,\mathscr {C})$ has the IPP if and only if $O\in {\text {Conv}}(Y)$, or

• $\mathscr {A}_X^\mathscr {C}$ is a non-trivial group if and only if $O\in {\text {Rel-Int}}({\text {Conv}}(Y))$.

But neither of these are true, as again evidenced by the pair $(X,\mathscr {C}_3)$ from Example 3.2(iv). $\square$

Appendix (joint with Stewart Wilcox): Combination (V)

In Sect. 2.9 we used Theorem 2.24 to limit the ostensibly possible combinations of finiteness conditions and geometric properties of step sets to just ten. One combination was shown never to occur (cf. Proposition 2.36), and all but one of the other combinations have been exemplified by various step sets whose locations are listed in Table 1. The purpose of this appendix is to construct a step set with the final combination (see Example A.5). The construction relies crucially on the existence of very specific sequences of real numbers (see Proposition A.2), and we turn to these first.

In all that follows, we fix a positive irrational number $\xi$, and we denote by

$$\begin{aligned} M = \{ {a+b\xi } : {a,b\in \mathbb Z,\ a+b\xi \ge 0} \} \end{aligned}$$

the additive monoid consisting of all non-negative $\mathbb Z$-linear combinations of 1 and $\xi$. Note that a or b might be negative in $a+b\xi \in M$, but we require $a+b\xi$ itself to be non-negative. So M is a submonoid of $\mathbb R_{\ge 0}$, and is dense in $\mathbb R_{\ge 0}$; see the claim in the proof of Lemma 2.15. Since 1 and $\xi$ are linearly independent over $\mathbb Q$, there is a well defined (and surjective) monoid homomorphism

$$\begin{aligned} \phi :M\rightarrow \mathbb Z\qquad \text {given by}\qquad \phi (a+b\xi )=b. \end{aligned}$$

For $a,b\in \mathbb R$, we write [a, b] and (a, b) for the closed and open intervals of all $x\in \mathbb R$ satisfying $a\le x\le b$ or $a<x<b$, respectively; we also write [a, b) and (a, b] for the half-open intervals, with the obvious meanings. If $\Sigma \subseteq \mathbb R$, we will also write $[a,b]_\Sigma =[a,b]\cap \Sigma$, with similar notation for other kinds of intervals; for example, if $a,b\in \mathbb Z$ and $a\le b$, then $[a,b]_\mathbb Z=\{a,a+1,\ldots ,b\}$. If x is a real number, we will write $(\!(x)\!) = x-\lfloor x\rfloor$ for the fractional part of x.

Lemma A.1

There is a mapping $\mathbb P\rightarrow \mathbb P:k\mapsto p_k$ such that

$$\begin{aligned} \phi ^{-1}\big ( [p,p+p_k]_\mathbb Z\big ) \cap (\alpha ,\alpha +\tfrac{1}{k})\not =\emptyset \qquad \text {for all}~\, p\in \mathbb Z\quad \text {and}~\, \alpha \in \mathbb R_{\ge 0}. \end{aligned}$$

Proof

Fix some $k\in \mathbb P$. By the claim in the proof of Lemma 2.15, there exists $l\in \mathbb P$ and $a\in \mathbb Z$ such that $0<l\xi -a<\frac{1}{k}$. Let $p_k\in \mathbb P$ be arbitrary so that

$$\begin{aligned} p_k > l(1+\tfrac{1}{l\xi -a}). \end{aligned}$$

Now suppose we are given $p\in \mathbb Z$ and $\alpha \in \mathbb R_{\ge 0}$. Define

$$\begin{aligned} t = 1 + \left\lfloor \frac{ (\!(\alpha -p\xi )\!)}{l\xi -a}\right\rfloor . \end{aligned}$$

Then

$$\begin{aligned} 1 \le t \le 1 + \frac{ (\!(\alpha -p\xi )\!)}{l\xi -a}< 1 + \frac{1}{l\xi -a} < \frac{p_k}{l}. \end{aligned}$$

(A.1)

We also claim that

$$\begin{aligned} 0< t(l\xi -a) - (\!(\alpha -p\xi )\!) < \frac{1}{k}. \end{aligned}$$

(A.2)

Indeed, for the inequality $0 < t(l\xi -a) - (\!(\alpha -p\xi )\!)$, note that if we write $\beta =l\xi -a$ and $\gamma =(\!(\alpha -p\xi )\!)$, then we have

$$\begin{aligned} t\beta - \gamma = (1+\lfloor \tfrac{\gamma }{\beta }\rfloor )\beta - \gamma = \beta \big (1 - (\tfrac{\gamma }{\beta }-\lfloor \tfrac{\gamma }{\beta }\rfloor )\big ) = \beta \big (1-(\!(\tfrac{\gamma }{\beta })\!)\big )>\beta (1-1)=0, \end{aligned}$$

while for the inequality $t(l\xi -a) - (\!(\alpha -p\xi )\!) \le l\xi -a$, we continue from above to obtain

$$\begin{aligned} t\beta - \gamma = \beta \big (1-(\!(\tfrac{\gamma }{\beta })\!)\big ) \le \beta = l\xi -a < \frac{1}{k}. \end{aligned}$$

Now that we have established (A.2), adding $\alpha$ throughout gives

$$\begin{aligned} \alpha< t(l\xi -a) +\alpha - (\!(\alpha -p\xi )\!) < \alpha +\frac{1}{k}. \end{aligned}$$

Since $\alpha -(\!(\alpha -p\xi )\!)=\alpha -(\alpha -p\xi )+\lfloor \alpha -p\xi \rfloor =p\xi +\lfloor \alpha -p\xi \rfloor$, it follows that

$$\begin{aligned} \alpha< t(l\xi -a) + p\xi + \lfloor \alpha -p\xi \rfloor < \alpha +\tfrac{1}{k}. \end{aligned}$$

That is,

$$\begin{aligned} \alpha< b + c\xi < \alpha +\tfrac{1}{k} \qquad \text {where}\qquad b=\lfloor \alpha -p\xi \rfloor -ta \quad \text {and}\quad c=tl+p. \end{aligned}$$

So $b+c\xi \in (\alpha ,\alpha +\frac{1}{k})$, and also $b+c\xi \in \phi ^{-1}\big ([p,p+p_k]_\mathbb Z\big )$ since $\phi (b+c\xi )=c=tl+p$ clearly satisfies $p\le c$, while $c\le p+p_k$ follows from $t<\frac{p_k}{l}$ which is itself part of (A.1).$\square$

In what follows, we fix the mapping $\mathbb P\rightarrow \mathbb P:k\mapsto p_k$ from Lemma A.1. In fact, by suitably increasing each $p_k$ if necessary, we may assume that $p_1<p_2<\cdots$.

In what follows, for any subset $\Sigma$ of $\mathbb R$, we write $S_n(\Sigma )=\{ {\sigma _1+\cdots +\sigma _n} : {\sigma _1,\ldots ,\sigma _n\in \Sigma } \}$ for the set of all sums of n elements of $\Sigma$. Clearly if $\Sigma$ is finite, then $|S_n(\Sigma )|\le |\Sigma |^n$.

For each $l\in \mathbb P$, we define

$$\begin{aligned} B(l) = \phi ^{-1}\big ((-l,l)_\mathbb Z\big )\cap [0,l)\subseteq M \qquad \text {and}\qquad n_l = l+l^3\in \mathbb P. \end{aligned}$$

Note that the “[0, l)” in the definition of B(l) is not “$[0,l)_\mathbb Z$”; in particular, B(l) contains non-integers. We clearly have $B(1)\subseteq B(2)\subseteq \cdots$, and we also have $M=\bigcup _{l\in \mathbb P}B(l)$. Indeed, for the latter, if $\alpha \in M$, then $\alpha \in B(l)$ for any l greater than both $\alpha$ and $|\phi (\alpha )|$. We aim to prove the following:

Proposition A.2

There exist sequences $\alpha _i,\beta _i,\gamma _i$ $(i\in \mathbb P)$ of elements of M satisfying:

• (i) $\lim _{i\rightarrow \infty }\alpha _i=0$,

• (ii) $\lim _{i\rightarrow \infty }\gamma _i=1$,

• (iii) $\gamma _i>1 \text { for all}\,\, i\in \mathbb P$,

• (iv) $\beta _i+\gamma _i=4 \text { for all}\,\, i\in \mathbb P$, and

• (v) $S_n(\Sigma )\cap B(l)=\emptyset$ for all $l\in \mathbb P$ and $n>n_l$, where $\Sigma =\{ {\alpha _i,\beta _i,\gamma _i} : {i\in \mathbb P} \}$.

To prove the proposition, we will construct the $\alpha _i$ series shortly, and after that the $\beta _i,\gamma _i$ series inductively. We will write $\mathbf{A}=\{ {\alpha _i} : {i\in \mathbb P} \}$ and $\mathbf{A}_k=\{ {\alpha _i} : {i\in \{1,\ldots ,k\}} \}$ for each $k\in \mathbb P$, and similarly define the sets $\mathbf{B}$, $\mathbf{C}$, $\mathbf{B}_k$ and $\mathbf{C}_k$. (Of course these sets are only well-defined once their elements have been specified.)

For $k\in \mathbb P$, define

$$\begin{aligned} R_k = (2k+p_k+1) \left( 1+ \sum _{n=0}^{n_k} n_k(3k)^n\right) \in \mathbb P, \end{aligned}$$

noting that $R_1<R_2<\cdots$. For each $k\in \mathbb P$, let $\alpha _k\in M\cap (\frac{1}{k},\frac{2}{k})$ be such that $\phi (\alpha _k)>k(1+R_k)$; such an element $\alpha _k$ exists by Lemma A.1.

We will now inductively construct $\beta _k,\gamma _k$ ($k\in \mathbb P$) satisfying $\beta _k+\gamma _k=4$, $\gamma _k\in (1,1+\frac{1}{k}]$ and

$$\begin{aligned} S_n(\mathbf{A}\cup \mathbf{B}_k\cup \mathbf{C}_k)\cap B(l)=\emptyset \qquad \text {for all }l\in \mathbb P\text { and }n>n_l. \end{aligned}$$

For the base of the induction, we set $\beta _1=\gamma _1=2$. We must show the following:

Lemma A.3

With the above notation, we have $S_n(\mathbf{A}\cup \{2\})\cap B(l)=\emptyset$ for all $l\in \mathbb P$ and $n>n_l$.

Proof

Suppose to the contrary that there exists $\varepsilon \in S_n(\mathbf{A}\cup \{2\})\cap B(l)$ for some $l\in \mathbb P$ and $n>n_l$. Then there exist integers $c_i,d\in \mathbb N$ ($i\in \mathbb P$) such that

$$\begin{aligned} \varepsilon = \sum _{i\in \mathbb P}c_i\alpha _i+2d \qquad \text {and}\qquad \sum _{i\in \mathbb P} c_i + d = n . \end{aligned}$$

In particular, recalling the definition of B(l), we have $l>\varepsilon>c_i\alpha _i>\frac{c_i}{i}$ for each $i\in \mathbb P$, so that $c_i<il$ for each i. Similarly $l>2d\ge d$. Again recalling the definition of B(l), we also have

$$\begin{aligned} \sum _{i\in \mathbb P}c_i\phi (\alpha _i) = \phi (\varepsilon )<l. \end{aligned}$$

But $\phi (\alpha _i)>i(1+R_i)$ for all i, so it follows that $\phi (\alpha _i)\ge 0$ for all $i\in \mathbb P$, and that $\phi (\alpha _i)>l$ for $i>l$. This gives $c_i=0$ for all $i>l$. Putting all of the above together, we have

$$\begin{aligned} l+l^3&= n_l< n = \sum _{i\le l} c_i + d <(l+2l+\cdots +l^2)+l=\frac{l^2(l+1)}{2}+l \\&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad \le \frac{l^2(l+l)}{2}+l = l^3+l, \end{aligned}$$

a contradiction.$\square$

Now suppose $k>1$, and that we have defined the sequences $\beta _i,\gamma _i$ as desired for all $i<k$. Let $K>k$ be such that

$$\begin{aligned} R_K > |\phi (\beta _i)|, |\phi (\gamma _i)| \qquad \text {for all }i<k. \end{aligned}$$

Define the sets

$$\begin{aligned} \Omega = \bigcup _{n=0}^{n_K}\bigcup _{t=1}^{n_K} \frac{\phi \big ( S_n(\mathbf{A}_K\cup \mathbf{B}_{k-1}\cup \mathbf{C}_{k-1})\big )}{t} \qquad \text {and}\qquad \Gamma = \Omega \cup (-\Omega ). \end{aligned}$$

Note that

$$\begin{aligned} |\Gamma | \le 2|\Omega | \le 2 \sum _{n=0}^{n_K}\sum _{t=1}^{n_K} \big |S_n(\mathbf{A}_K\cup \mathbf{B}_{k-1}\cup \mathbf{C}_{k-1})\big | \le 2\sum _{n=0}^{n_K}n_K(3K)^n. \end{aligned}$$

It quickly follows that $\big (|\Gamma |+1\big )(2K+p_k+1) < 2R_K$, and so there exists an integer $p\in \mathbb Z$ such that

$$\begin{aligned}{}[p,p+2K+p_k]_\mathbb Z\subseteq (-R_K,R_K)_\mathbb Z\setminus \Gamma . \end{aligned}$$

(A.3)

By Lemma A.1, we may fix some

$$\begin{aligned} \gamma _k \in \phi ^{-1}\big ( [p+K,p+K+p_k]_\mathbb Z\big ) \cap (1,1+\tfrac{1}{k}) \qquad \text {and we also put}\qquad \beta _k=4-\gamma _k. \end{aligned}$$

Since $\phi (\gamma _k)\in [p+K,p+K+p_k]_\mathbb Z\subseteq [p,p+2K+p_k]_\mathbb Z\subseteq (-R_K,R_K)_\mathbb Z$, we have $|\phi (\gamma _k)|<R_K;$ since $\phi (\beta _k)=-\phi (\gamma _k)$, it follows that $|\phi (\beta _k)|<R_K$ as well. We also claim that

$$\begin{aligned} |\phi (\gamma _k)\pm \omega | > K \qquad \text {for all } \omega \in \Omega . \end{aligned}$$

(A.4)

Indeed, we have $\phi (\gamma _k)\in [p+K,p+K+p_k]_\mathbb Z$, so the set of all integers of distance at most K from $\phi (\gamma _k)$ is contained in $[p,p+2K+p_k]_\mathbb Z$, and by (A.3) the latter interval is disjoint from $\Gamma$. Thus, for any $\omega \in \Omega$, since ${\mp }\omega \in \Gamma$, it follows that the distance from $\phi (\gamma _k)$ to ${\mp }\omega$ is greater than K: i.e., $|\phi (\gamma _k)-({\mp }\omega )|>K$, completing the proof of (A.4).

Lemma A.4

With the above notation, we have $S_n(\mathbf{A}\cup \mathbf{B}_k\cup \mathbf{C}_k)\cap B(l)=\emptyset$ for all $l\in \mathbb P$ and $n>n_l$.

Proof

Suppose to the contrary that there exists $\varepsilon \in S_n(\mathbf{A}\cup \mathbf{B}_k\cup \mathbf{C}_k)\cap B(l)$ for some $l\in \mathbb P$ and $n>n_l$. Then there exist integers $c_i,d_i,e_i\in \mathbb N$ such that

$$\begin{aligned} \varepsilon = \sum _{i\in \mathbb P}c_i\alpha _i + \sum _{i=1}^k(d_i\beta _i+e_i\gamma _i)\in B(l) \qquad \text {and}\qquad \sum _{i\in \mathbb P}c_i + \sum _{i=1}^k(d_i+e_i) = n. \end{aligned}$$

Since $\beta _k+\gamma _k=\beta _1+\gamma _1$, we may assume without loss of generality that $d_k=0$ or $e_k=0$. But we note that $d_k$ and $e_k$ cannot both be zero, or else then $\varepsilon \in S_n(\mathbf{A}\cup \mathbf{B}_{k-1}\cup \mathbf{C}_{k-1})\cap B(l)$, contradicting the assumption that $\beta _i,\gamma _i$ ($i=1,\ldots ,k-1$) have the desired properties. As in the proof of Lemma A.3, we have $c_i<il$ for all $i\in \mathbb P$.

Case 1. Suppose first that $d_k=0$, so that $e_k>0$ as just noted. Also, since each $\beta _i,\gamma _i>1$ and each $\alpha _i>0$, and since $\varepsilon \in B(l)$, we have $\sum _{i=1}^k(d_i+e_i)<\sum _{i=1}^k(d_i\beta _i+e_i\gamma _i)\le \varepsilon <l$. Next note that

$$\begin{aligned}&l > \phi (\varepsilon ) = \sum _{i\in \mathbb P}c_i\phi (\alpha _i) + \sum _{i=1}^k\big (d_i\phi (\beta _i)+e_i\phi (\gamma _i)\big ) \\&\qquad \qquad \ge \sum _{i\in \mathbb P}c_i\phi (\alpha _i) - \sum _{i=1}^k\big (d_i|\phi (\beta _i)|+e_i|\phi (\gamma _i)|\big ), \end{aligned}$$

from which it follows that

$$\begin{aligned}&\sum _{i\in \mathbb P}c_i\phi (\alpha _i)< l + \sum _{i=1}^k\big (d_i|\phi (\beta _i)|+e_i|\phi (\gamma _i)|\big ) \nonumber \\&\qquad \qquad \quad< l + \sum _{i=1}^k(d_iR_K+e_iR_K) = l + R_K\sum _{i=1}^k(d_i+e_i) < l(1+R_K). \end{aligned}$$

(A.5)

We now consider two subcases.

Case 1.1. Suppose $l\ge K$. Then (A.5) gives

$$\begin{aligned} l(1+R_K) > \sum _{i\ge K}c_i\phi (\alpha _i) \ge \sum _{i\ge K}c_ii(1+R_i) \ge \sum _{i\ge K}c_i(1+R_K) \ \ \Rightarrow \ \ \sum _{i\ge K}c_i<l. \end{aligned}$$

From this it follows that

$$\begin{aligned} l+l^3 = n_l&< n = \sum _{i<K}c_i + \sum _{i\ge K}c_i + \sum _{i=1}^k(d_i+e_i) \\&< (l+2l+\cdots +(K-1)l)+l+l = l \frac{K(K-1)}{2} + 2l \le \frac{l^3}{2}+2l. \end{aligned}$$

But $l+l^3<\frac{l^3}{2}+2l$ implies $l^2<2$, a contradiction since $l\ge K>1$.

Case 1.2. Now suppose $l<K$. For $i\ge K$ we have $\phi (\alpha _i)>i(1+R_i)\ge K(1+R_K)$. Together with (A.5), it follows that for any such i,

$$\begin{aligned}&c_iK(1+R_K) \le c_i\phi (\alpha _i)<l(1+R_K) <K(1+R_K) \end{aligned}$$

so that $c_i=0$ for all $i\ge K$.

Setting $t=e_k\ge 1$, we have

$$\begin{aligned} \varepsilon -t\gamma _k = \sum _{i<K}c_i\alpha _i + \sum _{i<k}(d_i\beta _i+e_i\gamma _i) \in S_{n-t}(\mathbf{A}_K\cup \mathbf{B}_{k-1}\cup \mathbf{C}_{k-1}). \end{aligned}$$

But also

$$\begin{aligned} n-t< n&= \sum _{i<K}c_i + \sum _{i=1}^k(d_i+e_i)< (l+2l+\cdots +(K-1)l)+l \\&\qquad \qquad \qquad \qquad \qquad = l\frac{K(K-1)}{2}+l<\frac{K^3}{2}+K<n_K, \end{aligned}$$

and $t=e_k\le \sum _{i\in \mathbb P}c_i + \sum _{i=1}^k(d_i+e_i) = n<n_K$. So it follows that $\phi (\varepsilon )-t\phi (\gamma _k)\in t\Omega$, say $\phi (\varepsilon )-t\phi (\gamma _k)=t\omega$. Then by (A.4),

$$\begin{aligned} |\phi (\varepsilon )| = t|\phi (\gamma _k)+\omega | >tK \ge K. \end{aligned}$$

But also from $\varepsilon \in B(l)$, we have $|\phi (\varepsilon )|<l<K$, so we have arrived at a contradiction again.

Case 2. The case in which $e_k=0$ and $d_k>0$ is almost identical, since $\phi (\beta _k)=-\phi (\gamma _k)$. $\square$

We are now ready to tie together the loose ends.

Proof of Proposition A.2

With respect to the sequences $\alpha _i,\beta _i,\gamma _i$ ($i\in \mathbb P$) constructed above, conditions (i)–(iv) are immediate, while (v) follows from the fact that

$$\begin{aligned}&S_n(\Sigma )\cap B(l) = S_n(\mathbf{A}\cup \mathbf{B}\cup \mathbf{C})\cap B(l) = \bigcup _{k\in \mathbb P}\big (S_n(\mathbf{A}\cup \mathbf{B}_k\cup \mathbf{C}_k)\cap B(l)\big )\\ \end{aligned}$$

for all $n,l\in \mathbb P$. $\square$

We now use Proposition A.2 to construct a step set $X\subseteq \mathbb Z_\times ^2$ with combination (V); cf. Table 1.

Example A.5

In all that follows, we keep the notation above: in particular, the irrational number $\xi >0$, the monoid $M=\{ {a+b\xi } : {a,b\in \mathbb Z,\ a+b\xi \ge 0} \}$ and the sequences $\alpha _i,\beta _i,\gamma _i$ $(i\in \mathbb P)$. Also let

$$\begin{aligned} N = \big \{ {(a,b)\in \mathbb Z^2}: {a+b\xi \ge 0} \big \} \end{aligned}$$

be the additive submonoid of $\mathbb Z^2$ consisting of all lattice points on or above the line $\mathscr {L}$ with equation ${x+\xi y=0}$. The map

$$\begin{aligned} \psi :N\rightarrow M:(a,b)\mapsto a+b\xi \end{aligned}$$

is clearly a surjective monoid homomorphism. In fact, $\psi$ is an isomorphism, as injectivity follows quickly from the irrationality of $\xi$. For each $i\in \mathbb P$, let

$$\begin{aligned} A_i = \psi ^{-1}(\alpha _i) ,\qquad B_i = \psi ^{-1}(\beta _i) ,\qquad C_i = \psi ^{-1}(\gamma _i) , \end{aligned}$$

and put $X=\{ {A_i,B_i,C_i} : {i\in \mathbb P} \}$. Also let $E=(1,0)=\psi ^{-1}(1)$. We claim that:

• (i) X does not satisfy the SLC,

• (ii) X satisfies the LC,

• (iii) X does not have the FPP,

• (iv) X has the BPP.

First note that (ii) is clear, as $\mathscr {L}$ itself witnesses the LC (as $\xi$ is irrational, the only lattice point on $\mathscr {L}$ is O). Item (iii) follows quickly from the fact that $\beta _i+\gamma _i=4$ for all $i\in \mathbb P$; indeed, since $\psi$ is an isomorphism, this implies that $B_i+C_i=\psi ^{-1}(4)=(4,0)=4E$ for all i, and hence $\pi _X(4E)=\infty$.

Fig. 18

A subset of the step set from Example A.5 (not to scale). Some X-walks of the form $B_jC_j$ from $\Pi _X(4E)$ are shown in red (color figure online)

To establish the remaining items, first define $\eta =\sqrt{1+\xi ^2}$. For $A=(u,v)\in N$ write $\delta (A)$ for the (perpendicular) distance from A to $\mathscr {L}$. Then by (2.7), and since $u+v\xi \ge 0$ as $A\in N$, we have

$$\begin{aligned} \delta (A) = \frac{u+v\xi }{\sqrt{1+\xi ^2}} = \frac{\psi (A)}{\eta }. \end{aligned}$$

Next, let $\mathscr {L}'$ and $\mathscr {L}''$ be the lines obtained, respectively, by sliding $\mathscr {L}$ a distance of $\frac{1}{\eta }$ or $\frac{3}{\eta }$ units into the half-plane on the side of $\mathscr {L}$ containing X (or, equivalently, by sliding $\mathscr {L}$ by 1 or 3 units to the right, since $\delta (E)=\frac{1}{\eta }$). This is all shown in Fig. 18. Now,

$$\begin{aligned} \lim _{i\rightarrow \infty }\delta (A_i) = \lim _{i\rightarrow \infty }\frac{\alpha _i}{\eta }=0. \end{aligned}$$

This shows that X contains points arbitrarily close to $\mathscr {L}$, and consequently that:

• (v) no line parallel to $\mathscr {L}$ witnesses the SLC.

We also have

$$\begin{aligned} \lim _{i\rightarrow \infty }\delta (C_i) = \lim _{i\rightarrow \infty }\frac{\gamma _i}{\eta }=\frac{1}{\eta }\qquad \text {and}\qquad \lim _{i\rightarrow \infty }\delta (B_i) = \lim _{i\rightarrow \infty }\frac{\beta _i}{\eta }= \lim _{i\rightarrow \infty }\frac{4-\gamma _i}{\eta }= \frac{3}{\eta }. \end{aligned}$$

This means that the points $C_1,C_2,\ldots$ approach $\mathscr {L}'$ from the right, while $B_1,B_2,\ldots$ approach $\mathscr {L}''$ from the left. Since the points $C_1,C_2,\ldots$ are between the lines $\mathscr {L}'$ and $\mathscr {L}''$, and since a bounded region of $\mathbb R^2$ contains only finitely many lattice points, the y-coordinates of $C_1,C_2,\ldots$ are unbounded, either above or below or both; it follows (since $B_i=4E-C_i$ for all i) that the y-coordinates of $B_1,B_2,\ldots$ are unbounded below or above or both, respectively. Thus, X contains points between $\mathscr {L}'$ and $\mathscr {L}''$ with arbitrarily large positive and negative y-coordinates, and it quickly follows that:

• (vi) $\mathscr {L}$ is the only line through O that witnesses the LC.

Items (v) and (vi), together with Lemma 2.9(ii), show that X does not satisfy the SLC. Figure 18 depicts all the above, but only showing subsequences $A_i$ ($i\in I$), and $B_j,C_j$ ($j\in J$) with monotone y-coordinates (with the y-coordinates of $A_i,C_j$ increasing, and those of $B_j$ decreasing).

Finally, the BPP follows quickly from the properties of the $\alpha _i,\beta _i,\gamma _i$ sequences. Indeed, let $D\in \mathscr {A}_X$ be arbitrary, and fix some $w\in \Pi _X(D)$. Write $w=F_1\cdots F_k$, where $F_1,\ldots ,F_k\in X$, so that ${D=F_1+\cdots +F_k}$. Now consider the real number ${\psi (D)\in M}$, and let $l\in \mathbb P$ be such that $\psi (D)\in B(l)$; the set $B(l)\subseteq M$ was defined just before Proposition A.2. Now, $\psi (D)=\psi (F_1)+\cdots +\psi (F_k)$, and $\psi (F_1),\ldots ,\psi (F_k)$ all belong to $\Sigma =\{ {\alpha _i,\beta _i,\gamma _i} : {i\in \mathbb P} \}$. This means that $\psi (D)\in S_k(\Sigma )\cap B(l)$, and so Proposition A.2 gives $\ell (w)=k\le n_l=l+l^3$. This shows that the set $\{ {\ell (w)} : {w\in \Pi _X(D)} \}$ is contained in $\{1,\ldots ,n_l\}$, and hence is finite. Since $D\in \mathscr {A}_X$ was arbitrary, the BPP has been established.