Directed Graphs from Exact Covering Systems

Dana Neidmann^{1} Department of Mathematics University of Illinois at Urbana-Champaign Urbana, IL 61801 USA

                   dn2@illinois.edu

Abstract

Given an exact covering system S = {a_{i} (mod d_{i}) : 1 ≤ i ≤ r}, we introduce the corresponding exact covering system digraph (ECSD) G_{S} = G(d_{1}n + a_{1}, …, d_{r}n + a_{r}). The vertices of G_{S} are the integers and the edges are (n, d_{i}n + a_{i}) for each n ∈ ℤ and for each congruence in the covering system. We study the structure of these directed graphs, which have finitely many components, one cycle per component, as well as indegree 1 and outdegree r at each vertex. We also explore the link between ECSDs that have a single component and non-standard digital representations of integers.

1 Introduction

In this paper, we take inspiration from the fundamental concept of covering systems to create an associated family of directed graphs on the integers.

Definition 1. For integers a_{i}, d_{i}, and r, a system of congruences

{x ≡ a_{i} (mod d_{i}) : 1 ≤ i ≤ r}

is called a covering system if every integer n satisfies n ≡ a_{i} (mod d_{i}) for at least one value of i; equivalently, we say n is covered by the congruence x ≡ a_{i} (mod d_{i}). A covering system in which each integer is covered by exactly one congruence is called an exact covering system.

1This work was supported in part by the University of Illinois Urbana-Champaign Research Board Award [RB19143].

As congruences denote equivalence classes, choosing an equivalent representative a_{i} does not change the congruence. For example, x ≡ 1 (mod 2) and x ≡ 3 (mod 2) denote the same equivalence class. However, for our purposes in this paper, we do care about the choice of representative.

Similarly, although number theorists customarily think about congruences modulo positive numbers only, it will make sense for us to consider negative moduli as well: we say that an integer n is congruent to a (mod −d) if and only if n ≡ a (mod d). This is because d | n − a if and only if −d | n − a. Thus we can think of −d as another representative of the modulus d, so the congruences x ≡ 1 (mod 2) and x ≡ 1 (mod −2) denote the same equivalence class. However, for our purposes we will also care about the sign of the modulus.

To clarify these choices, for a given exact covering system we can introduce a representative set denoting the specific choice of representatives.

Definition 2. The set of pairs S = {(a_{i}, d_{i}) ∈ ℤ^{2} : 1 ≤ i ≤ r} is a representative set for an exact covering system if the system of congruences {x ≡ a_{i} (mod d_{i}) : 1 ≤ i ≤ r} is an exact covering system.

For each representative set, we introduce a corresponding (infinite) directed graph on the set of integers (note that the definition can be extended to any covering system).

Definition 3. Let S = {(a_{i}, d_{i}) ∈ ℤ^{2} : 1 ≤ i ≤ r} be a representative set for an exact covering system. We denote the corresponding exact covering system digraph (ECSD)

G_{S} = G(d_{1}n + a_{1}, …, d_{r}n + a_{r}) := (V, E),

where V (G_{S}) = ℤ, and E(G_{S}) = {(n, d_{i}n + a_{i}) : 1 ≤ i ≤ r}. Note that the parameters of G_{S} are the r integers to which each n ∈ ℤ is sent. Let r be called the degree of G_{S} (this is the outdegree of every vertex).

In Figure 1, we see the ECSD corresponding to the representative set S = {(0, 2), (−9, 2)}. We refer to this ECSD as G(2n, 2n − 9) because every integer n has a directed edge to 2n as well as to 2n − 9. All components are shown, and dotted lines indicate that the graph continues on infinitely. (Note that in this paper, we use component to refer to a connected component in the underlying undirected graph, more precisely, a weakly connected component of the digraph.) In this figure, we can see that each n ∈ ℤ has indegree 1; in fact, this is true for each vertex in any ECSD since each integer satisfies exactly one congruence:

Observation 4. Each vertex of an ECSD has indegree 1.

Proof. Given an ECSD G_{S}, each n ∈ ℤ is in exactly one congruence class of the exact covering system corresponding to S; say, for example, that we have n ≡ a_{i} (mod d_{i}). Therefore, there is a unique m such that d_{i}m + a_{i} = n, and a single edge (m, n) ending in n.

Since every vertex has indegree 1, we can define several more terms:

09−9 18 ⋮⋮⋮⋮12487536−7 −5 −1 16 14 10 −3 12 ⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮

Figure 1: The ECSD G(2n, 2n − 9).

Definition 5. In an ECSD, let the predecessor of n be the unique P (n) ∈ ℤ such that (P (n), n) is an edge. Let P^{k}(n) = P (P (⋯ P (n) ⋯)), where the predecessor function is composed k times. If m = P^{k}(n) for some k ∈ ℕ, we call m a (k-)ancestor of n, and call n a (k-)descendant of m. We call a 1-descendant of n a successor of n.

For example, in Figure 1 we can see that the predecessor of −5 is 2, two visible 2descendants of 8 are 5 and 14, and 7 is an ancestor of −1.

ECSDs have several interesting applications within number theory. The example that inspired the definition of ECSDs comes from the Stern sequence s(n), defined recursively by

s(0) = 0, s(1) = 1, s(2n) = s(n), s(2n + 1) = s(n) + s(n + 1)

(\underline{A002487} in the On-Line Encyclopedia of Integer Sequences (OEIS) [10]). The set of nonnegative integers n with the property s(n) ≡ 0 (mod 3) is precisely the set of non-negative integers in the component of G(2n, 8n + 5, 8n − 5, 8n + 7, 8n − 7) containing 0 [12]. Some structural results about ECSDs also imply results about non-standard digital representations of integers, as we will see in Section 4.

Previous results about similar directed graphs have been explored by Tangjai, who in her 2014 Ph.D. thesis from the University of Illinois at Urbana-Champaign [14] studied primarily G(3n, 3n + 1, 3n + 5) on the non-negative integers. She focused on finding properties of the subset of ℕ_{0} that were members of the component containing 0, looking at the asymptotic density and blocks of consecutive integers contained in this subset. She considered directed graphs only on the non-negative integers, which do not have the same general structure as when they are considered on all the integers.

Questions of the density of components of ECSDs in the integers nonetheless provide an interesting further area of study. Some ECSDs clearly have stable asymptotic density; for example, each component of the ECSD G(dn, dn+1, …, dn+d−1) has asymptotic density \frac{1}{2} because one component contains all the positive integers and the other component contains all the negative integers. However, for d ≥ 4, the asymptotic density of the component containing 0 in the ECSD G(dn, dn + 2, dn + 3, …, dn + d − 1, dn + d + 1) does not exist.

In Section 2, we discuss the structure of ECSDs of degree 1, as they behave very differently from ECSDs of higher degree. In Section 3, we prove several theorems that hold for all ECSDs of degree at least 2. In particular, we prove that the number of components in such an ECSD must be finite, and every component must contain exactly one cycle. We also find graph isomorphisms between different ECSDs.

In Section 4, we connect structural results about ECSDs with non-standard representations of integers. Recall standard base d, or d-ary, representations of natural numbers: every natural number can be written as a sum

∑_{j=0}^{k} b_{j}d^{j} with b_{j} ∈ {a_{1}, …, a_{d}}

for some k ∈ ℕ if {a_{1}, …, a_{d}} = {0, …, d − 1}. Generalizing this concept to non-standard representations, we choose non-standard representatives of each congruence class modulo d for {a_{1}, …, a_{d}}. We show that every integer can be written uniquely as the above sum if and only if the ECSD G(dn + a_{1}, …, dn + a_{d}) has a single component and 0 is an element of the cycle.

2 ECSDs of degree 1

First we completely characterize ECSDs of degree 1, and we shall see that they behave quite differently from ECSDs of higher degree. Since the only exact covering system with a single congruence is {0 (mod 1)}, the only possible representative sets are

S = {(a, 1)} or S = {(a, −1)}.

Thus every ECSD of degree 1 is of the form G(n + a) or G(−n + a) for some a ∈ ℤ. The graphs of the form G(n+a) with a ≠ 0 are the only ECSDs where each component is acyclic, and G(n) and G(−n + a) are the only ECSDs with infinitely many components; we shall prove both claims in Section 3.

Proposition 6. The graph G(n + a), with a ≠ 0, is the disjoint union of |a| infinite paths. When a = 0, the graph is the disjoint union of infinitely many loops, one at each integer.

Proof. Clearly G(n) is the disjoint union of infinitely many loops, because each n ∈ ℤ is sent to itself (shown in Figure 2).

The graph G(n + a) sends n ∈ ℤ to n + a, so the component containing n is an infinite path where every element of the path is congruent to n (mod a). Thus, there are |a| disjoint infinite paths P_{i} = {i + ka : k ∈ ℤ} for 0 ≤ i < |a|. One path is shown in Figure 3.

\begin{matrix}1 \\ 2 \\ 0 \\ −1 \\ −2 \\ −3 \\ 3 \\ ⋯ \\ ⋯ \end{matrix}

Figure 2: The ECSD G(n).

\begin{matrix}a \\ 0 \\ −a \\ 2a \\ ⋯ \\ ⋯ \\ ⋯ \\ ⋯ \\ ⋯ \end{matrix}

Figure 3: The ECSD G(n + a).

Proposition 7. The graph G(−n+a) is a disjoint union of infinitely many 2-cycles covering ℤ, with one exception being that, if a is even, the graph has a loop at \frac{1}{2}a. If a is odd, there is no such loop. Thus there are exactly two isomorphism classes of ECSDs of this type.

Proof. Since n ∈ ℤ is sent to −n + a, and −n + a is sent to −(−n + a) + a = n, there are infinitely many disjoint 2-cycles. If a is even, then n = −n + a for n = \frac{a}{2}. Thus, if a is even there is a loop at \frac{a}{2}, and if a is odd there is no such loop (see Figure 4).

\frac{a}{2}−k + a · · · · · · k · · · · · · \frac{a}{2} + 1 \frac{a}{2} − 1

−k + a k ⌊\frac{a}{2}⌋ ⌈\frac{a}{2}⌉ · · · · · · · · · · · ·

Figure 4: The ECSDs G(−n + a) with a even above and a odd below.

In this simple case where the degree is 1, we can already see that the signs of the d_{i} (in this case, determining ±n) matter significantly to the structure of an ECSD. This will continue to hold for ECSDs of greater degree.

3 Basic theorems about ECSDs

For an ECSD of degree r ≥ 2, we will prove that each of finitely many components has exactly one cycle, and that each vertex of a cycle is the root of a tree with r − 1 successors, each of which is the root of an infinite r-ary tree. In order to do so, we first require a lemma.

Lemma 8. Given an ECSD, for each n ∈ ℤ, there is an ancestor m of n such that |P (m)| ≥ |m|. Moreover, for each ECSD of degree at least 2 there exists some N ∈ ℕ such that if m ∈ ℤ and |P (m)| ≥ |m|, then |m| ≤ N.

Proof. Suppose n ∈ ℤ has no such ancestor. Then |P^{k+1}(n)| < |P^{k}(n)| < ⋯ < |n| for each k ∈ ℕ. But there are only finitely many nonnegative numbers less than |n|, contradicting the assumption.

Let m ∈ ℤ be such an ancestor. Suppose the edge (P (m), m) comes from the pair (a_{i}, d_{i}), i.e., when m = P (m)d_{i}+a_{i} (recall that d_{i} may be negative). We therefore have the inequality |\frac{m−a_{i}}{d_{i}} | ≥ |m|, which simplifies to 0 ≥ ((d_{i} − 1)m + a_{i})((d_{i} + 1)m − a_{i}). This ensures that m must be between −\frac{a_{i}}{d_{i}−1} and \frac{a_{i}}{d_{i}+1} (when d_{i} ≠ ±1, which is true assuming r ≥ 2).

Let N_{i} = max \{|−\frac{a_{i}}{d_{i}−1} | , |\frac{a_{i}}{d_{i}+1} |\}. Then |m| ≤ N_{i}. Now let N = max_{i} N_{i}, so for any m ∈ ℤ such that |P (m)| ≥ |m|, we have |m| ≤ N.

From this lemma, we can conclude that the number of components of an ECSD of degree at least 2 must be finite: if each n ∈ ℤ has an ancestor in {m ∈ ℤ : |m| ≤ N}, the number of components is at most 2N + 1. Note that this is a rather poor upper bound. Although it is simple to determine the number of components for a given ECSD computationally, the number of components of a general ECSD seems to often be irregular. In future work [9] we find all ECSDs of degree 2 with a single component, but the ECSD G(3n, 3n + 1, 3n − a) has a single component whenever a is in the sequence \underline{A110081} in the On-Line Encyclopedia of Integer Sequences (OEIS) [10], which is infinite, irregular, and has density zero. In section 4 we will show why single-component ECSDs are of special interest.

Instead, we will use this lemma to prove that each component has exactly one cycle:

Theorem 9. Each component of an ECSD of degree at least 2 has exactly one cycle.

Proof. Let n ∈ ℤ. By Lemma 8, n has some ancestor m_{1} such that |P (m_{1})| ≥ |m_{1}|. Similarly, m_{1} has such an ancestor m_{2}. Thus, we can construct an infinite sequence of ancestors m_{1}, m_{2}, …, m_{k}, … of n such that |m_{k}| ≤ N for each k ∈ ℕ. Thus, this sequence contains repetitions, and n is the descendant of some cycle.

Since every vertex has indegree 1, every edge adjacent to a cycle must be oriented away from the cycle. Also, every walk that intersects a cycle is oriented away from this cycle, and cannot intersect itself, or else would violate the indegree 1 condition. Thus, there is at most one cycle per component.

We begin to see that the cycles of ECSDs are essential to their overall structure, and indeed, proving results about the cycles of ECSDs is the main goal of our future efforts. To this end, we shall study the integers in cycles of an ECSD, which we will call cyclic vertices. We will use the notation C = (c_{1}, c_{2}, …, c_{k}) to denote a cycle of length k in an ECSD, where P (c_{i+1}) = c_{i} for each i, and P (c_{1}) = c_{k}.

Observation 10. If a vertex n is an ancestor of a cyclic vertex, then n is also a cyclic vertex.

Proof. All edges adjacent to a cycle must be oriented away from the cycle, and thus any ancestor of a cyclic vertex must also be on the cycle.

One way we can study the structure of ECSDs is by using graph isomorphisms to conclude that many different ECSDs must all have the same structure. In fact, two ECSDs of the same degree are isomorphic if they have the same number of components, and the same number of cyclic vertices in each corresponding component. Thus, the structure of an ECSD up to graph isomorphism can be represented by its degree along with a weakly increasing list of numbers of cyclic vertices in each component. For example, the ECSD in Figure 1 could be represented by the list [2; 1, 1, 2, 6].

There are two main types of isomorphisms of covering system digraphs, both of which are automorphisms of the integers. Specifically, the isomorphisms of covering system digraphs are automorphisms of ℤ that respect ℤ as a graph, that is, the images of neighbors n + 1 and n − 1 of n ∈ ℤ under the automorphism are still neighbors of the image of n. The first type of ECSD isomorphism results from a shift on the integers:

Proposition 11. For each k ∈ ℤ and representative sets of exact covering systems

S = {(a_{i}, d_{i}) ∈ ℤ^{2} : 1 ≤ i ≤ r},
S′ = {(a_{i} − (d_{i} − 1)k, d_{i}) ∈ ℤ^{2} : 1 ≤ i ≤ r},

the map ϕ_{1,k} : ℤ → ℤ defined by ϕ_{1,k}(n) = n + k is a graph isomorphism between G_{S} and G_{S′}.

Proof. By definition, ϕ_{1,k} maps V (G_{S}) to V (G_{S′}): for each edge (n, d_{i}n + a_{i}) ∈ E(G_{S}), we have the edge (ϕ_{1,k}(n), ϕ_{1,k}(d_{i}n + a_{i})) = (n + k, d_{i}n + a_{i} + k) ∈ E(G_{S′}). If we let m = n + k and n = m − k, this edge is (m, d_{i}m + a_{i} − (d_{i} − 1)k) ∈ E(G_{S′}).

The second type of ECSD isomorphism results from a shift and flip on the integers:

Proposition 12. For each k ∈ ℤ and representative sets of exact covering systems

S = {(a_{i}, d_{i}) ∈ ℤ^{2} : 1 ≤ i ≤ r},
S′ = {(−a_{i} + (d_{i} − 1)k, d_{i}) ∈ ℤ^{2} : 1 ≤ i ≤ r},

the map ϕ_{2,k} : ℤ → ℤ defined by ϕ_{2,k}(n) = −(n + k) is a graph isomorphism between G_{S} and G_{S′}.

Proof. By definition, ϕ_{2,k} maps V (G_{S}) to V (G_{S′}): for each edge (n, d_{i}n + a_{i}) ∈ E(G_{S}), we have the edge (ϕ_{2,k}(n), ϕ_{2,k}(d_{i}n + a_{i})) = (−(n + k), −(d_{i}n + a_{i} + k)) ∈ E(G_{S′}). If we let m = −(n + k) and n = −m − k, this edge is (m, d_{i}m − a_{i} + (d_{i} − 1)k) ∈ E(G_{S′}).

Note that in both of the above propositions, S is an exact covering system if and only if S′ is also an exact covering system: for example, in Proposition 11, if all n ∈ ℤ are covered exactly once by S then all n + k ∈ ℤ are covered exactly once by S′.

In forthcoming work [9], we shall use these isomorphisms to classify all ECSDs of degree 2. We split the degree 2 ECSDs into three types based on the signs of their d_{i}: G(2n+a_{1}, 2n+a_{2}), G(−2n + a_{1}, 2n + a_{2}), and G(−2n + a_{1}, −2n + a_{2}). We then use these isomorphisms to simplify each type and determine the vertices contained in cycles for each. For now, we turn our attention to single-component ECSDs.

4 Single-component ECSDs and non-standard digital representations

In an ECSD, if d_{1} = d_{2} = ⋯ = d_{r}, then its structure is closely linked to digital representations.

Consider an ECSD G_{S} with representative set S = {(a_{i}, d) ∈ ℤ^{2} : 1 ≤ i ≤ d}, where d is a positive integer. There are d pairs, each representing a different congruence class modulo d. Then the set

{∑_{j=0}^{k} b_{j}d^{j} : b_{j} ∈ {a_{1}, …, a_{d}}}  (1)

is the set of all (k + 1)-descendants of 0 in G_{S}: each coefficient b_{j} is a representative a_{i} determined by the choice of each corresponding branch in the path from 0 to the descendant.

This is more clearly illustrated in Figure 5, which shows the 1, 2, and 3-descendants of 0 in the ECSD G(2n + a_{1}, 2n + a_{2}). Here, the representatives of the two binary congruence classes are a_{1} and a_{2}. For example, if we travel from 0 through an edge (n, 2n + a_{1}), then two edges (n, 2n + a_{2}), we arrive at the 3-descendant

2(2(2(0) + a_{1}) + a_{2}) + a_{2} = 2^{2}a_{1} + 2^{1}a_{2} + 2^{0}a_{2} = 4a_{1} + 2a_{2} + a_{2}.

If we choose a_{1} = 0 and a_{2} = 1, this representation becomes the standard binary representation. The corresponding ECSD G(2n, 2n + 1) is shown in Figure 6, with (n, 2n) edges colored red and (n, 2n + 1) edges colored blue. In this case, there are two loops and two components. Here, we can see that the number 6 can be reached via two blue steps then a red step from 0. The standard binary representation of 6 is 2^{2} · 1 + 2^{1} · 1 + 2^{0} · 0, written as “110” in digital form.

Thus, one can see that the component of G_{S} containing 0, assuming that 0 is a cyclic vertex, is the set of integers which for some k ∈ ℕ can be expressed as the sum in Equation 1 (as every vertex m in the component containing 0 will have a walk from 0 to m). For the

0 a_{1} a_{2} 2a_{1} + a_{1} 2a_{1} + a_{2} 2a_{2} + a_{1} 2a_{2} + a_{2} 4a_{1} + 2a_{1} + a_{1} 4a_{1} + 2a_{1} + a_{2} 4a_{1} + 2a_{2} + a_{1} 4a_{1} + 2a_{2} + a_{2} 4a_{2} + 2a_{1} + a_{1} 4a_{2} + 2a_{1} + a_{2} 4a_{2} + 2a_{2} + a_{1} 4a_{2} + 2a_{2} + a_{2}

Figure 5: The 1, 2, and 3-descendants of 0 in G(2n + a_{1}, 2n + a_{2}), with vertices possibly non-unique because of cycles.

01234567⋮⋮⋮⋮⋮⋮⋮⋮−1 −2 −3 −4 −5 −6 −7 −8 ⋮⋮⋮⋮⋮⋮⋮⋮

Figure 6: The ECSD G(2n, 2n + 1) with (n, 2n) edges colored red and (n, 2n + 1) edges colored blue.

standard binary representation, we can see from Figure 6 that every non-negative integer has such a representation. The same is true for any standard d-ary representation (i.e., with representatives 0, 1, …, d − 1).

Through non-standard choices of representatives, we are able to create different nonstandard representations. Moreover, we have not restricted ourselves to positive moduli, so we may also consider ECSDs with modulus representative −d for some integer d > 0, i.e., the ECSD G_{S′} with S′ = {(a_{i}, −d) ∈ ℤ^{2} : 1 ≤ i ≤ d}. In this case, the (k + 1)-descendants of 0 in G_{S′} are

{∑_{j=0}^{k} b_{j}(−d)^{j} : b_{j} ∈ {a_{1}, …, a_{d}}} .  (2)

Although perhaps not immediately familiar, this leads to interesting digital representations. For base −2, for example, we have coefficients not of powers of 2, but of powers of −2: 1, −2, 4, −8, etc. While we can represent every non-negative integer with a standard d-ary representation, we cannot represent any of the negative integers. Using non-standard representations, we can. It is the case that representations which can represent every integer are given by one-component ECSDs:

Theorem 13. Let G_{S} be an ECSD with representative set S = {(a_{i}, D) ∈ ℤ^{2} : 1 ≤ i ≤ d}, the base D = ±d, and d ≥ 2 ∈ ℤ. Then every integer n can be expressed as the sum

∑_{j=0}^{k} b_{j}D^{j} : b_{j} ∈ {a_{1}, …, a_{d}}  (3)

for some k ∈ ℕ if and only if G_{S} is connected and its single cycle contains 0. This representation is unique up to leading instances of the block of digits representing the path from 0 to itself in G_{S}.

Proof. As in the previous discussion, the set of descendants of 0 in G_{S} is the set of n ∈ ℤ that can be expressed as (3) for some k ∈ ℕ. Thus, if there is only one cycle (and therefore only one component by Proposition 9) and 0 is a cyclic vertex, every integer must be a descendant of 0 and can be expressed as (3) for some k ∈ ℕ. If G_{S} has more than one component or if 0 is not a cyclic vertex, then some integers are not descendants of 0 and hence do not have such a representation.

Because the structure of each component of an ECSD is a single base cycle and infinite trees at each cyclic vertex, a walk from 0 to n ∈ ℤ will become unique once the path leaves the cycle. Since representations correspond to walks from 0 to n, the only difference may be an arbitrary number of walks around the cycle which correspond to leading digits.

We are used to digital representations being unique up to leading 0 digits; for example, in the standard binary representation, we would say “00011” = “11”. If 0 is the only cyclic vertex of an ECSD, then the cycle is a loop at 0, so the path from 0 to itself is one edge with corresponding digit 0. Thus, in this case we ignore leading zeroes as usual.

However, consider a more complicated case, such as G(−2n+1, −2n+4) (shown in Figure 7 with (n, −2n + 1) edges colored blue and (n, −2n + 4) edges colored red). One can reach -3 by a blue step, a red step, and a blue step from 0, so the shortest representation of −3 would be “141”, as 1(−2)^{2} +4(−2)^{1} +1(−2)^{0} = −3. However, we can also reach −3 by going once around the cycle first, giving us a different representation of “144141”, as

1(−2)^{5} + 4(−2)^{4} + 4(−2)^{3} + 1(−2)^{2} + 4(−2)^{1} + 1(−2)^{0} = −3.

Each time we go around the cycle at the beginning, we add an extra “144” to the beginning of the representation. This is because the shortest representation of 0 in this digital system is “144”, since 0 is not a digit: we have that 1(−2)^{2}+4(−2)^{1}+4(−2)^{0} = 0. Thus, by ignoring leading appearances of “144”, we are really ignoring leading zeroes.

The idea of non-standard representations is certainly not new, though this specific way of studying them seems to be.

1204−1 −3 −7 −4 36710 ⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮

Figure 7: The ECSD G(−2n+1, −2n+4) with (n, −2n+1) edges colored blue and (n, −2n+4) edges colored red.

Arithmetic in negative bases was first proposed by Grünwald in 1885 [5], though his work seemed to be forgotten for a time. With the advent of digital computing in the mid 20th century, interest in negative bases exploded, especially in regards to base −2 which became known as “negabinary” (term first introduced by deRegt [4]). Numerous papers have been published on the subject, but are all about the computer science and efficiency of such number systems [11]. Such a system was more efficient, because instead of needing a bit to represent whether a number was negative or positive, every integer could be represented in such a manner, and its sign depended on the number of digits. It is important to note that all of these publications assumed a standard digit set.

The most commonly explored type of alternate digit set is a symmetric digit set, in which for an odd base d, the digits are taken to be −\frac{r−1}{2}, …, \frac{r−1}{2}. Such systems seem to be as old as civilization itself, for example, one can see similarities with the number system of the Yoruba people of West Africa [15]. In such a system, one counts down from a larger place value as well as up.

As well as using an odd base and taking digits centered about 0, in fact, one can use any integer base d ≥ 3 and any set of consecutive d − 1 digits including −1, 0, and 1, and get a system in which one can represent all integers, not just all natural numbers. The first modern study of such systems is Colson in 1726 [3], who studied “negativo-affirmative arithmetick,” a base 10 system using the digits {−4, −3, …, 4, 5}. In his book The Philosophy of Arithmetic, Leslie includes such an idea, suggesting the same digits as Colson, though acknowledging there could be other choices of digit set. [8]. Cauchy suggested the extension to an arbitrary base in 1840 [2], and Lalanne provided a follow-up discussion in the same year [7]. A century later, in 1950, Shannon published an informative summary in the American Mathematical Monthly [13]. In most of these publications, emphasis was put on the ease of calculating with such a number system — it effectively gets rid of larger digits, and the same computations can be used for multiple calculations.

One system in particular that holds great interest for computer scientists is balanced ternary, which Knuth termed “perhaps the prettiest number system of all:” a number system in base 3 with digit set {−1, 0, 1} [6]. Of course, this is just a special case of a symmetric digit set. In the following proposition we use ECSDs to prove that every integer can be expressed in balanced ternary:

Proposition 14. Every integer can be written uniquely as ∑_{i=0}^{k} ϵ_{i}3^{i} for ϵ_{i} ∈ {0, ±1}, where

ϵ_{k} ≠ 0.

Proof. It suffices to show that 0 is the only cyclic vertex of G(3n, 3n − 1, 3n + 1), from which Theorem 13 completes the proof. The ECSD G(3n, 3n − 1, 3n + 1) is shown in Figure 8.

Each cyclic vertex m must have itself as a k-descendant for some k ∈ ℕ. However, if m > 0, its three successors 3m, 3m + 1, and 3m − 1 are all greater than m, so none of its descendants will be m. Similarly, if m < 0, all of its descendants are less than m. Thus, 0 is the only cyclic vertex of G(3n, 3n − 1, 3n + 1). By Theorem 13, each representation is unique up to leading zeroes.

\begin{matrix}0 \\ 1 \\ -1 \\ 2 \\ 3 \\ 4 \\ -2 \\ -3 \\ -4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12 \\ 13 \\ -5 \\ -6 \\ -7 \\ -8 \\ -9 \\ -10 \\ -11 \\ -12 \\ -13 \\ ⋯ \\ ⋯ \end{matrix}

Figure 8: The ECSD G(3n, 3n + 1, 3n − 1).

We can extend this proof to the general case for a consecutive digit set including digits −1, 0, and 1 for base d ≥ 3:

Proposition 15 ([3]). Let d ≥ 3. If −(d − 1) < t < 0, then every integer can be written uniquely as

∑_{i=0}^{k} b_{i}d^{i} for b_{i} ∈ {t, t + 1, …, 0 …, t + d − 1} where b_{k} ≠ 0.

Proof. It suffices to show that 0 is the only cyclic vertex of

G(dn + t, dn + (t + 1), …, dn, …, dn + t + d − 1),

from which Theorem 13 completes the proof. We can see that 0 is a loop in this ECSD because dm = m if and only if m = 0. If m ≥ 1, all of its successors are greater than m, because the smallest successor is dm + t > dm − (d − 1) ≥ m, so it cannot be a descendant of itself. If m ≤ −1, all of its successors are smaller than m, because the largest successor is dm + t + d − 1 < dm + d − 1 ≤ m, so it cannot be a descendant of itself. Therefore 0 is the only cyclic vertex.

Remark 16. In the previous proposition, if t = 0, we get the standard d-ary representation, that is, every non-negative integer can be expressed uniquely as

∑_{i=0}^{k} b_{i}d^{i} for b_{i} ∈ {0, 1, 2, …, d − 1}.

If t = −(d − 1), we get the standard representation but multiplied by −1, that is, we can represent every non-positive integer as ∑_{i=0}^{k} b_{i}d^{i} for b_{i} ∈ {0, −1, −2, …, −(d − 1)}. Both of these can be proved in a similar manner to the proof of Theorem 15 using ECSDs: each corresponding ECSD has two components, and the component with 0 as the sole cyclic vertex contains all the non-negative integers in the standard case and all the non-positive integers in the second case.

Notably, this digital representation does not work for d = 2, because there is no valid integer choice of t between −(d − 1) = −1 and 0. However, we can represent every integer in base “2” using the negabinary representation, as follows:

Proposition 17 ([5]). Every integer can be written uniquely as ∑_{i=0}^{∞} b_{i}(−2)^{i} for b_{i} ∈ {0, 1}.

The ECSD G(−2n, −2n + 1) has a single component and 0 is its only cyclic vertex. It is shown in Figure 9, where we can see that the rows alternate between all negative and all positive values: the direct k-descendants of 0 are positive for odd k and negative for even k.

We can see that the structure of this ECSD will hold for a generalization into ECSDs of higher degree, giving us the same result for negative-base digital representations of degree d. For example, the ECSD G(−3n, −3n + 1, −3n + 2) will have the same general structure, containing every integer and alternating between positive and negative rows, shown in Figure 10. Thus, we can prove the following:

01−1 −2 2345−3 −4 −5 −6 −7 −8 −9 −10 ⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮

Figure 9: The ECSD G(−2n, −2n + 1).

0⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮12−1 −2 −3 −4 −5 −6 345678910 11 12 13 14 15 16 17 18 19 20 ⋮⋮⋮

Figure 10: The ECSD G(−3n, −3n + 1, −3n + 2).

Proposition 18 ([5]). For any natural number d ≥ 2, every integer can be written uniquely

as ∑_{i=0}^{∞} b_{i}(−d)^{i} for b_{i} ∈ {0, 1, …, d − 1}.

Proof. It again suffices to show that 0 is the only cyclic vertex of

G(−dn, −dn + 1, …, −dn + d − 1).

Suppose m > 0. Then its successors are negative and its 2-descendants are positive. Its largest successor is −dm + d − 1, so its smallest 2-descendant is

−d(−dm + d − 1) = d^{2}(m − 1) + d > m

since d ≥ 2 and m > 0. It follows that all of the positive descendants of m are greater than m, thus m is not a cyclic vertex.

Suppose m < 0. Then its successors are positive and its 2-descendants are negative. Its smallest successor is −dm, so its largest 2-descendant is −d(−dm)+d−1 = d^{2}m+d−1 < m since d ≥ 2 and m < 0. It follows that all of the negative descendants of m are less than m, and thus that m is not a cyclic vertex.

Since −d(0) = 0, we have that 0 is a cyclic vertex, so m = 0 is the only cyclic vertex.

In later years the topic of numeration systems was extended to consider any base, positive or negative, along with any digit set — however, the digit set is always defined to include the digit 0 [1]. This is because of the leading-zeroes problem, which we have already accounted for in Theorem 13: by ignoring leading appearances of the block of digits corresponding to the base cycle, this is equivalent to ignoring leading zeroes.

1−1 3246−2 5010 812 −5 −7 −3 −11 14 −9 ⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮

Figure 11: The ECSD G(−2n + 1, −2n + 10).

If we expand our definitions to allow digit sets that do not include 0, we can find other non-standard digits sets for a negabinary representation that can represent all integers. This task is equivalent to finding ECSDs of degree 2 with one component. We can show that G(−2n + 1, −2n + 4), depicted in Figure 7, has a single component. We know that every cycle of an ECSD must contain a vertex m such that |P (m)| ≥ |m|, and by Lemma 8, vertices with this property are bounded by some N ∈ ℕ. Thus, it is simply a task of extending the graph until we have all of these vertices to determine the number of components. In the case of G(−2n + 1, −2n + 4), N = 4 by the proof of Lemma 8. Since Figure 7 includes all integers in the range −4 to 4 (except for −2 which is a successor of 3), we can see that this is indeed the only component of this ECSD. By this same process, we can also show that the ECSD G(−2n + 1, −2n + 10) has a single component, as depicted in Figure 11.

Using the classification of all degree 2 ECSDs, we can prove [9] that the only ECSDs of degree 2 to have a single component are either G(2n, −2n+1) or are isomorphic to an ECSD of the form G(−2n + 1, −2n + a) with a = ±3^{m} + 1 for some m ∈ ℕ_{0}. Thus, by Theorem 13 we have that

ℤ = {∑_{j=0}^{k} b_{j}(−2)^{j} : b_{j} ∈ {1, a}, k ∈ ℕ}

if and only if a = ±3^{m} + 1 for some m ∈ ℕ_{0}.

References

[1] J. P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge Univ. Press, 2003.

[2] A. Cauchy, Sur les moyens d’éviter les erreurs dans les calculs numériques, C. R. Acad. Sci. 11 (1840), 789–798.

[3] J. Colson, A short account of negativo-affirmative arithmetick, Philos. Trans. Roy. Soc. 34 (1726), 161–173.

[4] M. P. deRegt, Negative radix arithmetic, Computer Design 6 (1967), 52–63.

[5] V. Grünwald, Intorno all’aritmetica dei sistemi numerici a base negativa con particolare riguardo al sistema numerico a base negativo-decimale per lo studio delle sue analogie coll’aritmetica (decimale). Giornale di matematiche di Battaglini 23 (1885), 203–221.

[6] D. E. Knuth, The Art of Computer Programming. Volume 2: Seminumerical Algorithms, Addison-Wesley, 2nd edition, 1981.

[7] L. Lalanne, Note sur quelques propositions d’arithmologie élémentaire, C. R. Acad. Sci. 11 (1840), 903–905.

[8] J. Leslie, The Philosophy of Arithmetic, A. Constable and Company, 1817.

[9] D. Neidmann, Exact covering system digraphs of degree 2 (in preparation).

[10] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2022, https://

   oeis.org.

[11] Z. Pawlak and A. Wakulicz, Use of expansions with a negative basis in the arithmometer of a digital computer, Bulletin L’Académie Polonaise des Science III 5 (1957), 233-235.

[12] B. Reznick, Regularity properties of the Stern enumeration of the rationals, J. Integer Sequences 11 (2008), Article 08.4.1.

[13] C. E. Shannon, A symmetrical notation for numbers, Amer. Math. Monthly 57 (1970), 90–93.

[14] W. Tangjai, Density and spacing properties of some families of non-standard ternary representations, Ph.D. Dissertation, University of Illinois at Urbana-Champaign, 2014.

[15] C. Zaslavsky, Mathematics of the Yoruba people and of their neighbors in southern Nigeria, The Two-Year College Mathematics Journal 1 (2) (Autumn 1970), 76–99.

AMS 2010 Mathematics Subject Classification: Primary 11A07; Secondary 05C20, 05C63, 11A63, 11A67.

Keywords: exact covering system, infinite directed graph, non-standard digital representation.

(Concerned with sequences \underline{A002487} and \underline{A110081}.)

Received March 2 2021; revised versions received November 3 2021; January 24 2022; January 31 2022. Published in Journal of Integer Sequences, Fevruary 1 2022.

Return to Journal of Integer Sequences home page.