On Free Numerical Semigroups and the Construction of Minimal Telescopic Sequences

Caleb M. Shor Department of Mathematics Western New England University Springfield, MA 01119 USA

                     cshor@wne.edu

Abstract

A free numerical semigroup is a submonoid of the non-negative integers with finite complement that is additively generated by the terms in a telescopic sequence with gcd 1. However, such a sequence need not be minimal, which is to say that some proper subsequence may generate the same numerical semigroup, and that subsequence need not be telescopic. In this paper, we will see that for a telescopic sequence with any gcd, there is a minimal telescopic sequence that generates the same submonoid. In particular, given a free numerical semigroup we can construct a telescopic generating sequence that is minimal. In the process, we will examine some operations on and constructions of telescopic sequences in general.

1 Introduction

Let ℕ denote the set of positive integers and let ℕ_{0} = ℕ ∪ {0}. For a set A ⊆ ℕ_{0}, let ⟨A⟩ denote the set of all (finite) ℕ_{0}-linear combinations of elements of A. Let S be a submonoid of ℕ_{0}. All submonoids of ℕ_{0} are finitely generated, so S = ⟨A⟩ for some finite A = {a_{1}, …, a_{k}} ⊂ ℕ_{0}. We also write this as S = ⟨a_{1}, …, a_{k}⟩. We say a set A is minimal if ⟨A′⟩ ≠ ⟨A⟩ for all A′ ⊊ A. It is well known that any set has a unique minimal subset that generates the same submonoid, and hence there exists a bijection between submonoids of ℕ_{0} and minimal subsets of ℕ_{0}. (See Rosales and García-Sánchez [19, Cor. 2.8] for details.)

In this paper, we are interested in generating sets that are ordered in some way. We therefore consider (finite) sequences G = (g_{1}, …, g_{k}) for some k ∈ ℕ with g_{i} ∈ ℕ_{0}, which we denote by G ∈ ℕ_{0}^{k}.^{1} We similarly define the submonoid generated by G as ⟨G⟩ = ⟨g_{1}, …, g_{k}⟩. As with sets, a sequence G is minimal if ⟨G′⟩ ≠ ⟨G⟩ for all proper subsequences G′ of G. Any sequence then has a unique minimal subsequence that generates the same submonoid. Observe that any permutation of a minimal sequence is also necessarily minimal.

For G ∈ ℕ_{0}^{k} a sequence with g_{1} + g_{2} > 0, let G_{i} = (g_{1}, …, g_{i}) and d_{i} = gcd(G_{i}) for 1 ≤ i ≤ k. Let c(G) = (c_{2}, …, c_{k}) where c_{j} = d_{j−1}/d_{j} for 2 ≤ j ≤ k.^{2} If c_{j}g_{j} ∈ ⟨G_{j−1}⟩ for all j ≥ 2, then we say G is a telescopic (or smooth) sequence. Some authors include the additional properties where gcd(G) = 1 and/or G is an increasing sequence. In this paper, we require neither.

The reader can confirm that all sequences G ∈ ℕ_{0}^{k} with g_{1} + g_{2} > 0 for k = 1 and k = 2 are telescopic. There are longer sequences that are not telescopic, though some permutation is. One example is G = (4, 5, 6), which is not telescopic, though G′ = (4, 6, 5) is telescopic. And finally, there are sequences for which no permutation is telescopic, such as G = (3, 4, 5).

Telescopic sequences arise naturally in the world of numerical semigroups. They generate so-called free numerical semigroups, which have some nice properties that we will see along with references for further reading in Section 2. Unfortunately, the usage of the word “free” here does not coincide with the categorical idea of free objects.

The motivation for this paper is how the definitions of “telescopic” and “minimal” interact. Consider the following example.

Example 1. Let S = ⟨G⟩ for G = (660, 550, 352, 50, 201) ∈ ℕ_{0}^{5}. We see that c(G) = (6, 5, 11, 2) and that c_{j}g_{j} ∈ ⟨G_{j−1}⟩ for 2 ≤ j ≤ 5, so G is a telescopic sequence. Since gcd(G) = 1, S is a free numerical semigroup. However, G is not minimal because 550 = 0 · 660 + 0 · 352 + 11 · 50 + 0 · 201. We eliminate 550 from G to obtain the proper subsequence G′ = (660, 352, 50, 201) with ⟨G′⟩ = ⟨G⟩ = S. We can see that G′ is minimal. However, G′ is not telescopic.

This leads to the following question.

Question 2. Given a telescopic sequence G, does there exist a telescopic sequence G′ that is minimal and has ⟨G′⟩ = ⟨G⟩?

We can ask this more generally.

Question 3. Suppose G and H are sequences such that ⟨G⟩ = ⟨H⟩. If G is telescopic, must some permutation of H be telescopic?

1By taking G ∈ ℕ_{0}^{k}, we allow for the possibility that g_{i} = g_{j} for i ≠ j. We can also have g_{i} = 0 for some i. Clearly, if we remove any repeats or 0s, the resulting subsequence will still generate the same submonoid.

However, our results hold in the more general case of allowing repeats and/or zeros, so we choose to allow them to give slightly more general results.

2Observe that c_{j} is a well-defined integer when d_{j} ≠ 0. We have d_{j} ≠ 0 for all j precisely when g_{1}+g_{2} > 0.

As Example 1 illustrates, for G telescopic and G′ its unique minimal subsequence, G′ need not be telescopic. In this particular case, the permutation (660, 50, 352, 201) of G′ is telescopic. We will show that this always happens – i.e., that the answer to Question 2 is “yes,” as is the answer to the more general Question 3. In the context of numerical semigroups, this means that any free numerical semigroup is generated by a telescopic minimal sequence, and we will give a procedure to compute it.

1.1 Organization

This paper is organized as follows. In Section 2, we will give some background material on free numerical semigroups. Following that, given a sequence (c_{2}, …, c_{k}) and some d ∈ ℕ, we provide an explicit method (Remark 19) in Section 3 to produce any telescopic sequence G = (g_{1}, …, g_{k}) such that c(G) = (c_{2}, …, c_{k}) and gcd(G) = d. In Section 4, we describe two functions that map telescopic sequences to telescopic sequences. As we will see, any function that maps telescopic sequences to telescopic sequences (with the same gcd) must be a composition of these functions (with certain parameters).

Then, in Section 5 we present a construction that takes a telescopic sequence as input and outputs a minimal telescopic sequence that generates the same submonoid, answering Question 2 affirmatively. The main result is Theorem 52. As a corollary, we find that every free numerical semigroup is generated by a minimal telescopic sequence. We also answer the more general Question 3 affirmatively.

Finally, in Section 6 we combine two results (Remark 19 and Proposition 43) to give an explicit method to construct any minimal telescopic sequence G with c(G) = (c_{2}, …, c_{k}). As an application, we have Corollary 58, which says that any non-decreasing telescopic sequence G = (g_{1}, …, g_{k}) with c_{j} > 1 for all j is necessarily minimal.

2 Background

Free numerical semigroups, which are generated by telescopic sequences G with gcd(G) = 1, have been studied in various contexts by Brauer and Shockley [5], Herzog [10], Bertin and Carbonne [3], Rödseth [17], Kirfel and Pellikaan [12], Rosales and García-Sánchez [18, 19], Leher [13], Ayano [2], Robles-Pérez and Rosales [16], Gassert and Shor [9], and others. We will highlight some of their properties.

2.1 Numerical semigroups

We begin with numerical semigroups. For a comprehensive reference on the subject, see the work of Rosales and García-Sánchez [19].

A numerical semigroup S is a submonoid of ℕ_{0} with finite complement. It is wellknown that every numerical semigroup S is given by S = ⟨A⟩ for some finite A ⊂ ℕ_{0} with gcd(A) = 1. Since we are interested in generating sequences, we equivalently have that every numerical semigroup S is given by S = ⟨G⟩ for some k ∈ ℕ and G ∈ ℕ_{0}^{k} with gcd(G) = 1. Elements of the complement of S are known as gaps of S, and we denote the set of gaps by H(S). The genus of S, denoted g(S), is the number of gaps of S. The Frobenius element of S, denoted F (S), is the largest integer not in S, which is max(H(S)) when S ≠ ℕ_{0}. The embedding dimension of S, denoted e(S), is the cardinality of the unique minimal generating set of S (which is the cardinality of any minimal generating sequence of S).

Given a numerical semigroup S, it can be difficult to compute g(S), F (S), and other properties of the set of gaps. Curtis [6] showed that there cannot be a polynomial formula to compute the Frobenius number of S as a function of the generating elements of S when e(S) > 2 . Ramírez Alfonsín [14] proved that the problem of computing the Frobenius number of S, when e(S) > 2, is NP-hard. For more on the Frobenius problem, see Ramírez Alfonsín’s book [15].

A very helpful tool in understanding the gaps of a numerical semigroup is called the Apéry set [1]. For any nonzero t ∈ S, the Apéry set of S relative to t is

Ap(S; t) = {s ∈ S : s − t ∉ S}.  (1)

Equivalently, Ap(S; t) is the set of elements in S that are minimal in their congruence class modulo t.

If we know Ap(S; t), then we immediately know the genus of S (from Selmer [20]) and the Frobenius number of S (from Brauer and Shockley [5]).

Theorem 4 ([5, Lem. 3], [20, Eqn. 2.3]). For S a numerical semigroup and any nonzero t ∈ S,

F (S) = max(Ap(S; t)) − t,  (2)

and

g(S) = \frac{1 − t}{2} + \frac{1}{t} ∑_{n∈Ap(S;t)} n.  (3)

We can also deduce other properties of the gaps of S with the following identity and an appropriately chosen function f.

Theorem 5 ([9, Thm. 2.3]). For S a numerical semigroup with set of gaps H(S), any nonzero t ∈ S, and any function f defined on ℕ_{0},

∑_{n∈H(S)}[f(n + t) − f(n)] = ∑_{n∈Ap(S;t)} f(n) − ∑_{n=0}^{t−1} f(n).  (4)

For instance, with f(n) = n in Equation (4), we obtain the genus formula in Equation (3). Tuenter [21] presents additional applications in the case where S = ⟨a, b⟩.

2.2 Free numerical semigroups

A numerical semigroup S is a free numerical semigroup if S = ⟨G⟩ for a telescopic sequence G. The following result from Bertin and Carbonne [3, Sect. 2] motivates our interest in free numerical semigroups. We present it for any value of gcd(G), whereas it usually appears in the case of gcd(G) = 1.

Theorem 6. Let G = (g_{1}, …, g_{k}) ∈ ℕ_{0}^{k} be telescopic, let c(G) = (c_{2}, …, c_{k}), and let d = gcd(G). For any n ∈ dℤ, there is a unique representation

n = ∑_{i=1}^{k} n_{i}g_{i},  (5)

with integers n_{1}, …, n_{k} where 0 ≤ n_{j} < c_{j} for j = 2, …, k. Furthermore, for such an n ∈ dℤ, we have n ∈ ⟨G⟩ if and only if n_{1} ≥ 0.

This theorem is a generalization of the result that, given relatively prime positive integers a and b, any integer n can be uniquely written as n = n_{1}a + n_{2}b with n_{1}, n_{2} ∈ ℤ and 0 ≤ n_{2} < a.

We then obtain an explicit description of the Apéry set of a free numerical semigroup relative to the first generating element.

Corollary 7 ([9, Prop. 3.6]). Suppose S is a free numerical semigroup, so S = ⟨G⟩ for G = (g_{1}, …, g_{k}) ∈ ℕ_{0}^{k} a telescopic sequence with gcd(G) = 1. For c(G) = (c_{2}, …, c_{k}), we have

Ap(S; g_{1}) = {∑_{j=2}^{k} n_{j}g_{j} : 0 ≤ n_{j} < c_{j}} .  (6)

Using Corollary 7 with Theorem 4 we obtain the formulas for the Frobenius number and genus of a free numerical semigroup. The formula for F (S) in this case was known to Brauer [4].

Corollary 8. For S a free numerical semigroup generated by G = (g_{1}, …, g_{k}) ∈ ℕ_{0}^{k}, a telescopic sequence with gcd(G) = 1 and c(G) = (c_{2}, …, c_{k}),

F (S) = −g_{1} + ∑_{j=2}^{k}(c_{j} − 1)g_{j},  (7)

and

g(S) = \frac{1}{2} (1 − g_{1} + ∑_{j=2}^{k}(c_{j} − 1)g_{j}) .  (8)

Observe that for S a free numerical semigroup we have F (S) = 2g(S) − 1. Numerical semigroups with this property are symmetric. These semigroups are equivalently characterized as those for which the map ϕ : S → ℤ \ S given by ϕ(s) = F (S) − s is a bijection.

We can combine Corollary 7 with Theorem 5 to obtain an explicit identity for the gaps of a free numerical semigroup.

Corollary 9 ([9, Cor. 3.7]). Suppose S = ⟨G⟩ for G = (g_{1}, …, g_{k}) telescopic and c(G) = (c_{2}, …, c_{k}). For H(S) the set of gaps of S, and for any function f defined on ℕ_{0},

∑_{n∈H(S)}[f(n + g_{1}) − f(n)] = ∑_{n_{2}=0}^{c_{2}−1} ⋯ ∑_{n_{k}=0}^{c_{k}−1} f (∑_{j=2}^{k} n_{j}g_{j}) − ∑_{n=0}^{g_{1}−1} f(n).  (9)

As before, with the function f(n) = n in Equation (9) we recover the genus formula given in Equation (8).

2.3 Prior results

The motivating question for this paper is whether a free numerical semigroup has a minimal telescopic generating sequence. We can answer the question immediately for embedding dimension at most 3.

If e(S) = 1, then S = ℕ_{0} = ⟨G⟩ for G = (1), which is a minimal telescopic sequence. If e(S) = 2, then S = ⟨G⟩ for G = (a, b) with a, b > 1 and gcd(a, b) = 1. The sequence

G = (a, b) is telescopic, so S is generated by a minimal telescopic sequence.

If e(S) = 3, then we need a result of Herzog [10]. (We quote the result as written by Rosales and García-Sánchez [19].)

Theorem 10 ([19, Cor. 9.5]). For S a numerical semigroup with e(S) = 3, S is symmetric if and only if S = ⟨G⟩, for G = (am_{1}, am_{2}, bm_{1} + cm_{2}) where a, b, c, m_{1}, m_{2} ∈ ℕ with gcd(m_{1}, m_{2}) = 1, a, m_{1}, m_{2} ≥ 2, b + c ≥ 2, and gcd(a, bm_{1} + cm_{2}) = 1.

For our purposes, if S is a free numerical semigroup then S is symmetric. If we also have e(S) = 3, then by the above theorem we have S = ⟨G⟩ for G = (am_{1}, am_{2}, bm_{1} + cm_{2}), which is necessarily telescopic (and of course minimal).

This approach will not work when e(S) ≥ 4, however, because there are symmetric numerical semigroups that are not free. For instance, the numerical semigroup S = ⟨e + 1, …, e + e⟩ of embedding dimension e is symmetric and not free for all e ≥ 4.

In what follows, we will take a different approach to show that every free numerical semigroup S is generated by a minimal telescopic sequence.

3 Explicit form of telescopic sequences

In this section, our goal is to obtain an explicit form for the terms in a telescopic sequence, which we will need for our main result in Section 5. We will see a method to construct a telescopic sequence G with gcd(G) = d given a desired sequence c(G) and d ∈ ℕ. Our method uses the same ideas as in “gluing” of numerical semigroups, described by Watanabe [22] and by Rosales and García-Sánchez [19, Chap. 8].

3.1 Notation and preliminaries

For notation, given c_{m+1}, …, c_{n} ∈ ℕ_{0}, let

C_{m,n} = ∏_{j=m+1}^{n} c_{j}.  (10)

If n ≤ m, then this product is empty, so C_{m,n} = 1. In particular, we will make use of the fact that C_{m,m} = 1. Additionally, as was mentioned in the introduction, for i = 1, …, k, let G_{i} = (g_{1}, …, g_{i}). Finally, recall that we will only consider sequences G with g_{1} + g_{2} > 0.

We begin with a few lemmas. Lemma 11. Let G ∈ ℕ_{0}^{k} be any sequence with c(G) = (c_{2}, …, c_{k}). Then gcd(G_{i}) = C_{i,k} gcd(G) for all i = 1, …, k. In particular, if gcd(G) = 1, then gcd(G_{i}) = C_{i,k}. Proof. Observe that

C_{i,k} = c_{i+1}c_{i+2} ⋯ c_{k} = \frac{gcd(G_{i})}{gcd(G_{i+1})} \frac{gcd(G_{i+1})}{gcd(G_{i+2})} ⋯ \frac{gcd(G_{k−1})}{gcd(G_{k})}.

With cancellation and the fact that G_{k} = G, we get C_{i,k} = gcd(G_{i})/ gcd(G), as desired.

For any sequence G = (g_{1}, …, g_{k}) ∈ ℕ_{0}^{k} and any m ∈ ℕ_{0}, let mG = (mg_{1}, …, mg_{k}) ∈ ℕ_{0}^{k}. If m | g_{1}, …, g_{k}, let G/m = (g_{1}/m, …, g_{k}/m) ∈ ℕ_{0}^{k}. Lemma 12. For any G ∈ ℕ_{0}^{k} and any m ∈ ℕ_{0},

1. (mG)_{i} = m(G_{i}); and

2. gcd((mG)_{i}) = m gcd(G_{i}). Proof. Let H = mG = (mg_{1}, …, mg_{k}). Then H_{i} = (mg_{1}, …, mg_{i}) = m(g_{1}, …, g_{i}) = m(G_{i}), so gcd(H_{i}) = gcd(m(G_{i})) = m gcd(G_{i}). Lemma 13. For any G ∈ ℕ_{0}^{k} and any m ∈ ℕ,

1. c(mG) = c(G); and

2. G is telescopic if and only if mG is telescopic.

Proof. Let c(G) = (c_{2}, …, c_{k}), H = mG, and c(H) = (e_{2}, …, e_{k}). For i = 1, …, k, we have H_{i} = m(G_{i}). Thus, for j = 2, …, k,

e_{j} = gcd(H_{j−1})/ gcd(H_{j})
= (m gcd(G_{j−1}))/(m gcd(G_{j}))
= gcd(G_{j−1})/ gcd(G_{j})
= c_{j},

so c(H) = c(G).

Finally, for any j = 2, …, k, suppose c_{j}g_{j} ∈ ⟨G_{j−1}⟩. For m ∈ ℕ, this occurs exactly when c_{j}mg_{j} ∈ ⟨mG_{j−1}⟩. Since e_{j} = c_{j} and h_{j} = mg_{j}, we conclude that c_{j}g_{j} ∈ ⟨G_{j−1}⟩ if and only if e_{j}h_{j} ∈ ⟨H_{j−1}⟩. This holds for all j = 2, …, k, so G is telescopic if and only if H is telescopic.

Let S_{k} denote the symmetric group on k letters. Elements of S_{k} act on sequences G ∈ ℕ_{0}^{k} in a natural way: for σ ∈ S_{k} and G = (g_{1}, …, g_{k}), let σ(G) = (g_{σ(1)}, …, g_{σ(k)}) ∈ ℕ_{0}^{k}. Since σ(G) is a permutation of G, we have ⟨σ(G)⟩ = ⟨G⟩. In the following proposition, we show that the permutation (1 2) ∈ S_{k} takes telescopic sequences to telescopic sequences.

Proposition 14. For k ≥ 2, G = (g_{1}, …, g_{k}) ∈ ℕ_{0}^{k}, and σ = (1 2) ∈ S_{k}, G is telescopic if and only if σ(G) is telescopic.

Proof. Suppose G is telescopic and let H = σ(G). Then H = (h_{1}, …, h_{k}) = (g_{2}, g_{1}, g_{3}, …, g_{k}). Let c(H) = (e_{2}, …, e_{k}).

We have e_{2} = gcd(H_{1})/ gcd(H_{2}) = g_{2}/ gcd(g_{2}, g_{1}), so

e_{2}h_{2} = \frac{g_{2}}{gcd(g_{2}, g_{1})}g_{1} = \frac{g_{1}}{gcd(g_{1}, g_{2})}g_{2}.

Since g_{1}/ gcd(g_{1}, g_{2}) ∈ ℕ_{0}, e_{2}h_{2} ∈ ⟨g_{2}⟩ = ⟨H_{1}⟩.

For i > 1, H_{i} is a permutation of G_{i}, so ⟨H_{i}⟩ = ⟨G_{i}⟩ and gcd(H_{i}) = gcd(G_{i}). For j > 2, e_{j} = gcd(H_{j−1})/ gcd(H_{j}) = gcd(G_{j−1})/ gcd(G_{j}) = c_{j}, and therefore e_{j}h_{j} = c_{j}g_{j}. Since G is telescopic, c_{j}g_{j} ∈ ⟨G_{j−1}⟩, so e_{j}h_{j} ∈ ⟨G_{j−1}⟩ = ⟨H_{j−1}⟩. Thus e_{j}h_{j} ∈ ⟨H_{j−1}⟩ for j = 2, …, k, so H is a telescopic sequence.

For the reverse implication, since σ has order two, if σ(G) is telescopic, then σ(σ(G)) = G is telescopic as well.

Remark 15. Since we already have the restriction that g_{1} + g_{2} > 0, and since G is telescopic exactly when (1 2)(G) is telescopic, for the rest of this paper we will assume g_{1} > 0. Therefore gcd(g_{1}, …, g_{i}) > 0 for all i ≥ 1, and since c_{j} = gcd(g_{1}, …, g_{j−1})/ gcd(g_{1}, …, g_{j}), this will ensure that c_{j} > 0 for all j ≥ 2 as well. We can therefore divide by g_{1}, gcd(G_{i}) for all i, and c_{j} for all j without worrying about possibly dividing by zero.

Finally, we show that the sequence consisting of the first m terms of a telescopic sequence forms a telescopic sequence on its own.

Lemma 16. For any k ∈ ℕ, let G ∈ ℕ_{0}^{k} be a telescopic sequence with g_{1} > 0 and c(G) = (c_{2}, …, c_{k}). For any m ∈ {1, …, k}, the sequence G_{m} = (g_{1}, …, g_{m}) is telescopic with c(G_{m}) = (c_{2}, …, c_{m}). Proof. Let m ∈ {1, …, k}, let H = G_{m}, and let c(H) = (e_{2}, …, e_{m}). Then H = (h_{1}, …, h_{m}) with h_{i} = g_{i} for i = 1, …, m. Observe that h_{1} > 0. We have e_{j} = gcd(H_{j−1})/ gcd(H_{j}) = gcd(G_{j−1})/ gcd(G_{j}) = c_{j} for 2 ≤ j ≤ m. Since c_{j}g_{j} ∈ ⟨G_{j−1}⟩ for j = 2, …, k, and since m ≤ k, it follows that e_{j}h_{j} ∈ ⟨H_{j−1}⟩ for j = 2, …, m. Therefore H is telescopic with c(H) = (c_{2}, …, c_{m}).

3.2 Construction of telescopic sequences

We can now give an explicit description for the elements of a telescopic sequence. We do so first in the case where gcd(G) = 1 and then for any value of gcd(G). Proposition 17. Suppose G = (g_{1}, …, g_{k}) ∈ ℕ_{0}^{k} with gcd(G) = 1 and c(G) = (c_{2}, …, c_{k}). Let z_{1} = 1. Then G is a telescopic sequence if and only if, for each i = 2, …, k, there exists z_{i} ∈ ℕ_{0} such that g_{i} = z_{i}C_{i,k}, gcd(z_{i}, c_{i}) = 1, and

z_{i} ∈ ⟨z_{j}C_{j,i−1} : 1 ≤ j < i⟩ .

Proof. ( ⟹ ) Suppose G is telescopic. For i = 2, …, k, we will use strong induction.

We first show the statement is true for the base case i = 2. Since G is telescopic we have c_{2}g_{2} ∈ ⟨g_{1}⟩. Let z_{2} = c_{2}g_{2}/g_{1} ∈ ⟨1⟩ = ⟨z_{1}C_{1,1}⟩ since z_{1} = C_{1,1} = 1. Then, since g_{1} = C_{1,k} (by Lemma 11), we get g_{2} = z_{2}g_{1}/c_{2} = z_{2}C_{2,k}. By definition c_{2} = g_{1}/ gcd(g_{1}, g_{2}), so C_{2,k} = g_{1}/c_{2} = gcd(g_{1}, g_{2}) = gcd(C_{1,k}, z_{2}C_{2,k}) = gcd(c_{2}C_{2,k}, z_{2}C_{2,k}) = C_{2,k} gcd(c_{2}, z_{2}). Hence gcd(c_{2}, z_{2}) = 1. The conditions are therefore satisfied for i = 2.

For strong induction, for i = 2, …, n, with n < k, we assume g_{i} = z_{i}C_{i,k} with gcd(z_{i}, c_{i}) = 1 and z_{i} ∈ ⟨z_{j}C_{j,i−1} : 1 ≤ j < i⟩. By Lemma 11, g_{1} = C_{1,k} so C_{n,k} | g_{1}. Then, since C_{n,k} | C_{j,k} for j = 2, …, n, by induction C_{n,k} | g_{2}, …, g_{n}. Since G is telescopic, we have c_{n+1}g_{n+1} ∈ ⟨g_{1}, …, g_{n}⟩. We can divide through by C_{n,k} (using the fact that g_{j}/C_{n,k} = z_{j}C_{j,n}) to get

\frac{c_{n+1}g_{n+1}}{C_{n,k}} = \frac{g_{n+1}}{C_{n+1,k}} ∈ ⟨z_{1}C_{1,n}, …, z_{n}C_{n,n}⟩ ⊆ ℕ_{0}.

Let z_{n+1} = g_{n+1}/C_{n+1,k}. Then g_{n+1} = z_{n+1}C_{n+1,k}, and z_{n+1} ∈ ⟨z_{j}C_{j,n} : 1 ≤ j < n + 1⟩. Next, we verify the gcd condition. By Lemma 11, gcd(G_{n}) = C_{n,k}, so

c_{n+1} = \frac{gcd(G_{n})}{gcd(G_{n+1})} = \frac{C_{n,k}}{gcd(C_{n,k}, g_{n+1})}.

Therefore

C_{n+1,k} = C_{n,k}/c_{n+1}
= gcd(C_{n,k}, g_{n+1})
= gcd(C_{n,k}, z_{n+1}C_{n+1,k})
= C_{n+1,k} gcd(c_{n+1}, z_{n+1}),

so gcd(c_{n+1}, z_{n+1}) = 1.

Since we have verified all of the conditions for i = n + 1, by induction the statement is true for all i = 2, …, k.

( ⟸ ) Suppose G = (g_{1}, g_{2}, …, g_{k}) = (C_{1,k}, z_{2}C_{2,k}, …, z_{k}C_{k,k}) with gcd(z_{i}, c_{i}) = 1 and z_{i} ∈ ⟨z_{j}C_{j,i−1} : 1 ≤ j < i⟩ for i = 2, …, k. For G to be telescopic, we need c_{i}g_{i} ∈ ⟨G_{i−1}⟩ for i = 2, …, k. Since c_{i}g_{i} = c_{i}z_{i}C_{i,k} = z_{i}C_{i−1,k} and z_{i} ∈ ⟨z_{j}C_{j,i−1} : 1 ≤ j < i⟩, we have

c_{i}g_{i} = z_{i}C_{i−1,k} ∈ ⟨z_{j}C_{j,i−1}C_{i−1,k} : 1 ≤ j < i⟩
= ⟨z_{j}C_{j,k} : 1 ≤ j < i⟩
= ⟨g_{1}, …, g_{i−1}⟩
= ⟨G_{i−1}⟩

for i = 2, …, k. Thus, G is telescopic.

We now give the result for any gcd(G).

Corollary 18. Suppose G = (g_{1}, …, g_{k}) ∈ ℕ_{0}^{k} and c(G) = (c_{2}, …, c_{k}). Let z_{1} = gcd(G). Then G is a telescopic sequence if and only if, for each i = 2, …, k, there exists z_{i} ∈ ⟨z_{1}⟩ such that g_{i} = z_{i}C_{i,k}, gcd(z_{i}/z_{1}, c_{i}) = 1, and

z_{i} ∈ ⟨z_{j}C_{j,i−1} : 1 ≤ j < i⟩.

Proof. Let d = gcd(G) and H = G/d, so gcd(H) = 1. By Lemma 13, c(H) = c(G) = (c_{2}, …, c_{k}). Let y_{1} = 1. For H = (h_{1}, …, h_{k}), by Proposition 17, H is telescopic if and only if, for each i = 2, …, k, there exists y_{i} ∈ ℕ_{0} such that h_{i} = y_{i}C_{i,k}, gcd(y_{i}, c_{i}) = 1, and y_{i} ∈ ⟨y_{j}C_{j,i−1} : 1 ≤ j < i⟩. Since G = dH, g_{i} = dh_{i}. By Lemma 13, G is telescopic if and only if H is telescopic. Finally, let z_{i} = dy_{i}.

We rewrite the quoted result of Proposition 17 to now say that with z_{1} = dy_{1} = d, G is telescopic if and only if, for each i = 2, …, k, there exists z_{i} ∈ dℕ_{0} such that g_{i} = z_{i}C_{i,k}, gcd(z_{i}/d, c_{i}) = 1, and z_{i} ∈ ⟨z_{j}C_{j,i−1} : 1 ≤ j < i⟩. Since z_{1} = d, the corollary statement follows.

Remark 19. For k ∈ ℕ, given any sequence (c_{2}, …, c_{k}) ∈ ℕ^{k−1} and any d ∈ ℕ, we have a process to construct any telescopic sequence G ∈ ℕ_{0}^{k} for which gcd(G) = d and c(G) = (c_{2}, …, c_{k}). We just need non-negative integers z_{1}, …, z_{k} where z_{1} = d and, for i = 2, …, k, gcd(z_{i}, dc_{i}) = d and z_{i} ∈ ⟨z_{j}C_{j,i−1} : 1 ≤ j < i⟩. Then, for i = 1, …, k, we let g_{i} = z_{i}C_{i,k} to produce G = (g_{1}, …, g_{k}), a sequence for which gcd(G) = d and c(G) = (c_{2}, …, c_{k}).

Example 20. Suppose we want a telescopic sequence G ∈ ℕ_{0}^{5} with gcd(G) = 4 and c(G) = (c_{2}, c_{3}, c_{4}, c_{5}) = (3, 2, 5, 3).

To start, we have z_{1} = gcd(G) = 4.

For z_{2}, z_{3}, z_{4}, z_{5}, we have some choices to make. For z_{2}, we need gcd(z_{2}, 4 · 3) = 4 and z_{2} ∈ ⟨z_{1}⟩. For z_{3}, we need gcd(z_{3}, 4·2) = 4 and z_{3} ∈ ⟨3z_{1}, z_{2}⟩. For z_{4}, we need gcd(z_{4}, 4·5) = 4 and z_{4} ∈ ⟨6z_{1}, 2z_{2}, z_{3}⟩. For z_{5}, we need gcd(z_{5}, 4 · 3) = 4 and z_{5} ∈ ⟨30z_{1}, 10z_{2}, 5z_{3}, z_{4}⟩.

One option is to take z_{2} = z_{3} = z_{4} = z_{5} = 4. With g_{i} = z_{i}C_{i,k}, we get G = (g_{1}, g_{2}, g_{3}, g_{4}, g_{5}) = (360, 120, 60, 12, 4).

Another option is to take z_{2} = 8, z_{3} = 20, z_{4} = 28, z_{5} = 44. With g_{i} = z_{i}C_{i,k}, we get G = (360, 240, 300, 84, 44).

Both sequences are telescopic with gcd(G) = 4 and c(G) = (3, 2, 5, 3).

Observe that the first sequence in Example 20 is not minimal, whereas the second sequence is. In Section 6, we present Corollary 56, a refinement of Remark 19, which allows us to construct any minimal telescopic sequence. We postpone its appearance because it relies on a result (Proposition 43) from Section 5.

3.3 Specific values for certain telescopic sequences

We describe the sequences (c_{2}, …, c_{k}) and (z_{1}, …, z_{k}) that occur for some families of telescopic sequences: geometric, supersymmetric, and compound sequences. Gassert and Shor [8] detail some applications of Corollary 9 to these sequences, as well as connections to certain algebraic curves.

A (finite) geometric sequence G of length k with gcd(G) = 1 is a sequence of the form (g_{1}, …, g_{k}) where g_{i} = a^{k−i}b^{i−1} for a, b ∈ ℕ with gcd(a, b) = 1. In this case, gcd(g_{1}, …, g_{i}) = a^{k−i}, so c_{i} = a for i = 2, …, k. In the notation of Proposition 17, we have z_{i} = b^{i−1} for i = 1, …, k.

As named and studied by Fröberg, Gottlieb, and Häggkvist [7], a supersymmetric sequence G of length k with gcd(G) = 1 is a sequence of the form (g_{1}, …, g_{k}) where g_{i} = A/a_{i} for pairwise coprime natural numbers a_{1}, …, a_{k} and A = a_{1} ⋯ a_{k}. In this case, gcd(g_{1}, …, g_{i}) = A/(a_{1} ⋯ a_{i}), so c_{i} = a_{i}. In the notation of Proposition 17, we have z_{1} = 1 and z_{i} = a_{1} ⋯ a_{i−1} for i = 2, …, k.

Geometric and supersymmetric sequences are special cases of compound sequences, which were named and studied by Kiers, O’Neill, and Ponomarenko [11]. A compound sequence G of length k with gcd(G) = 1 is a sequence of the form (g_{1}, …, g_{k}) where g_{i} = b_{1} ⋯ b_{i−1}a_{i} ⋯ a_{k−1} for a_{i}, b_{j} ∈ ℕ with gcd(a_{i}, b_{j}) = 1 for all i ≥ j. In this case, gcd(g_{1}, …, g_{i}) = a_{i} ⋯ a_{k−1}, so c_{i} = a_{i−1}. In the notation of Proposition 17, we have z_{1} = 1 and z_{i} = b_{1} ⋯ b_{i−1} for i = 2, …, k.

4 Operations on telescopic sequences

In this section, we will introduce two operations: ρ_{n}, which maps a sequence of length k to a sequence of length k − 1; and τ_{g,m}, a gluing map as described by Rosales and García-Sánchez [19, Chap. 8], which maps a sequence of length k to a sequence of length k + 1. With appropriate parameters, these operations “preserve telescopicness,” which is to say they map telescopic sequences to telescopic sequences. We will also show that any function between two telescopic sequences with the same greatest common divisor can be written as a composition of these functions. In particular, ρ_{n} will be useful in Section 5 where we will use it to eliminate redundant terms from a telescopic sequence that is not minimal.

As a reminder, in Remark 15 we saw that we can assume g_{1} > 0 for any sequence G = (g_{1}, …, g_{k}) ∈ ℕ_{0}^{k}. We will continue to make this assumption, from which it follows that gcd(G_{i}) > 0 for all i ≥ 1 and c_{j} > 0 for all j ≥ 2.

4.1 Two useful sequence operations

For k, l ∈ ℕ, let G = (g_{1}, …, g_{k}) ∈ ℕ_{0}^{k} and H = (h_{1}, …, h_{l}) ∈ ℕ_{0}^{l}. For integers i and j with 0 ≤ i < j ≤ k, let G_{i,j} = (g_{i+1}, g_{i+2}, …, g_{j}) ∈ ℕ_{0}^{j−i}. Let G × H = (g_{1}, …, g_{k}, h_{1}, …, h_{l}) ∈ ℕ_{0}^{k+l}.

Using this notation, we have the following results.

Proposition 21. For any G ∈ ℕ_{0}^{k},

1. gcd(G × H) = gcd (gcd(G), gcd(H)) for any H ∈ ℕ_{0}^{l}; and

2. G_{i,j} × G_{j,l} = G_{i,l} for any integers i, j, l with 0 ≤ i < j < l ≤ k.

Proof. The first result is a consequence of the fact that for a, b, c ∈ ℤ, gcd(a, b, c) = gcd(gcd(a, b), c).

The second result is equivalent to saying (g_{i+1}, …, g_{j}) × (g_{j+1}, …, g_{l}) = (g_{i+1}, …, g_{l}), which is true when i < j < l.

We now introduce two operations on sequences that preserve telescopicness. The first, ρ_{n}, produces a sequence with one fewer entry. The second, τ_{g,m}, produces a sequence that has one more entry. As we will see, given any two telescopic sequences G and H with gcd(G) = gcd(H), one can compose finitely many of these functions together to transform G into H.

For the definition of ρ_{n} below, note that for G ∈ ℕ_{0}^{k}, c(G) = (c_{2}, …, c_{k}), and n = 2, …, k, we have c_{n} | C_{n−1,k}. Then, by Lemma 11, c_{n} | gcd(G_{n−1}), so G_{n−1}/c_{n} ∈ ℕ_{0}^{n−1}.

Definition 22. For any k ≥ 2, G ∈ ℕ_{0}^{k}, c(G) = (c_{2}, …, c_{k}), and n = 2, …, k, let

ρ_{n}(G) = (G_{n−1}/c_{n}) × G_{n,k} ∈ ℕ_{0}^{n−1} × ℕ_{0}^{k−n} = ℕ_{0}^{k−1}.  (11)

In other words, ρ_{n}(g_{1}, …, g_{k}) = (g_{1}/c_{n}, …, g_{n−1}/c_{n}, g_{n+1}, …, g_{k}).

Remark 23. We specify k ≥ 2 in the definition because there are no corresponding n for which to define ρ_{n} when k = 1. Remark 24. The definition of ρ_{n} allows us to remove the nth entry of G for any n ∈ {2, …, k}. If we wish to remove the first entry, we can apply the permutation σ = (1 2) first and then apply ρ_{2}.

ρ_{2}(σ(G)) = ρ_{2}(g_{2}, g_{1}, g_{3}, …, g_{k}) = (gcd(g_{2}, g_{1}), g_{3}, …, g_{k}).

Since gcd(g_{2}, g_{1}) = gcd(g_{1}, g_{2}), it follows that ρ_{2}(σ(G)) = ρ_{2}(G). Thus, removal of the first entry is equivalent to removal of the second entry.

Definition 25. For any k ≥ 1, G ∈ ℕ_{0}^{k}, g ∈ ⟨G⟩, and m ∈ ℕ with gcd(m, g) = 1, let

τ_{g,m}(G) = (mG) × (g) ∈ ℕ_{0}^{k+1}.  (12)

In other words, τ_{g,m}(g_{1}, …, g_{k}) = (mg_{1}, …, mg_{k}, g).

Example 26. As in Example 1, let G = (660, 550, 352, 50, 201) ∈ ℕ_{0}^{5}. We have c(G) = (6, 5, 11, 2).

We can apply ρ_{n} for any n ∈ {2, 3, 4, 5}. Applying ρ_{2} (and thereby removing g_{2}), we get ρ_{2}(G) = (G_{1}/c_{2}) × G_{2,5} = (110, 352, 50, 201) ∈ ℕ_{0}^{4}. If we wish to remove g_{1}, we apply the permutation (1 2) first. Let H = (1 2)(G) = (550, 660, 352, 50, 201). Then c(H) = (e_{2}, e_{3}, e_{4}, e_{5}) = (5, 6, 11, 2) and

ρ_{2}((1 2)(G)) = ρ_{2}(H) = (H_{1}/e_{2}) × H_{2,5} = (110, 352, 50, 201) ∈ ℕ_{0}^{4},

which, as expected, is equal to ρ_{2}(G).

We can apply τ_{g,m} for any g ∈ ⟨G⟩ and any m with gcd(m, g) = 1. Applying τ_{251,3}, we have τ_{251,3}(G) = (3G) × (251) = (1980, 1650, 1056, 150, 603, 251) ∈ ℕ_{0}^{6}.

Our goal with ρ_{n} and τ_{g,m} is to determine the conditions under which they send telescopic sequences to telescopic sequences. We begin by investigating their basic properties. In Lemma 27, we see how ρ_{n} and τ_{g,m} act on multiples of sequences. In Lemma 28, we compute gcd(ρ_{n}(G)) and c(ρ_{n}(G)). In Lemma 29, we compute gcd(τ_{g,m}(G)) and c(τ_{g,m}(G)).

Lemma 27. Suppose G ∈ ℕ_{0}^{k} and d ∈ ℕ. For n = 2, …, k, ρ_{n}(dG) = dρ_{n}(G). For any g ∈ ⟨G⟩ and any m ∈ ℕ with gcd(g, m) = 1, τ_{dg,m}(dG) = dτ_{g,m}(G).

Proof. Let c(G) = (c_{2}, …, c_{k}). By Lemma 13, c(dG) = c(G), so c(dG) = (c_{2}, …, c_{k}). Then

ρ_{n}(dG) = ((dG)_{n−1}/c_{n}) × ((dG)_{n,k})
= (d(G_{n−1}/c_{n})) × (d(G_{n,k}))
= d ((G_{n−1}/c_{n}) × G_{n,k})
= dρ_{n}(G).

Next, τ_{dg,m}(dG) = (mdG) × (dg) = d ((mG) × (g)) = dτ_{g,m}(G).

Lemma 28. Let G ∈ ℕ_{0}^{k} with c(G) = (c_{2}, …, c_{k}). For any n = 2, …, k, we have gcd(ρ_{n}(G)) = gcd(G) and c(ρ_{n}(G)) = (c_{2}, …, c_{n−1}, c_{n+1}, …, c_{k}).

Proof. We begin with the case where gcd(G) = 1.

Let H = ρ_{n}(G), so H = (h_{1}, …, h_{k−1}) where, for i = 1, …, n − 1, we have h_{i} = g_{i}/c_{n}, and for i = n, …, k − 1, we have h_{i} = g_{i+1}. Let c(H) = (e_{2}, …, e_{k−1}).

We begin by computing gcd(H_{i}). For i < n, H_{i} = G_{i}/c_{n}. Thus gcd(H_{i}) = gcd (G_{i}/c_{n}). By Lemma 11, gcd(G_{i}) = C_{i,k} = c_{i+1} ⋯ c_{k}. Since i < n, gcd(G_{i}) contains c_{n} as a factor. Therefore gcd (G_{i}/c_{n}) = C_{i,k}/c_{n}.

For i ≥ n, we wish to show gcd(H_{i}) = C_{i+1,k}. We proceed with induction on i. If i = n, H_{n} = (G_{n−1}/c_{n}) × (g_{n+1}). By the previous paragraph, gcd(G_{n−1}/c_{n}) = C_{n,k}. By Proposition 17, g_{n+1} = z_{n+1}C_{n+1,k} with gcd(c_{n+1}, z_{n+1}) = 1. Then

gcd(H_{n}) = gcd ((G_{n−1}/c_{n}) × (g_{n+1}))
= gcd (gcd(G_{n−1}/c_{n}), g_{n+1})
= gcd(C_{n,k}, g_{n+1})
= gcd(c_{n+1}C_{n+1,k}, z_{n+1}C_{n+1,k})
= C_{n+1,k} gcd(c_{n+1}, z_{n+1})
= C_{n+1,k}.

For i > n, by Proposition 17 we have g_{i+2} = z_{i+2}C_{i+2,k} with gcd(c_{i+2}, z_{i+2}) = 1. By induction we assume gcd(H_{i}) = C_{i+1,k}, so

gcd(H_{i+1}) = gcd(h_{1}, …, h_{i+1})
= gcd(gcd(H_{i}), g_{i+2})
= gcd(C_{i+1,k}, z_{i+2}C_{i+2,k})
= gcd(c_{i+2}C_{i+2,k}, z_{i+2}C_{i+2,k})
= C_{i+2,k}.

Therefore gcd(H_{i}) = C_{i+1,k} for i > n. In particular, gcd(H) = gcd(H_{k−1}) = C_{k,k} = 1.

Now we compute e_{j}. For j < n, e_{j} = gcd(H_{j−1})/ gcd(H_{j}) = (C_{j−1,k}/c_{n})/(C_{j,k}/c_{n}) = c_{j}. For j = n, e_{j} = gcd(H_{n−1})/ gcd(H_{n}) = (C_{n−1,k}/c_{n})/C_{n+1,k} = c_{n+1} = c_{j+1}. For j > n, e_{j} = gcd(H_{j−1})/ gcd(H_{j}) = C_{j,k}/C_{j+1,k} = c_{j+1}. Therefore c(H) = (c_{2}, …, c_{n−1}, c_{n+1}, …, c_{k}), as desired.

Now, suppose gcd(G) = d ≥ 1, let G′ = G/d. Since c(G) = c(G′), we have c(G′) = (c_{2}, …, c_{k}). Since gcd(G′) = 1, we apply the above result to obtain gcd(ρ_{n}(G′)) = 1 and c(ρ_{n}(G′)) = (c_{2}, …, c_{n−1}, c_{n+1}, …, c_{k}). By Lemma 27, ρ_{n}(G) = ρ_{n}(dG′) = dρ_{n}(G′), so gcd(ρ_{n}(G)) = gcd(dρ_{n}(G′)) = d gcd(ρ_{n}(G′)) = d and c(ρ_{n}(G)) = c(dρ_{n}(G′)) = c(ρ_{n}(G′)) = (c_{2}, …, c_{n−1}, c_{n+1}, …, c_{k}).

Lemma 29. Let G ∈ ℕ_{0}^{k} with c(G) = (c_{2}, …, c_{k}). For any g ∈ ⟨G⟩ and any m ∈ ℕ with gcd(g, m) = 1, we have gcd(τ_{g,m}(G)) = gcd(G) and c(τ_{g,m}(G)) = c(G) × (m).

Proof. Let H = τ_{g,m}(G), and let c(H) = (e_{2}, …, e_{k+1}). We’ll compute e_{j} for j = 2, …, k, and for j = k + 1.

We have H_{k} = mG. By Lemma 13, c(mG) = c(G). By Lemma 16, c(H_{k}) = (e_{2}, …, e_{k}). Thus e_{j} = c_{j} for j = 2, …, k.

For j = k + 1, first note that

gcd(H) = gcd((mG) × (g))
= gcd(gcd(mG), g)
= gcd(m gcd(G), g)
= gcd(gcd(G), g)
= gcd(G),

where the fourth equality follows from gcd(g, m) = 1 and the final equality follows from the fact that g ∈ ⟨G⟩, which implies that gcd(G) | g. Then

e_{k+1} = gcd(H_{k})/ gcd(H_{k+1})
= gcd(mG_{k})/ gcd(H)
= m gcd(G)/ gcd(G)
= m.

Combining the results for j = 2, …, k and j = k + 1, we have c(H) = (c_{2}, …, c_{k}, m) = c(G) × (m), as desired.

With appropriate parameters, ρ_{n} and τ_{g,m} are inverses of each other as the following lemma shows.

Lemma 30. Let G = (g_{1}, …, g_{k}) ∈ ℕ_{0}^{k} with c(G) = (c_{2}, …, c_{k}), g ∈ ⟨G⟩, and m ∈ ℕ with gcd(g, m) = 1. Then τ_{g_{k},c_{k}}(ρ_{k}(G)) = G and ρ_{k+1}(τ_{g,m}(G)) = G.

Proof. Since ρ_{k}(G) = G_{k−1}/c_{k},

τ_{g_{k},c_{k}}(ρ_{k}(G)) = τ_{g_{k},c_{k}} (G_{k−1}/c_{k})
= (c_{k}G_{k−1}/c_{k}) × (g_{k})
= G_{k−1} × (g_{k})
= G.

By Lemma 29, c(τ_{g,m}(G)) = (c_{2}, …, c_{k}, m), so

ρ_{k+1}(τ_{g,m}(G)) = ρ_{k+1} ((mG) × (g))
= ρ_{k+1} ((mg_{1}, …, mg_{k}, g))
= (mg_{1}, …, mg_{k})/m
= (g_{1}, …, g_{k})
= G.

4.2 Telescopicness-preserving operations

Now that we have developed some of the properties of ρ_{n} and τ_{g,m}, we will see how they map telescopic sequences to telescopic sequences. The goal is to then construct a map between any two telescopic sequences with the same greatest common divisor using some sequence of these maps composed together.

We first show that ρ_{n} preserves telescopicness.

Proposition 31. For k ≥ 2, let G ∈ ℕ_{0}^{k}. For n = 2, …, k, if G is telescopic, then ρ_{n}(G) is telescopic.

Proof. Let H = ρ_{n}(G). Then H = (h_{1}, … h_{k−1}) where h_{i} = g_{i}/c_{n} for i < n, and h_{i} = g_{i+1} for i ≥ n. Let c(H) = (e_{2}, …, e_{k−1}). By Lemma 28, c(H) = (c_{2}, …, c_{n−1}, c_{n+1}, …, c_{k}). Since G is telescopic, c_{j}g_{j} ∈ ⟨G_{j−1}⟩ for j = 2, …, k. We need to show e_{j}h_{j} ∈ ⟨H_{j−1}⟩ for j = 2, …, k − 1.

For i = 1, …, n − 1, H_{i} = G_{i}/c_{n}, so for j = 2, …, n − 1, e_{j} = c_{j}. Since G is telescopic, c_{j}g_{j} ∈ ⟨G_{j−1}⟩. Thus e_{j}h_{j} = c_{j}g_{j}/c_{n} ∈ ⟨G_{j−1}/c_{n}⟩ = ⟨H_{j−1}⟩.

Next, we have c_{n}g_{n} ∈ ⟨G_{n−1}⟩. Since c_{n} | gcd(G_{n−1}), g_{n} ∈ ⟨G_{n−1}/c_{n}⟩, so ⟨G_{n−1}/c_{n}⟩ = ⟨(G_{n−1}/c_{n})×(g_{n})⟩. For i = n, …, k −1, ⟨G_{i}⟩ ⊂ ⟨(G_{n−1}/c_{n})×G_{n−1,i}⟩ = ⟨(G_{n−1}/c_{n})×G_{n,i}⟩ = ⟨H_{i−1}⟩. For j = n, …, k − 1, we have e_{j}h_{j} = c_{j+1}g_{j+1} ∈ ⟨G_{j}⟩ ⊂ ⟨H_{j−1}⟩.

Since e_{j}h_{j} ∈ ⟨H_{j−1}⟩ for j = 2, …, k − 1, H is telescopic.

Remark 32. Unfortunately, Proposition 31 is not an “if and only if” statement. Since all sequences of length 2 are telescopic, we can illustrate this with a sequence of length 3 that is not telescopic. For example, consider the sequence G = (3, 4, 5). We have that c(G) = (c_{2}, c_{3}) = (3, 1). Since 1 · 5 ∉ ⟨3, 4⟩, G is not telescopic. However, ρ_{2}(G) = (1, 5) and ρ_{3}(G) = (3, 4), and both are telescopic sequences.

Next, we show that, with proper parameters, τ_{g,m} preserves telescopicness.

Proposition 33. For k ∈ ℕ, let G ∈ ℕ_{0}^{k}, g ∈ ⟨G⟩, and m ∈ ℕ with gcd(g, m) = 1. Then G is telescopic if and only if τ_{g,m}(G) is telescopic.

Proof. ( ⟹ ) Let H = τ_{g,m}(G), so H = (h_{1}, …, h_{k+1}) with h_{i} = mg_{i} for i = 1, …, k, and h_{k+1} = g. Let c(H) = (e_{2}, …, e_{k+1}). By Lemma 29, c(H) = (c_{2}, …, c_{k}, m). Since G is telescopic, c_{j}g_{j} ∈ ⟨G_{j−1}⟩ for j = 2, …, k. We need to show e_{j}h_{j} ∈ ⟨H_{j−1}⟩ for j = 2, …, k+1.

For j = 2, …, k, e_{j}h_{j} = c_{j}g_{j} ∈ ⟨G_{j−1}⟩ = ⟨H_{j−1}⟩. For j = k+1, e_{j}h_{j} = mg. Since g ∈ ⟨G⟩, mg ∈ ⟨mG⟩ = ⟨H_{k}⟩. Thus e_{k+1}h_{k+1} ∈ ⟨H_{k}⟩. Therefore e_{j}h_{j} ∈ ⟨H_{j−1}⟩ for j = 2, …, k + 1, so H is telescopic.

( ⟸ ) For G = (g_{1}, …, g_{k}), if τ_{g,m}(G) ∈ ℕ_{0}^{k+1} is telescopic, then ρ_{k+1}(τ_{g,m}(G)) is also telescopic. Since ρ_{k+1}(τ_{g,m})(G) = ρ_{k+1}((mG) × (g)) = G, and ρ_{n} maps telescopic sequences to telescopic sequences, we conclude that G is telescopic.

Now that we know ρ_{n} and τ_{g,m} send telescopic sequences to telescopic sequences (using appropriate parameters with τ_{g,m}), in Lemma 34 we will construct a map from ℕ_{0}^{k} to ℕ_{0} using a sequence of ρ_{n} functions that sends G to gcd(G). Following this, in Lemma 35 we will construct a map from ℕ_{0} to ℕ_{0}^{k} using a sequence of τ_{g,m} functions that sends gcd(G) to G.

Lemma 34. For any G ∈ ℕ_{0}^{k} (telescopic or not), let

R_{G} = ρ_{2} ∘ ρ_{3} ∘ ⋯ ∘ ρ_{k} : ℕ_{0}^{k} → ℕ_{0}.  (13)

Then R_{G}(G) = gcd(G).

Proof. If k = 1, then R_{G} is the identity map. Since gcd(g_{1}) = g_{1}, R_{G}(G) = gcd(G).

Now, suppose k > 1. Let c(G) = (c_{2}, …, c_{k}). Then ρ_{k}(G) = G_{k−1}/c_{k} and c(ρ_{k}(G)) = (c_{2}, …, c_{k−1}). Then ρ_{k−1}(ρ_{k}(G)) = (G_{k−2}/c_{k})/c_{k−1} and c(ρ_{k−1}(ρ_{k}(G))) = (c_{2}, …, c_{k−2}). Continuing in this way we find

(ρ_{2} ∘ ρ_{3} ∘ ⋯ ∘ ρ_{k})(G) = G_{1}/(c_{k}c_{k−1} ⋯ c_{2}) = g_{1}/C_{1,k} = gcd(G),

by Lemma 11.

Lemma 35. For G ∈ ℕ_{0}^{k} a telescopic sequence with c(G) = (c_{2}, …, c_{k}) and z_{i} = g_{i}/C_{i,k} for i = 1, …, k, let

T_{G} = τ_{z_{k},c_{k}} ∘ τ_{z_{k−1},c_{k−1}} ∘ ⋯ ∘ τ_{z_{2},c_{2}} : ℕ_{0} → ℕ_{0}^{k}.  (14)

Then T_{G}(gcd(G)) = G.

Proof. If k = 1, then T_{G} is the identity map. Since gcd(g_{1}) = g_{1}, T_{G}(gcd(G)) = G.

Now, suppose k > 1. We first consider the case where gcd(G) = 1. For j = 2, …, k, we wish to show τ_{z_{j},c_{j}} ∘ ⋯ ∘ τ_{z_{2},c_{2}}(1) is defined and equal to (z_{1}C_{1,j}, …, z_{j}C_{j,j}).

For j = 2, since z_{2} ∈ ⟨1⟩, τ_{z_{2},c_{2}}(1) = (c_{2}, z_{2}) = (z_{1}C_{1,2}, z_{2}C_{2,2}).

Now, for induction assume τ_{z_{j},c_{j}} ∘ ⋯ ∘ τ_{z_{2},c_{2}}(1) is defined and equal to (z_{1}C_{1,j}, …, z_{j}C_{j,j}). Since G is telescopic, c_{j+1}g_{j+1} ∈ ⟨G_{j}⟩, so z_{j+1}C_{j,k} ∈ ⟨z_{1}C_{1,k}, …, z_{j}C_{j,k}⟩. It follows that z_{j+1} ∈ ⟨z_{1}C_{1,j}, …, z_{j}C_{j,j}⟩, and therefore z_{j+1} ∈ ⟨τ_{z_{j},c_{j}} ∘ ⋯ ∘ τ_{z_{2},c_{2}}(1)⟩. Then

(τ_{z_{j+1},c_{j+1}} ∘ ⋯ ∘ τ_{z_{2},c_{2}})(1) = τ_{z_{j+1},c_{j+1}}(z_{1}C_{1,j}, …, z_{j}C_{j,j})
= (z_{1}C_{1,j}c_{j+1}, …, z_{j}C_{j,j}c_{j+1}, z_{j+1})
= (z_{1}C_{1,j+1}, …, z_{j}C_{j,j+1}, z_{j+1}C_{j+1,j+1}).

In particular, for j = k, we have

(τ_{z_{k},c_{k}} ∘ τ_{z_{k−1},c_{k−1}} ∘ ⋯ ∘ τ_{z_{2},c_{2}})(1) = (z_{1}C_{1,k}, …, z_{k}C_{k,k}) = G.

Now, suppose gcd(G) = d ≥ 1 and let H = G/d, so H = (h_{1}, …, h_{k}) with h_{i} = g_{i}/d and c(H) = c(G). Let y_{i} = z_{i}/d. By Proposition 17, since g_{i} = z_{i}C_{i,k} with z_{i} ∈ dℕ_{0} for i = 1, …, k, we have h_{i} = y_{i}C_{i,k} with y_{i} ∈ ℕ_{0}. By above,

(τ_{y_{k},c_{k}} ∘ τ_{y_{k−1},c_{k−1}} ∘ ⋯ ∘ τ_{y_{2},c_{2}})(1) = (y_{1}C_{1,k}, …, y_{k}C_{k,k}) = H.

Since τ_{dg,m}(G) = τ_{g,m}(dG) (by Lemma 27), we multiply by d and get

(τ_{dy_{k},c_{k}} ∘ τ_{dy_{k−1},c_{k−1}} ∘ ⋯ ∘ τ_{dy_{2},c_{2}})(d) = (dy_{1}C_{1,k}, …, dy_{k}C_{k,k}) = dH.

Finally, since z_{i} = dy_{i} and dH = G,

(τ_{z_{k},c_{k}} ∘ τ_{z_{k−1},c_{k−1}} ∘ ⋯ ∘ τ_{z_{2},c_{2}})(d) = (z_{1}C_{1,k}, …, z_{k}C_{k,k}) = G.

We now have our result. Given any two telescopic sequences G and H with gcd(G) = gcd(H), we can perform a sequence of ρ_{n} and τ_{g,m} operations on G to produce H. We send G to gcd(G) = gcd(H) and then send gcd(H) to H.

Proposition 36. Let G and H be telescopic sequences with gcd(G) = gcd(H). Then there exist functions ϕ_{G,H} and ϕ_{H,G}, each a finite composition of functions ρ_{n_{i}} and τ_{g_{j},m_{j}} (for parameters n_{i} and g_{j}, m_{j}) such that ϕ_{G,H}(G) = H and ϕ_{H,G}(H) = G.

Proof. By Lemmas 34 and 35, T_{H}(R_{G}(G)) = T_{H}(gcd(G)) = T_{H}(gcd(H)). Since H is telescopic, T_{H}(gcd(H)) = H. Thus, ϕ_{G,H} = T_{H} ∘ R_{G} is composition of ρ_{n_{i}} and τ_{g_{j},m_{j}} functions such that ϕ_{G,H}(G) = H.

Reversing the roles of G and H, since G is telescopic, we have the same result for ϕ_{H,G}.

We conclude this section with an example.

Example 37. Let G = (4, 6, 9) and H = (30, 18, 20, 33). Then gcd(G) = gcd(H) = 1, c(G) = (2, 2), and c(H) = (5, 3, 2). Both sequences are telescopic. Then R_{G} = ρ_{2} ∘ ρ_{3}, and

R_{G}(G) = (ρ_{2} ∘ ρ_{3})(4, 6, 9) = ρ_{2}(2, 3) = 1.

For T_{H}, we first need the z_{i} values for H. Since z_{i} = h_{i}/C_{i,4} for i = 1, 2, 3, 4, we get z_{1} = 1, z_{2} = 3, z_{3} = 10, and z_{4} = 33. Therefore T_{H} = τ_{33,2} ∘ τ_{10,3} ∘ τ_{3,5}, and

T_{H}(1) = (τ_{33,2} ∘ τ_{10,3} ∘ τ_{3,5})(1) = (τ_{33,2} ∘ τ_{10,3})(5, 3) = τ_{33,2}(15, 9, 10) = (30, 18, 20, 33).

Thus, for ϕ_{G,H} = T_{H} ∘ R_{G} = τ_{33,2} ∘ τ_{10,3} ∘ τ_{3,5} ∘ ρ_{2} ∘ ρ_{3}, we have ϕ_{G,H}(G) = H.

We follow the same process for the reverse direction. Here, T_{G} = τ_{9,2} ∘ τ_{3,2} and R_{H} = ρ_{2} ∘ ρ_{3} ∘ ρ_{4}. Therefore ϕ_{H,G} = T_{G} ∘ R_{H} = τ_{9,2} ∘ τ_{3,2} ∘ ρ_{2} ∘ ρ_{3} ∘ ρ_{4} and ϕ_{H,G}(H) = G.

5 Reduction of a telescopic sequence to a minimal telescopic sequence

In this section, we present a method to take a telescopic sequence G and produce a minimal telescopic sequence G′ such that ⟨G′⟩ = ⟨G⟩. The main result is Theorem 52. In the context of free numerical semigroups, this shows that every free numerical semigroup is generated by a telescopic sequence that is minimal. As we will see, the main idea is in Proposition 43, which says there are only two ways in which a telescopic sequence can fail to be minimal.

Before we begin, we introduce one more sequence operation and two helpful lemmas. For G ∈ ℕ_{0}^{k} and n = 1, …, k, let

π_{n}(G) = G_{n−1} × G_{n,k}.  (15)

In other words, for G = (g_{1}, …, g_{k}),

π_{n}(G) = (g_{1}, …, ĝ_{n}, …, g_{k}) = (g_{1}, …, g_{n−1}, g_{n+1}, …, g_{k}) ∈ ℕ_{0}^{k−1}.  (16)

The nth term is removed from G and the indices of all subsequent terms are decreased by one.

With this notation, we have that a sequence G ∈ ℕ_{0}^{k} is minimal if and only if ⟨π_{n}(G)⟩ ≠ ⟨G⟩ for all n = 1, …, k, which occurs if and only if g_{n} ∉ ⟨π_{n}(G)⟩ for all n = 1, …, k.

As in previous sections, we will continue to assume that g_{1} > 0.

Lemma 38. For any sequence G ∈ ℕ_{0}^{k}, let S = ⟨G⟩. Then gcd(G) = gcd(S).

Proof. Let d_{G} = gcd(G) and d_{S} = gcd(S). Since G ⊂ S, d_{S} | d_{G}. For any s ∈ S, s = ∑_{i=1}^{k} a_{i}g_{i} for some non-negative integers a_{i}. Since d_{G} | g_{i} for all i, we have d_{G} | s for all s ∈ S. Since d_{G} is a common divisor for all elements of S, d_{G} | d_{S}. Thus d_{G} = d_{S}.

Lemma 39. Suppose G = (g_{1}, …, g_{k}) ∈ ℕ_{0}^{k} is any sequence (not necessarily telescopic). If g_{n} ∈ ⟨π_{n}(G)⟩ for some n, then gcd(π_{n}(G)) = gcd(G).

Proof. Since ⟨π_{n}(G)⟩ = ⟨G⟩, we use Lemma 38 twice with π_{n}(G) and G to get

gcd(π_{n}(G)) = gcd(⟨π_{n}(G)⟩) = gcd(⟨G⟩) = gcd(G).

5.1 Determination of the two cases for non-minimality of a telescopic sequence

As we will see, there are two ways for which a telescopic sequence can fail to be minimal. In Lemmas 40 and 41, we will show that if one entry of a telescopic sequence can be written as a non-negative linear combination of the remaining elements, then we have a divisibility condition on the coefficient of the term with highest index.

Lemma 40. Let G = (g_{1}, …, g_{k}) ∈ ℕ_{0}^{k} be telescopic with c(G) = (c_{2}, …, c_{k}). Suppose g_{n} ∈ ⟨π_{n}(G)⟩ for some n ∈ {1, …, k}. That is, suppose

g_{n} = ∑_{i=1, i≠n}^{k} a_{i}g_{i}  (17)

for non-negative integers a_{i}. Then c_{k} | a_{k}.

Proof. Since g_{n} ∈ ⟨π_{n}(G)⟩, by Lemma 39, gcd(π_{n}(G)) = gcd(G). We consider two cases: n = k and n < k.

Assume n = k. Since G_{k−1} = (g_{1}, …, g_{k−1}) = π_{k}(G), we have gcd(G_{k−1}) = gcd(G_{k}), so c_{k} = gcd(G_{k−1})/ gcd(G_{k}) = 1, and consequently c_{k} | a_{k}.

Now assume n < k. Since gcd(G_{k}) = gcd(G), then c_{k} = gcd(G_{k−1})/ gcd(G). Therefore, in order to have that c_{k} | a_{k}, it is enough to show that gcd(G_{k−1}) | (a_{k} gcd(G)). From Equation (17) we solve for a_{k}g_{k} to get

a_{k}g_{k} = g_{n} − ∑_{i=1, i≠n}^{k−1} a_{i}g_{i},

so a_{k}g_{k} is a linear combination of g_{1}, …, g_{k−1}. Since gcd(G_{k−1}) | g_{1}, …, g_{k−1}, we have gcd(G_{k−1}) | (a_{k}g_{k}). Then, since gcd (gcd(G_{k−1}), g_{k}) = gcd(G), we conclude that gcd(G_{k−1}) | (a_{k} gcd(G)).

Lemma 41. Let G = (g_{1}, …, g_{k}) ∈ ℕ_{0}^{k} be a telescopic sequence with c(G) = (c_{2}, …, c_{k}). Suppose there exist n and m with 1 ≤ n < m ≤ k such that g_{n} ∈ ⟨π_{n}(G_{m})⟩. That is, suppose

g_{n} = ∑_{i=1, i≠n}^{m} a_{i}g_{i}  (18)

for non-negative integers a_{i}. Then c_{m} | a_{m}.

Proof. Suppose g_{n} ∈ ⟨π_{n}(G_{m})⟩ for some m > n. Let H = G_{m}, a sequence of length m. By Lemma 16, H is telescopic with c(H) = (c_{2}, …, c_{m}). Since g_{n} ∈ ⟨π_{n}(H)⟩, we apply Lemma 40 to H to conclude that c_{m} | a_{m}.

We need one more lemma before we can state our main result on the form of a nonminimal telescopic sequence.

Lemma 42. For G = (g_{1}, …, g_{k}) ∈ ℕ_{0}^{k} telescopic with c(G) = (c_{2}, …, c_{k}), suppose g_{n} ∈ ⟨π_{n}(G_{m})⟩ for some m and n with 1 ≤ n ≤ m ≤ k. Then g_{n} ∈ ⟨π_{n}(G_{m−1})⟩ or g_{n} = c_{m}g_{m}.

Proof. First, suppose n = m. Since π_{n}(G_{n}) = (g_{1}, …, g_{n−1}) = π_{n}(G_{n−1}), if g_{n} ∈ ⟨π_{n}(G_{m})⟩ then g_{n} ∈ ⟨π_{n}(G_{m−1})⟩, as desired. (Additionally, we have that c_{m} = gcd(G_{m})/ gcd(G_{m−1}) = 1 in this case. Since g_{n} = g_{m}, we also have g_{n} = c_{m}g_{m}.)

Now suppose n < m. Suppose g_{n} ∈ ⟨π_{n}(G_{m})⟩ and g_{n} ∉ ⟨π_{n}(G_{m−1})⟩. We wish to show that g_{n} = c_{m}g_{m}.

Since g_{n} ∈ ⟨π_{n}(G_{m})⟩, there exist non-negative integers a_{i} such that

g_{n} = ∑_{i=1, i≠n}^{m} a_{i}g_{i}.  (19)

Since g_{n} ∉ ⟨π_{n}(G_{m−1})⟩, we must have a_{m} > 0. By Lemma 41, c_{m} | a_{m}, so we let q = a_{m}/c_{m} ∈ ℕ. For G telescopic, c_{m}g_{m} ∈ ⟨G_{m−1}⟩, so there are b_{1}, …, b_{m−1} ∈ ℕ_{0} such that

c_{m}g_{m} = b_{1}g_{1} + ⋯ + b_{m−1}g_{m−1}.  (20)

Thus a_{m}g_{m} = qc_{m}g_{m} = q ∑_{i=1}^{m−1} b_{i}g_{i}, which we plug into Equation (19) to obtain

g_{n} = qb_{n}g_{n} + ∑_{i=1, i≠n}^{m−1}(qb_{i} + a_{i})g_{i}.  (21)

Since g_{n} ∉ ⟨π_{n}(G_{m−1})⟩, we must have qb_{n} ≠ 0. Since qb_{n} ∈ ℕ, this implies qb_{n} = 1, so (qb_{i} + a_{i})g_{i} = 0 for i = 1, …, m − 1, with i ≠ n. Therefore q = b_{n} = 1 and a_{i}g_{i} = b_{i}g_{i} = 0 for i = 1, …, m − 1, with i ≠ n. Since q = 1, a_{m} = c_{m}. Finally, we plug these values into either Equation (19) or Equation (20) to conclude that g_{n} = c_{m}g_{m}.

We now have our result.

Proposition 43. For G = (g_{1}, …, g_{k}) ∈ ℕ_{0}^{k} a telescopic sequence, suppose g_{n} ∈ ⟨π_{n}(G)⟩. Then g_{n} ∈ ⟨G_{n−1}⟩ or g_{n} = c_{m}g_{m} for some m > n.

Proof. This follows immediately from Lemma 42.

Therefore, if a telescopic sequence G is not minimal, there are two cases: Case 1, where g_{n} ∈ ⟨G_{n−1}⟩; and Case 2, where g_{n} = c_{m}g_{m} for some m > n.

Proposition 43 gives us a straightforward criterion to determine whether a given telescopic sequence is minimal.

Corollary 44. Suppose G = (g_{1}, …, g_{k}) ∈ ℕ_{0}^{k} is telescopic with c(G) = (c_{2}, …, c_{k}). Let H = (h_{2}, …, h_{k}) = (c_{2}g_{2}, …, c_{k}g_{k}). Then G is minimal if and only if g_{i} ≠ h_{j} for all i, j.

Proof. ( ⟹ ) Suppose G is minimal. Then g_{j} ∉ ⟨G_{j−1}⟩ for all j ≥ 2. Since G is telescopic, c_{j}g_{j} ∈ ⟨G_{j−1}⟩ for all j ≥ 2. Thus g_{j} ≠ c_{j}g_{j} for all j ≥ 2.

Also, since G is minimal, g_{i} ∉ ⟨g_{j}⟩ for all i ≠ j. In particular, we have g_{i} ≠ c_{j}g_{j} for all i ≠ j. Combined with the previous paragraph, we have g_{i} ≠ h_{j} for all i, j.

( ⟸ ) Suppose G is not minimal, so g_{i} ∈ ⟨π_{i}(G)⟩ for some i. By Proposition 43, we have either g_{i} ∈ ⟨π_{i}(G_{i−1})⟩ or g_{i} = c_{j}g_{j} for some j > i. In the first case, gcd(g_{1}, …, g_{i}) = gcd(g_{1}, …, g_{i−1}), so c_{i} = 1. Therefore g_{i} = c_{i}g_{i} = h_{i}. In the second case, g_{i} = h_{j}.

The following example illustrates the two cases of Proposition 43.

Example 45. Let G = (660, 550, 352, 902, 50, 201) a telescopic sequence with c(G) = (6, 5, 1, 11, 2). We have g_{2} ∈ ⟨π_{2}(G)⟩ and g_{4} ∈ ⟨π_{4}(G)⟩. Observe that g_{2} = c_{5}g_{5}, which is Case 2. And g_{4} = g_{2} + g_{3}, which is Case 1.

For each case, we will see how to remove g_{n} without losing the telescopic property of the generating sequence. We will illustrate our methods with the above example.

5.1.1 Case 1

For the case where g_{n} ∈ ⟨G_{n−1}⟩, we use a result (Proposition 31) about ρ_{n} from Section 4.

Corollary 46. Suppose G = (g_{1}, …, g_{k}) ∈ ℕ_{0}^{k} is telescopic with g_{1} > 0 and that g_{n} ∈ ⟨G_{n−1}⟩ for some n. Then n > 1, c_{n} = 1, and π_{n}(G) is a telescopic sequence with ⟨π_{n}(G)⟩ = ⟨G⟩.

Proof. Suppose n = 1. Then G_{n−1} = G_{0} = (), the empty sequence, so ⟨G_{0}⟩ = {0}. Thus g_{1} = 0. However, since we have assumed that g_{1} > 0, this cannot occur. Therefore n > 1.

Now, let c(G) = (c_{2}, …, c_{k}). If g_{n} ∈ ⟨G_{n−1}⟩, then ⟨G_{n−1}⟩ = ⟨G_{n}⟩ so

c_{n} = gcd(G_{n−1})/ gcd(G_{n}) = 1.

By Proposition 31, the sequence ρ_{n}(G) is telescopic. Since c_{n} = 1,

ρ_{n}(G) = (g_{1}/c_{n}, …, g_{n−1}/c_{n}, g_{n+1}, …, g_{k}) = (g_{1}, …, g_{n−1}, g_{n+1}, …, g_{k}) = π_{n}(G),

so π_{n}(G) is telescopic. Also, since ⟨G_{n−1}⟩ = ⟨G_{n}⟩, ⟨G_{n−1} ×G_{n,k}⟩ = ⟨G_{n} ×G_{n,k}⟩, so ⟨π_{n}(G)⟩ = ⟨G⟩, as desired.

In this case, we can therefore remove g_{n} to produce a shorter telescopic sequence that generates the same submonoid.

Example 47. For the telescopic sequence G = (660, 550, 352, 902, 50, 201) with c(G) = (6, 5, 1, 11, 2) from Example 45, g_{4} = 902 = 550 + 352 = g_{2} + g_{3} ∈ ⟨G_{3}⟩. To remove g_{4} from G, we compute π_{4}(G) = (660, 550, 352, 50, 201), a telescopic sequence with c(π_{4}(G)) = (6, 5, 11, 2) and ⟨π_{4}(G)⟩ = ⟨G⟩.

5.1.2 Case 2

Now we consider the case where g_{n} = c_{m}g_{m} for m > n. Instead of just removing g_{n} (like we did in Case 1), we will first swap the positions of g_{n} and g_{m} before removing g_{n}. As the following lemma states, this is equivalent to a permutation from S_{k−1} acting on π_{n}(G).

Lemma 48. For G ∈ ℕ_{0}^{k}, suppose 1 ≤ n < m ≤ k and consider the transposition (n m) ∈ S_{k}. Then π_{m}((n m)(G)) = σ(π_{n}(G)) for σ ∈ S_{k−1} defined by

σ(i) = \begin{cases}i, & if i < n or i ≥ m; \\ n, & if i = m − 1; \\ i + 1, & if n ≤ i < m − 1. \end{cases}  (22)

We now have a lemma with two results about greatest common divisors that will be useful for the main result of the g_{n} = c_{m}g_{m} case. Since c_{1} is not defined, we will assume n > 1 for the following lemma and proposition. We will then address the possibility of n = 1 in Theorem 52 with the help of the permutation (1 2).

Lemma 49. For G = (g_{1}, …, g_{k}) ∈ ℕ_{0}^{k} a telescopic sequence with c(G) = (c_{2}, …, c_{k}) and gcd(G) = d, if g_{n} = c_{m}g_{m} for some m, n with 1 < n < m ≤ k, then g_{n} = z_{n}C_{n,k} with z_{n} ∈ ⟨d⟩ and gcd(z_{n}/d, c_{n}) = 1. In addition we have gcd(z_{n}/d, c_{m}) = 1 and gcd(c_{j}, c_{m}) = 1 for all n < j < m.

Proof. By Proposition 17, g_{n} = z_{n}C_{n,k} with gcd(z_{n}/d, c_{n}) = 1 and g_{m} = z_{m}C_{m,k} with gcd(z_{m}/d, c_{m}) = 1. Since g_{n} = c_{m}g_{m}, we have z_{n}C_{n,k} = c_{m}z_{m}C_{m,k}, so z_{n}C_{n,m−1} = z_{m}. Therefore (z_{n}/d)C_{n,m−1} = (z_{m}/d).

For the first greatest common divisor statement, (z_{n}/d) | (z_{m}/d), so gcd(z_{n}/d, c_{m}) | gcd(z_{m}/d, c_{m}), which is 1. Thus gcd(z_{n}/d, c_{m}) = 1.

For the second greatest common divisor statement, for n < j < m since c_{j} | C_{n,m−1}, c_{j} | (z_{m}/d). Then gcd(c_{j}, c_{m}) | gcd(z_{m}/d, c_{m}), which is 1. Thus gcd(c_{j}, c_{m}) = 1.

We now have our main result for this case.

Proposition 50. For G = (g_{1}, …, g_{k}) ∈ ℕ_{0}^{k} telescopic with c(G) = (c_{2}, …, c_{k}), suppose g_{n} = c_{m}g_{m} for some m, n with 1 < n < m ≤ k. For the transposition (n m) ∈ S_{k}, the sequence π_{m}((n m)(G)) is telescopic and ⟨π_{m}((n m)(G))⟩ = ⟨G⟩.

Proof. For H = π_{m}((n m)(G)), by Lemma 48, H is a permutation of π_{n}(G), and since g_{n} ∈ ⟨π_{n}(G)⟩, ⟨H⟩ = ⟨π_{n}(G)⟩ = ⟨G⟩.

We have H = (h_{1}, …, h_{k−1}) ∈ ℕ_{0}^{k−1} where

h_{i} = \begin{cases}g_{i}, & for i = 1, …, m − 1 with i ≠ n; \\ g_{m}, & for i = n; \\ g_{i+1}, & for i = m, …, k − 1. \end{cases}

Let c(H) = (e_{2}, …, e_{k−1}). To show H is telescopic, we must show e_{j}h_{j} ∈ ⟨H_{j−1}⟩ for 2 ≤ j ≤ k − 1. We will consider five subintervals of indices: 2 ≤ j < n; j = n; n < j < m; j = m; and m < j ≤ k − 1.

Since H_{n−1} = G_{n−1} and G is telescopic, by Lemma 16 H_{n−1} is telescopic, which implies that e_{j}h_{j} ∈ ⟨H_{j−1}⟩ for 2 ≤ j ≤ n − 1.

Suppose j = n. Let d = gcd(G). By Corollary 18, g_{n} = z_{n}C_{n,k} for some z_{n} ∈ dℕ_{0} with gcd(z_{n}/d, c_{n}) = 1. Then

gcd(H_{n}) = gcd(h_{1}, …, h_{n})

= gcd(g_{1}, …, g_{n−1}, g_{m}) = gcd(gcd(G_{n−1}), g_{n}/c_{m}) = gcd(C_{n−1,k}d, z_{n}C_{n,k}/c_{m})

= \frac{C_{n,k}d}{c_{m}} gcd(c_{m}c_{n}, z_{n}/d).

Note that C_{n,k}/c_{m} ∈ ℕ since m > n. Since gcd(z_{n}/d, c_{n}) = 1 and gcd(z_{n}/d, c_{m}) = 1 (the latter from Lemma 49), gcd(H_{n}) = C_{n,k}d/c_{m}. Since gcd(H_{n−1}) = gcd(G_{n−1}), we have e_{n} = gcd(H_{n−1})/ gcd(H_{n}) = gcd(G_{n−1})/(C_{n,k}d/c_{m}) = c_{m}c_{n}, so e_{n}h_{n} = c_{m}c_{n}g_{n}/c_{m} = c_{n}g_{n}, which is in ⟨G_{n−1}⟩ since G is telescopic. And since H_{n−1} = G_{n−1}, we have e_{n}h_{n} ∈ ⟨H_{n−1}⟩.

From the j = n case, we saw gcd(H_{n}) = C_{n,k}d/c_{m}. By Corollary 18 again, g_{n+1} = z_{n+1}C_{n+1,k} for some z_{n+1} ∈ dℕ with gcd(z_{n+1}/d, c_{n+1}) = 1. Then,

gcd(H_{n+1}) = gcd(g_{1}, …, g_{n−1}, g_{m}, g_{n+1})

= gcd(C_{n,k}d/c_{m}, g_{n+1})

= gcd(C_{n,k}d/c_{m}, z_{n+1}C_{n+1,k})

= \frac{C_{n+1,k}d}{c_{m}} gcd(c_{n+1}, c_{m}z_{n+1}/d)

= \frac{C_{n+1,k}d}{c_{m}},

since gcd(c_{n+1}, z_{n+1}/d) = 1 and gcd(c_{n+1}, c_{m}) = 1 (the latter from Lemma 49).

Continuing in this way, we find that gcd(H_{i}) = C_{i,k}d/c_{m} for n ≤ i < m. Therefore, for n < j < m, e_{j} = gcd(H_{j−1})/ gcd(H_{j}) = c_{j}. Since G is telescopic, c_{j}g_{j} ∈ ⟨G_{j−1}⟩. With g_{n} = c_{m}g_{m} and h_{n} = g_{m}, we have g_{n} ∈ ⟨h_{n}⟩, so ⟨G_{j−1}⟩ ⊂ ⟨H_{j−1}⟩. Thus e_{j}h_{j} = c_{j}g_{j} ∈ ⟨G_{j−1}⟩ ⊆ ⟨H_{j−1}⟩ for n < j < m.

Suppose j = m. We first note that ⟨G_{m}⟩ = ⟨H_{m−1}⟩. Then, since H_{m} is a permutation of π_{n}(G_{m+1}), we have ⟨H_{m}⟩ = ⟨π_{n}(G_{m+1})⟩ = ⟨G_{m+1}⟩, the latter equality holding because g_{n} ∈ ⟨g_{m}⟩ ⊂ ⟨π_{n}(G_{m+1})⟩. Thus gcd(H_{m}) = gcd(G_{m+1}) = C_{m+1,k}d, from which it follows that e_{m} = gcd(H_{m−1})/ gcd(H_{m}) = (C_{m−1,k}d/c_{m})/(C_{m+1,k}d) = c_{m+1}. Since G is telescopic, c_{m+1}g_{m+1} ∈ ⟨G_{m}⟩. Then e_{m}h_{m} = c_{m+1}g_{m+1} ∈ ⟨G_{m}⟩ = ⟨H_{m−1}⟩.

Finally, for m ≤ i ≤ k − 1, H_{i} is a permutation of π_{n}(G_{i+1}), so ⟨H_{i}⟩ = ⟨G_{i+1}⟩ and gcd(H_{i}) = gcd(G_{i+1}) = C_{i+1,k}d. Then for m < j ≤ k − 1, e_{j} = gcd(H_{j−1})/ gcd(H_{j}) = gcd(G_{j})/ gcd(G_{j+1}) = c_{j+1}. Since G is telescopic, c_{j+1}g_{j+1} ∈ ⟨G_{j}⟩. Thus e_{j}h_{j} = c_{j+1}g_{j+1} ∈ ⟨G_{j}⟩ = ⟨H_{j−1}⟩ for m < j ≤ k − 1.

As a result, we can therefore remove g_{n} and reorder the remaining terms to produce a shorter telescopic sequence that generates the same submonoid.

Example 51. For the telescopic sequence G = (660, 550, 352, 902, 50, 201) with c(G) = (6, 5, 1, 11, 2) from Example 45, g_{2} = 550 = 11·50 = c_{5}g_{5}. To remove g_{2} from G, we compute

π_{5}((2 5)(G)) = π_{5}(660, 50, 352, 902, 550, 201) = (660, 50, 352, 902, 201).

Then c(π_{5}((2 5)(G))) = (66, 5, 1, 2), π_{5}((2 5)(G)) is telescopic, and ⟨π_{5}((2 5)(G))⟩ = ⟨G⟩.

5.2 Answers to Questions 2 and 3

If a telescopic sequence G is not minimal, then there is some n such that g_{n} ∈ ⟨π_{n}(G)⟩. In Cases 1 and 2, we saw how to remove g_{n} and produce a shorter telescopic sequence that generates the same submonoid. We can now answer Question 2.

Theorem 52. Let G ∈ ℕ_{0}^{k} be telescopic. Then there exists a minimal telescopic sequence G′ such that ⟨G′⟩ = ⟨G⟩.

Proof. If G is minimal, we are done. Otherwise, for G = (g_{1}, …, g_{k}), there is some n for which g_{n} ∈ ⟨π_{n}(G)⟩. By Proposition 43, either g_{n} ∈ ⟨G_{n−1}⟩ (Case 1) or, for c(G) = (c_{2}, …, c_{k}), g_{n} = c_{m}g_{m} for some m > n (Case 2).

For Case 1, if g_{n} ∈ ⟨G_{n−1}⟩, then by Corollary 46, π_{n}(G) is a telescopic sequence of length k − 1 such that ⟨π_{n}(G)⟩ = ⟨G⟩.

For Case 2, if g_{n} = c_{m}g_{m} for some m > n, we consider two cases of n. If n > 1, then by Proposition 50, π_{m}((n m)(G)) is a telescopic sequence of length k − 1 such that ⟨π_{m}((n m)(G))⟩ = ⟨G⟩.

If n = 1 and g_{2} > 0, we transpose the first two terms and use the previous paragraph to remove the (new) second term. Let H = (1 2)(G). We have H = (h_{1}, …, h_{k}), a telescopic sequence (by Proposition 14) with h_{1} > 0, h_{2} ∈ ⟨π_{2}(H)⟩, and ⟨H⟩ = ⟨G⟩. By Proposition 50, π_{m}((2 m)(H)) is a telescopic sequence of length k−1 such that ⟨π_{m}((2 m)(H))⟩ = ⟨H⟩ = ⟨G⟩.

Now, to construct the minimal telescopic sequence, starting with G we first iteratively remove all of the Case 1 terms (in any order). Observe that this removes any zeros. Then, from the resulting sequence, we can iteratively remove all of the Case 2 terms (with n > 1 and n = 1). Since G ∈ ℕ_{0}^{k} and we remove one term with each step, this process terminates in fewer than k steps, producing a telescopic sequence G′ that is necessarily minimal and satisfies ⟨G′⟩ = ⟨G⟩.

Example 53. Once again using the telescopic sequence G = (660, 550, 352, 902, 50, 201) with c(G) = (6, 5, 1, 11, 2) from Example 45, we have g_{n} ∈ ⟨π_{n}(G)⟩ for n = 2 and n = 4. In Example 47, we removed g_{4} from G to get the telescopic sequence H = π_{4}(G) = (660, 550, 352, 50, 201) with c(H) = (6, 5, 11, 2). In Example 51, we removed g_{2} from G to get the telescopic sequence H̄ = π_{5}((2 5)(G)) = (660, 50, 352, 902, 201) with c(H̄) = (66, 5, 1, 2). Of course, neither of these resulting sequences is minimal.

In H = (h_{1}, …, h_{5}), h_{2} = 11h_{4}, which is Case 2. We therefore compute π_{4}((2 4)(H)) = π_{4}(660, 50, 352, 550, 201) = (660, 50, 352, 201), a telescopic sequence that generates the same submonoid as H. Observe that this sequence is also minimal. (On its own, this paragraph addresses the motivating example in Example 1.)

In H̄ = (h̄_{1}, …, h̄_{5}), h̄_{4} = 11h̄_{2} + 1h̄_{3}, which is Case 1. We therefore compute π_{4}(H̄) = (660, 50, 352, 201), which is the same sequence as in the previous paragraph.

The result is that, starting with the telescopic sequence G = (660, 550, 352, 902, 50, 201), after two steps we produce the sequence G′ = (660, 50, 352, 201) for which c(G′) = (66, 5, 2). Then G′ is telescopic and minimal, and ⟨G′⟩ = ⟨G⟩.

Since a free numerical semigroup is one that is generated by a (not necessarily minimal) telescopic sequence G with gcd(G) = 1, we get the following.

Corollary 54. Suppose S is a free numerical semigroup. Then S is generated by a telescopic sequence that is minimal.

We conclude this section by answering Question 3.

Corollary 55. Let G and H be sequences with ⟨G⟩ = ⟨H⟩. Then a permutation of G is telescopic if and only if a permutation of H is telescopic.

Proof. Suppose G is telescopic and that ⟨G⟩ = ⟨H⟩. By Theorem 52 there is a minimal telescopic sequence G′ such that ⟨G′⟩ = ⟨G⟩, so ⟨G′⟩ = ⟨H⟩ as well. Since G′ is minimal, each term in G′ must appear in H. Consider the permutation

σ(H) = G′ × H′,

where H′ consists of the remaining terms of H not included in G′. Each term in H′ is in ⟨G′⟩, so c(σ(H)) = c(G′) × (1, …, 1). Since G′ is telescopic, the telescopic conditions hold for the G′ portion of σ(H). And since 1 times each term in H′ is in ⟨G′⟩, the telescopic conditions hold for the H′ portion of σ(H). Therefore, σ(H) is a telescopic sequence.

Switching the roles of G and H, we find the reverse implication holds as well.

6 Construction of minimal telescopic sequences with desired properties

We now look at necessary and sufficient conditions for a constructed telescopic sequence to be minimal. Suppose G = (g_{1}, …, g_{k}) ∈ ℕ_{0}^{k} and c(G) = (c_{2}, …, c_{k}). If G is telescopic and not minimal, then g_{n} ∈ ⟨π_{n}(G)⟩ for some n, so by Proposition 43, either

1. g_{n} ∈ ⟨G_{n−1}⟩; or

2. there is some m > n such that g_{m} | g_{n}.

The first case occurs precisely when c_{n} = 1, which we can avoid by requiring c_{j} > 1 for all j = 2, …, k. The second case occurs precisely when z_{m}C_{m,k} | z_{n}C_{n,k}, which we can avoid by requiring z_{j} ∤ z_{i}C_{i,j} for all i, j with 1 ≤ i < j ≤ k.

Corollary 56. Suppose G = (g_{1}, …, g_{k}) is a telescopic sequence (with notation as in Corollary 18). Then G is minimal if and only if we additionally have c_{j} > 1 for j = 2, …, k and z_{j} ∤ z_{i}C_{i,j} for all 1 ≤ i < j ≤ k.

Example 57. Suppose we want a free numerical semigroup S = ⟨G⟩ where G is minimal and telescopic with

c(G) = (c_{2}, c_{3}, c_{4}, c_{5}) = (2, 3, 4, 5).

To generate a numerical semigroup, we need gcd(G) = 1, so we have z_{1} = gcd(G) = 1. Since c_{j} > 1 for all j, for minimality we need only satisfy the non-divisibility conditions for z_{2}, …, z_{5}. We need z_{j} ∈ ℕ where

• z_{2} ∈ ⟨z_{1}⟩, gcd(z_{2}, 2) = 1, and z_{2} ∤ 2z_{1}; • z_{3} ∈ ⟨2z_{1}, z_{2}⟩, gcd(z_{3}, 3) = 1, and z_{3} ∤ 6z_{1}, 3z_{2};

• z_{4} ∈ ⟨6z_{1}, 3z_{2}, z_{3}⟩, gcd(z_{4}, 4) = 1, and z_{4} ∤ 24z_{1}, 12z_{2}, 4z_{3};

• z_{5} ∈ ⟨24z_{1}, 12z_{2}, 4z_{3}, z_{4}⟩, gcd(z_{5}, 5) = 1, and z_{5} ∤ 120z_{1}, 60z_{2}, 20z_{3}, 5z_{4}.

Any such z_{2}, …, z_{5} satisfying the above will produce the desired result, and conversely every such numerical semigroup S can be constructed in this way.

For a concrete example, we can take z_{2} = 3, z_{3} = 5, z_{4} = 11, and z_{5} = 22. For g_{i} = z_{i}C_{i,5}, we get G = (120, 180, 100, 55, 22). We check that gcd(G) = 1, G is minimal, and G is telescopic with c(G) = (2, 3, 4, 5), as desired.

Corollary 58. Suppose G = (g_{1}, …, g_{k}) ∈ ℕ^{k} is a telescopic and non-decreasing sequence with c(G) = (c_{2}, …, c_{k}) where c_{j} > 1 for all j. Then G is minimal.

In particular, if gcd(G) = 1, then for the numerical semigroup S = ⟨G⟩, we have e(S) = |G|.

Proof. If g_{j} = g_{j−1} for some j > 1, then c_{j} = 1. Since we assume c_{j} > 1 for all j, we must have g_{j} ≠ g_{j+1}, so G is a strictly increasing sequence. In other words, g_{n} < g_{m} whenever n < m.

Since G is telescopic and c_{j} > 1 for all j, G is minimal if and only if g_{m} ∤ g_{n} for all 1 ≤ n < m ≤ k. Since g_{m} > g_{n} > 0, we have g_{m} ∤ g_{n}. Therefore G is minimal.

7 Acknowledgments

The author wishes to thank the anonymous referee for substantially helping to improve the presentation of this paper in many ways. Of particular note is the suggestion to write Lemma 16, which simplified a few subsequent proofs.

References

[1] R. Apéry, Sur les branches superlinéaires des courbes algébriques, C. R. Acad. Sci. Paris 222 (1946), 1198–1200.

[2] T. Ayano, Sigma functions for telescopic curves, Osaka J. Math. 51 (2014), 459–480.

[3] J. Bertin and P. Carbonne, Semi-groupes d’entiers et application aux branches, J. Algebra 49 (1977), 81–95.

[4] A. Brauer, On a problem of partitions, Amer. J. Math. 64 (1942), 299–312.

[5] A. Brauer and J. E. Shockley, On a problem of Frobenius, J. Reine Angew. Math. 211 (1962), 215–220.

[6] F. Curtis, On formulas for the Frobenius number of a numerical semigroup, Mathematica Scandinavica 67 (1990), 190–192.

[7] R. Fröberg, C. Gottlieb, and R. Häggkvist, On numerical semigroups, Semigroup Forum 35 (1987), 63–84.

[8] T. A. Gassert and C. M. Shor, On Sylvester sums of compound sequence semigroup complements, J. Number Theory 180 (2017), 45–72.

[9] T. A. Gassert and C. M. Shor, Characterizations of numerical semigroup complements via Apéry sets, Semigroup Forum (2018).

[10] J. Herzog, Generators and relations of abelian semigroups and semigroup rings, Manuscripta Math. 3 (1970), 175–193.

[11] C. Kiers, C. O’Neill, and V. Ponomarenko, Numerical semigroups on compound sequences, Comm. Algebra 44 (2016), 3842–3852.

[12] C. Kirfel and R. Pellikaan, The minimum distance of codes in an array coming from telescopic semigroups, IEEE Trans. Inform. Theory 41 (1995), 1720–1732.

[13] E. Leher, Applications of the minimal transversal method in numerical semigroups, PhD thesis, Tel Aviv University, 2007.

[14] J. L. Ramírez Alfonsín, Complexity of the Frobenius problem, Combinatorica 16 (1996), 143–147.

[15] J. L. Ramírez Alfonsín, The Diophantine Frobenius problem, Vol. 30 of Oxford Lecture Series in Mathematics and its Applications, Oxford University Press, Oxford, 2005.

[16] A. M. Robles-Pérez and J. C. Rosales, The Frobenius number for sequences of triangular and tetrahedral numbers, J. Number Theory 186 (2018), 473–492.

[17] Ö. J. Rödseth, On a linear Diophantine problem of Frobenius, J. Reine Angew. Math. 301 (1978), 171–178.

[18] J. C. Rosales and P. A. García-Sánchez, On free affine semigroups, Semigroup Forum 58 (1999), 367–385.

[19] J. C. Rosales and P. A. García-Sánchez, Numerical Semigroups, Vol. 20 of Developments in Mathematics, Springer-Verlag New York, 2009.

[20] E. S. Selmer, On the linear diophantine problem of Frobenius, J. Reine Angew. Math. 293/294 (1977), 1–17.

[21] H. J. H. Tuenter, The Frobenius problem, sums of powers of integers, and recurrences for the Bernoulli numbers, J. Number Theory 117 (2006), 376–386.

[22] K. Watanabe, Some examples of one dimensional Gorenstein domains, Nagoya Math. J. 49 (1973), 101–109.

2010 Mathematics Subject Classification: Primary 20M14; Secondary 11B75. Keywords: telescopic sequence, free numerical semigroup, minimal generating sequence, additive submonoid.

Received June 27 2018; revised versions received January 2 2019; January 6 2019. Published in Journal of Integer Sequences, February 23 2019.

Return to Journal of Integer Sequences home page.