Representation of complex numbers in redundant numeration systems

Positional numeration systems

A positional numeration system is the most common way of representing numbers. It consists of a number $β$ , the base, and a set of numbers $𝒟$ , the digits. Usually the base and digits are positive integers, but the definition can be generalized to any abelian group, with multiplication by a base being replaced with a group endomorphism [optimality-width-w]. However, for the purposes of this project, it will suffice to generalize the notion to complex numbers.

Definition 1.1. A positional numeration system is an ordered pair

(β, 𝒟)

, where

β \in ℂ

and

𝒟 \subset ℂ

is a finite set.

Definition 1.2. Let

(β, 𝒟)

be a positional numeration system and

(x_{n}, \dots, x_{0})

a finite sequence where each

x_{k} \in 𝒟

. Then the number represented by the sequence

(x_{n}, \dots, x_{0})

in base

β

x = {(x_{n} \dots x_{0})}_{β} ≔ \sum_{k = 0}^{n} x_{k} β^{k} .

The sequence

(x_{n}, \dots, x_{0})

is called a

(β, 𝒟)

-representation of

x

x_{0}

is its least significant digit and

x_{n}

is its most significant digit.

Example. Let

β = 4, 𝒟 = {0,1,2,3}

. Then

{(133220)}_{4} = 1 \cdot 4^{5} + 3 \cdot 4^{4} + 3 \cdot 4^{3} + 2 \cdot 4^{2} + 2 \cdot 4^{1} + 0 \cdot 4^{0} = 2024 .

Example. Let

β = φ = \frac{1 + \sqrt{5}}{2}, 𝒟 = {\pm 1}

. Then

{((- 1) 11)}_{φ} = - 1 \cdot φ^{2} + 1 \cdot φ^{1} + 1 \cdot φ^{0} = 0 .

Example. Let

β = i, 𝒟 = {0,1}

. Then

{(11001100110011001100)}_{i} = \sum_{k = 0}^{4} (i^{4 k + 2} + i^{4 k + 3}) = - 5 - 5 i .

Note. A positional representation of a number is not necessarily unique. For example, with

β = 2, 𝒟 = {0,1,2}

{(1000)}_{2} = {(200)}_{2} = {(120)}_{2} = {(112)}_{2} = 8 .

Definition 1.3. A positional representation

(x_{n}, \dots, x_{0})

is called reduced if

x_{n} \neq 0

. As a special case, the empty representation (representing the number

0

) is reduced.

Since adding leading zeros to a representation does not change its value, we will usually consider representations that differ only in leading zeros to be the same, with the reduced representation being their canonical form. In some cases, it is more useful to consider all representations as implicitly having an infinite sequence of zeros to their left.

It is a well-known fact that if $β$ is an integer greater than $1$ and $𝒟 = {0, \dots, β - 1}$ , as in our usual decimal systems, then every non-negative integer has a unique reduced representation. However, the basic concept of the proof is going to be useful later for proving similar facts about more unusual systems.

Definition 1.4. Let

β \in ℤ, β \geq 2, 𝒟 = {0, \dots, β - 1}

. Then

(β, 𝒟)

is the standard positional numeration system with base

β

Theorem 1.5. Let

(β, 𝒟)

be a standard positional numeration system. Then every

x \in ℕ_{0}

has exactly one reduced

(β, 𝒟)

-representation

(x_{n}, \dots, x_{0})

Proof. It follows immediately from Definition 1.2 that if

x = {(x_{n} \dots x_{0})}_{β}

, then

x \equiv x_{0} (m o d β)

. Since every digit from

𝒟

belongs to a different congruence class modulo

β

and all classes are covered, this uniquely determines

x_{0}

. Since

{(x_{n} \dots x_{0})}_{β} = x_{0} + β \cdot {(x_{n} \dots x_{1})}_{β}

(which also follows from the definition),

(x_{n}, \dots, x_{1})

has to be a

(β, 𝒟)

-representation of

\frac{x - x_{0}}{β}

(which is obviously a non-negative integer). Therefore, the same argument can be used to uniquely find the value of

x_{1}

. Since

\frac{x - x_{0}}{β} < x

for all

x \neq 0

, repeating this process will eventually result in trying to find a representation of

0

. Since

0

obviously has exactly one represention that does not start with

0

— the empty string, this gives an algorithm for finding the

(β, 𝒟)

-representation of

x

along with a proof of its uniqueness.

Example. Let us find the base-

17

representation of

2024

(with digits

{0,1, \dots, 16}

). We start by dividing

2024

17

with remainder:

2024 = 119 \cdot 17 + 1

From this, we know that the representation ends in

1

, which is preceded by the representation of

119

. We perform another division:

119 = 7 \cdot 17 + 0

This tells us that the representation of

119

ends in

0

, preceded by the representation of

7

. Since

7 < 17

, its representation is just the single digit

7

; if we were to continue dividing, we would get an infinite sequence of leading zeros. Therefore, the standard base-

17

representation of

2024

{(701)}_{17}

NAF binary representations

Consider the positional numeration system with $β = 2$ and $𝒟 = {0, \pm 1}$ . For the sake of compactness, we will write $- 1$ as $\overline{1}$ when used as a digit (this notation is not to be confused with the notation for complex conjugation). This system can represent any $x \in ℤ$ , including negative integers: simply take the standard binary representation of $| x |$ and multiply all digits by $sgn x$ . In this system, many integers have multiple representations, for example ${(101)}_{2} = {(11 \overline{1})}_{2} = {(10 \overline{1} \overline{1})}_{2} = {(1 \overline{1} 01)}_{2} = 5$ . However, it turns out that if we add a simple restriction to which representations are eligible, reduced representations will once again be unique. [binary-arithmetic]

Definition 1.6. A positional representation

(x_{n}, \dots, x_{0})

is in non-adjacent form (NAF) if there are no two non-zero digits next to each other, that is,

\forall k \in ℕ : x_{k} = 0 \lor x_{k + 1} = 0,

using the convention of representations having infinitely many leading zeros.

Note. If all non-zero digits have an absolute value of

1

(as is the case with

𝒟 = {0, \pm 1}

), Definition 1.6 can be equivalently written in a more compact, but also more obfuscated way:

\forall k \in ℕ : | x_{k} | + | x_{k + 1} | \leq 1 .

Example. Out of the aforementioned representations of

5

{(101)}_{2}, {(11 \overline{1})}_{2}, {(10 \overline{1} \overline{1})}_{2}, {(1 \overline{1} 01)}_{2}

, precisely one is in non-adjacent form, namely

{(101)}_{2}

. It turns out that this is the case for all integers, as shown in the following theorem.

Theorem 1.7. Let

𝒟 = {0, \pm 1}

. Then every

x \in ℤ

has exactly one reduced

(2, 𝒟)

-representation

(x_{n}, \dots, x_{0})

with the NAF property.

Proof. Analogously as in the proof of Theorem 1.5, we need to have

x_{0} \equiv x (m o d 2)

. If

x

is even, this uniquely determines

x_{0}

to be

0

; we can then recursively find a represention of

\frac{x}{2}

. If

x

is odd, we have two options: either choose

x_{0} = 1

and find a representation of

\frac{x - 1}{2}

, or choose

x_{0} = - 1

and find a representation of

\frac{x + 1}{2}

. Either way,

x_{0}

will be a non-zero digit, so in order to fulfill the NAF constraint, we need

x_{1} = 0

, which means that

{(x_{n} \dots x_{1})}_{2}

has to be even. Since exactly one of

\frac{x \pm 1}{2}

is even, we have precisely one choice. Repeating this process, we will eventually reach

0

, since for all non-zero

x

we have

| \frac{x - x_{0}}{2} | < | x |

Example. Let us find the NAF binary representation of

119

. Since

119

is odd, its representation has to end in either

1

\overline{1}

. If we were to choose

1

, we would have to find a representation of

\frac{119 - 1}{2} = 59

and then append the

1

to it. However, since

69

is also odd, the resulting representation would end in two non-zero digits, making it not NAF. So instead, we need to use

\overline{1}

as the last digit and prepend the representation of

\frac{119 + 1}{2} = 60

60

is even, so its representation ends in a zero, exactly as we need. After dividing by

2

, we get the even number

30

, giving us another zero. After that, we have to find a representation of

15

. Again, it is necessary to choose

\overline{1}

because choosing

1

would violate the NAF condition. After a few more divisions by

2

, we get to

1

, which must be represented as

1

because any other of its infinitely many representations is not NAF:

1 = {(1)}_{2} = {(1 \overline{1})}_{2} = {(1 \overline{1} \overline{1})}_{2} = {(1 \overline{1} \overline{1} \overline{1})}_{2} = \dots .

Putting all this together, we obtain the desired NAF representation

119 = {(1000 \overline{1} 00 \overline{1})}_{2} .

The system with $β = 2, 𝒟 = {0, \pm 1}$ also has the useful property that it is possible to tell the sign of a number just from the first non-zero digit of its representation, no matter whether the representation is NAF. We will need this property later, so here is a simple proof.

Theorem 1.8. Let

𝒟 = {0, \pm 1}

and

(x_{n}, \dots, x_{0})

be a reduced

(2, 𝒟)

representation of a non-zero integer

x

. Then

sgn x = sgn x_{n}

Proof. We shall prove the case

x_{n} = 1

, the proof for

x_{n} = - 1

is analogous. From Definition 1.2:

x = \sum_{k = 0}^{n} x_{k} 2^{k} = 2^{n} + \sum_{k = 0}^{n - 1} x_{k} 2^{k} \geq 2^{n} + \sum_{k = 0}^{n - 1} - 2^{k} = 2^{n} - \frac{2^{n} - 1}{2 - 1} = 1

NAF binary representations have the interesting property that they contain the fewest non-zero digits out of all $(2, 𝒟)$ -representations of the same number. As mentioned in the introduction, this has positive implications for parallel multiplication algorithms. In order to prove this fact, we first need some definitions and a lemma.

Definition 1.9. The Hamming weight of a

(β, 𝒟)

-representation

(x_{n}, \dots, x_{0})

is its count of non-zero digits:

W (x_{n}, \dots, x_{0}) ≔ | {k \in {0, \dots, n} | x_{k} \neq 0} | .

Note. If all non-zero digits in

𝒟

have an absolute value of

1

, then Definition 1.9 can be equivalently expressed as

W (x_{n}, \dots, x_{0}) ≔ \sum_{k = 0}^{n} | x_{k} | .

Definition 1.10. A

(β, 𝒟)

-representation is optimal if its Hamming weight is minimal among all

(β, 𝒟)

-representations of the same number.

Lemma 1.11. Let

𝒟 = {0, \pm 1}

. Then any

(2, 𝒟)

-representation

(x_{n}, \dots, x_{0})

can be converted to a NAF

(2, 𝒟)

-representation of the same number by repeatedly applying the following substitutions:

$1 \overline{1} \mapsto 01$ ,
$\overline{1} 1 \mapsto 0 \overline{1}$ ,
$011 \mapsto 10 \overline{1}$ ,
$0 \overline{1} \overline{1} \mapsto \overline{1} 01$ .

Proof. It is obvious from Definition 1.2 that the substitutions preserve the value of the representation. Also, if this procedure terminates, then the resulting representation has to be NAF, because if there was a pair of non-zero digits next to each other, one of the substitutions could be applied to the first such pair. Therefore, we only need to prove that this procedure terminates. Suppose that

x_{n} = 1

; the proof is analogous for

x_{n} = - 1

. Clearly, the only way the representation can increase in length is by applying the third substitution at the beginning:

11 y_{n - 2} \dots y_{0} \to 10 \overline{1} y_{n - 2} \dots y_{0}

In order for the representation to increase in length again, a series of substitutions would have to change

0 \overline{1} y_{n - 2} \dots y_{0}

into

1 z_{n - 1} z_{n - 2} \dots z_{0}

. However, by Theorem 1.8, the former represents a negative number, whereas the latter represents a positive number. Since the substitutions preserve the value, this is impossible. Therefore, the length of the initial representation can increase at most once. In other words, the length of all intermediate representations is at most

n + 2

. For a given intermediate representation

(y_{n + 1}, \dots, y_{0})

, we define

s (y_{n + 1}, \dots, y_{0}) ≔ \sum_{k = 0}^{n + 1} (n + 2 - k) | y_{k} | .

It can be easily verified that every substitution strictly decreases

s

. Since

s

is a non-negative integer, the procedure always terminates.

Example. Consider the number

119

with its standard binary representation

{(1110111)}_{2}

. By applying these substitutions from right to left, we obtain

\begin{aligned} 119 & = {(1110111)}_{2} \\ = {(11110 \overline{1} 1)}_{2} \\ = {(111100 \overline{1})}_{2} \\ = {(10 \overline{1} 1100 \overline{1})}_{2} \\ = {(100 \overline{1} 100 \overline{1})}_{2} \\ = {(1000 \overline{1} 00 \overline{1})}_{2} \end{aligned}

This gave us the same result as the modular algorithm, which was to be expected because binary NAF representations are unique according to Theorem 1.7. Notice that several of the substitutions decreased the Hamming weight of the representation, whereas none of them increased it. This is the key to proving that binary NAF representations are optimal, as formalized by the following theorem.

Theorem 1.12. Binary NAF representations are optimal: Let

𝒟 = {0, \pm 1}

. Let

(x_{n}, \dots, x_{0})

and

(y_{m}, \dots, y_{0})

be two

(2, 𝒟)

-representations of the same integer, with

(x_{n}, \dots, x_{0})

also being NAF. Then

W (x_{n}, \dots, x_{0}) \leq W (y_{n}, \dots, y_{0})

Proof. By Lemma 1.11, we can convert

(y_{m}, \dots, y_{0})

into a NAF representation

(z_{l}, \dots, z_{0})

of the same number. None of the possible substitutions increase the Hamming weight, therefore

W (z_{l}, \dots, z_{0}) \leq W (y_{m}, \dots, y_{0})

. According to Theorem 1.7, binary NAF representations of the same number are equal, so

W (z_{l}, \dots, z_{0}) = W (x_{n}, \dots, x_{0})

, which concludes the proof.

Not only are binary NAF representations optimal, they have asymptotically fewer non-zero digits on average than standard binary representations. To be specific: If we list all possible standard binary representations of some fixed length (not necessarily reduced), obviously exactly half of the digits will be $0$ and the other half will be $1$ . However, if we do the same with NAF representations in signed binary, the total proportion of non-zero digits will only be approximately $\frac{1}{3}$ , as shown in the following theorem.

Theorem 1.13. Let

𝒟 = {0, \pm 1}

. Let

a_{n}

be the number of all (not necessarily reduced) NAF

(2, 𝒟)

-representations of length

n

and

b_{n}

the sum of the Hamming weights of these representations. Then

\lim_{n \to \infty} \frac{b_{n}}{n a_{n}} = \frac{1}{3}

. That is, for an average sufficiently long NAF

(2, 𝒟)

-representation, about

\frac{1}{3}

of its digits are non-zeros.

Proof. [Proof (taken and modified from [algebraicke-metody]).] Let us find an explicit formula for

a_{n}

and

b_{n}

. We can think of NAF

(2, 𝒟)

-representations as consisting of three kinds of “blocks”:

0, 01 and 0 \overline{1}

. Note that these blocks can only be used to construct representations starting with a zero, so we are actually expressing

a_{n - 1}

and

b_{n - 1}

, but this does not matter when

n \to \infty

. Take one representation with

n

digits and let

k

be its Hamming weight, which corresponds to the number of

01

and

0 \overline{1}

blocks. These blocks take up

2 k

digits, so the number of

0

blocks is

n - 2 k

, for a total of

n - k

blocks. There are

(\binom{n - k}{k})

ways to choose which of these blocks contain a non-zero digit and

2^{k}

ways to choose whether the digit will be

1

\overline{1}

. Therefore, the total number of these representations is

a_{n} = \sum_{k = 0}^{\infty} 2^{k} (\binom{n - k}{k})

and the sum of Hamming weights is

b_{n} = \sum_{k = 0}^{\infty} k 2^{k} (\binom{n - k}{k}),

where we define

(\binom{n}{k}) ≔ 0

for

k > n

so that we do not have to worry about the upper limit. If we also define

(\binom{n}{k}) ≔ 0

for

k < 0

, the formula

(\binom{n}{k}) = (\binom{n - 1}{k}) + (\binom{n - 1}{k - 1})

will work for all

k

, which we can use in finding a recursive expression for

a_{n}

\begin{aligned} a_{n} & = \sum_{k = 0}^{\infty} 2^{k} (\binom{n - k}{k}) \\ = \sum_{k = 0}^{\infty} 2^{k} (\binom{n - k - 1}{k}) + \sum_{k = 0}^{\infty} 2^{k} (\binom{n - k - 1}{k - 1}) \\ = \sum_{k = 0}^{\infty} 2^{k} (\binom{n - k - 1}{k}) + \sum_{k = - 1}^{\infty} 2^{k + 1} (\binom{n - k - 2}{k}) \\ = \sum_{k = 0}^{\infty} 2^{k} (\binom{n - k - 1}{k}) + 2 \sum_{k = 0}^{\infty} 2^{k} (\binom{n - k - 2}{k}) \\ = a_{n - 1} + 2 a_{n - 2} . \end{aligned}

Solving this recurrence using its characteristic polynomial

λ^{2} - λ - 2 = (λ - 2) (λ + 1)

, we get

a_{n} = α 2^{n} + β {(- 1)}^{n}

for some

α, β \in ℝ

. Clearly

α \neq 0

, otherwise some terms would be negative. For

b_{n}

, we analogously have

\begin{aligned} b_{n} & = \sum_{k = 0}^{\infty} k 2^{k} (\binom{n - k}{k}) \\ = \sum_{k = 0}^{\infty} k 2^{k} (\binom{n - k - 1}{k}) + \sum_{k = 0}^{\infty} k 2^{k} (\binom{n - k - 1}{k - 1}) \\ = \sum_{k = 0}^{\infty} k 2^{k} (\binom{n - k - 1}{k}) + \sum_{k = - 1}^{\infty} (k + 1) 2^{k + 1} (\binom{n - k - 2}{k}) \\ = \sum_{k = 0}^{\infty} k 2^{k} (\binom{n - k - 1}{k}) + 2 \sum_{k = 0}^{\infty} k 2^{k} (\binom{n - k - 2}{k}) + 2 \sum_{k = 0}^{\infty} 2^{k} (\binom{n - k - 2}{k}) \\ = b_{n - 1} + 2 b_{n - 2} + 2 a_{n - 2} \\ = b_{n - 1} + 2 b_{n - 2} + 2 α 2^{n - 2} + 2 β {(- 1)}^{n - 2} . \end{aligned}

This is a non-homogenous linear recurrence. The homogenous solution is the same as for

a_{n}

, except with possibly different coefficients

\tilde{α}, \tilde{β} \in ℝ

b_{n}^{hom} = \tilde{α} 2^{n} + \tilde{β} {(- 1)}^{n}

The particular solution is of the form

b_{n}^{par} = μ n 2^{n} + ν n {(- 1)}^{n}

for some

μ, ν \in ℝ

. We can find those by substituting in the recurrence:

μ n 2^{n} + ν n {(- 1)}^{n} - μ (n - 1) 2^{n - 1} - ν (n - 1) {(- 1)}^{n - 1} - 2 μ (n - 2) 2^{n - 2} - 2 ν (n - 2) {(- 1)}^{n - 2} = 2 α 2^{n - 2} + 2 β {(- 1)}^{n - 2}

Collecting terms with

2^{n}

and cancelling, we obtain

μ (n - \frac{n - 1}{2} - \frac{n - 2}{2}) = \frac{α}{2}

μ = \frac{α}{3} \neq 0

This suffices to evaluate the desired limit, since only the fastest-growing terms matter:

\lim_{n \to \infty} \frac{b_{n}}{n a_{n}} = \lim_{n \to \infty} \frac{\tilde{α} 2^{n} + \tilde{β} {(- 1)}^{n} + \frac{α}{3} n 2^{n} + ν n {(- 1)}^{n}}{α n 2^{n} + β n {(- 1)}^{n}} = \frac{1}{3}

In Theorem 1.13, we have shown that NAF binary representations of a fixed length have an asymptotically smaller Hamming weight than standard binary representations. However, one might object that if, on average, the NAF representation of a given number is significantly longer than the standard binary representation, this might not result in such an improvement for fixed numbers. However, as shown in the following theorem, a NAF binary representation of a given integer is at most one digit longer than its standard binary representation. This is in fact already apparent from the proof of Lemma 1.11, but can easily be proven separately.

Theorem 1.14. Let

𝒟 = {0, \pm 1}

. Let

x

be a non-zero integer. Then the reduced NAF

(2, 𝒟)

-representation of

x

has at most

⌊ \log_{2} | x | ⌋ + 2

digits.

Proof. Let

h_{n}

be the smallest positive integer whose binary NAF representation consists of exactly

n

digits. From Theorem 1.8, we know that the representation starts with

1

. To minimize the value while respecting the NAF condition, it is easy to see that this

1

is followed by alternating

0

and

\overline{1}

, so for all

m \in ℕ_{0}

h_{2 m + 1} = {(1 {(0 \overline{1})}^{m})}_{2}, h_{2 m + 2} = {(1 {(0 \overline{1})}^{m} 0)}_{2} .

Consider first the odd case

n = 2 m + 1

. By Definition 1.2,

h_{n} = h_{2 m + 1} = 2^{2 m} - \sum_{k = 0}^{m - 1} 2^{2 k} = 2^{2 m} - \sum_{k = 0}^{m - 1} 4^{k} = 2^{2 m} - \frac{4^{m} - 1}{3} = \frac{2^{n} + 1}{3},

n = \log_{2} (3 h_{n} - 1) < \log_{2} (4 h_{n}) = \log_{2} h_{n} + 2 .

Since

h_{n}

has the minimal absolute value out of all integers with an

n

-digit NAF

(2, 𝒟)

-representation, this concludes the proof for odd

n

. For even

n

h_{n} = 2 h_{n - 1}

, so by the already proven odd case,

n = (n - 1) + 1 < \log_{2} h_{n - 1} + 2 + 1 = \log_{2} h_{n} + 2 .

Complex integers

There are two different natural ways to extend the concept of an integer to complex numbers: either using a square lattice, or using a triangular lattice. These generalizations are called Gaussian integers and Eisenstein integers respectively.

Definition 1.15. The Gaussian integers are the numbers

ℤ [i] ≔ {a + b i | a, b \in ℤ} .

Definition 1.16. Let

ω ≔ \exp (\frac{2}{3} π i) = - \frac{1}{2} + \frac{\sqrt{3}}{2} i

. The Eisenstein integers are the numbers

ℤ [ω] ≔ {a + b ω | a, b \in ℤ} .

It is obvious how to naturally extend the notion of divisibility and modular arithmetic to integers. A more interesting question is how to extend the notion of parity. We could, just like in the ordinary integers, define a complex integer to be even if it is divisible by $2$ . However, this way we would lose the useful property that if $x$ is even, then $x \pm 1$ is odd and vice-versa. Instead, we will use the following definition for the case of Gaussian integers, which preserves this property (additionally ensuring that $x \pm i$ also has the opposite parity from $x$ ):

Definition 1.17. Let

x \in ℤ [i]

. If

x \equiv 0 (m o d i - 1)

, then

x

is even, otherwise

x

is odd. (Note that divisibility by

i - 1

is the same as divisibility by

i + 1

, we are choosing the former for reasons that will be apparent soon.)

However, it is not possible to do this with Eisenstein integers, the reason being that the triangular grid is not a bipartite graph. Note that if there were names for different congruence classes modulo $3$ , they could be generalized to Eisenstein integers by considering congruence classes modulo $ω - 1$ .

The most obvious way to represent complex integers using a positional numeration system is to simply choose a system for representing regular integers and apply it component-wise. However, with the right choice of base and digits, we can naturally represent both kinds of complex integers directly. [binary-system-complex-numbers]

Theorem 1.18. Let

β = i - 1, 𝒟 = {0,1}

. Then every Gaussian integer

x

has a unique reduced

(β, 𝒟)

-representation

(x_{n}, \dots, x_{0})

Proof. Analogously as in the proof of Theorem 1.5, if

x

is even (by Definition 1.17), then

x_{0} = 0

, otherwise

x_{0} = 1

. We then recursively find a representation of

\frac{x - x_{0}}{i - 1}

. It remains to show that this procedure terminates. We can estimate

| \frac{x - x_{0}}{i - 1} | = \frac{| x - x_{0} |}{\sqrt{2}} \leq \frac{| x | + | x_{0} |}{\sqrt{2}} \leq \frac{| x | + 1}{\sqrt{2}} .

This implies that if

| x | > \sqrt{2} + 1

, then

| \frac{x - x_{0}}{i - 1} | < | x |

. Since

| x |

is always the square root of an integer, after finitely many steps we will reach an

x

such that

| x | \leq \sqrt{2} + 1

. Therefore, we just have to manually check that every such

x

has a representation. There are 21 such numbers:

\begin{aligned} 0 & = {()}_{i - 1}, \\ 1 & = {(1)}_{i - 1}, \\ i & = {(11)}_{i - 1}, \\ - 1 & = {(11101)}_{i - 1}, \\ - i & = {(111)}_{i - 1}, \\ 1 + i & = {(1110)}_{i - 1}, \\ - 1 + i & = {(10)}_{i - 1}, \\ - 1 - i & = {(110)}_{i - 1}, \\ 1 - i & = {(111010)}_{i - 1}, \\ 2 & = {(1100)}_{i - 1}, \\ 2 i & = {(1110100)}_{i - 1}, \\ - 2 & = {(11100)}_{i - 1}, \\ - 2 i & = {(100)}_{i - 1}, \\ 2 + i & = {(1111)}_{i - 1}, \\ - 1 + 2 i & = {(11001)}_{i - 1}, \\ - 2 - i & = {(11101011)}_{i - 1}, \\ 1 - 2 i & = {(101)}_{i - 1}, \\ 1 + 2 i & = {(1110101)}_{i - 1}, \\ - 2 + i & = {(11111)}_{i - 1}, \\ - 1 - 2 i & = {(11101001)}_{i - 1}, \\ 2 - i & = {(111011)}_{i - 1} . \end{aligned}

Note. This system is known as the Penney numeration system due to Walter F. Penney being one of the first mathematicians to work with it.

Note. It is apparent from the proofs of Theorem 1.5 and Theorem 1.18 that they could be generalized to a much larger class of positional numeration systems, with the only two requirements being that the digits uniquely cover all congruence classes modulo

β

and that all numbers with an absolute value within some bound have a representation. The general statement is outside the scope of this project, but can be found in [kvaterniony].

Note. It is not possible to represent every Gaussian integer with

β = i + 1

and

𝒟 = {0,1}

. If we tried to find such a representation for some numbers, such as

- 1

, using the modular algorithm, we would get into an infinite loop. This shows that verifying the representability of certain small numbers is an important part of the proof of Theorem 1.18 that cannot be left out.

Theorem 1.19. Let

β = ω - 1, 𝒟 = {0,1, ω + 1}

. Then every Eisenstein integer

x

has a unique reduced

(β, 𝒟)

-representation

(x_{n}, \dots, x_{0})

Proof. Analogous to the proof of Theorem 1.18. The proof is left as an exercise for the reader or it can be found in [kvaterniony].

Representation of complex numbers in redundant numeration systems | Basics

Positional numeration systems

NAF binary representations

Complex integers

Exercises