Representation of complex numbers in redundant numeration systems | 𝑤-NAF representations of complex integers

In Chapter 1, we extended the standard binary system by adding the digit

- 1

, creating a system where a number can have multiple representations, then restricted it to NAF representations, which once again guaranteed uniqueness while also decreasing the average ratio of non-zero digits in a representation. In this chapter, we will show analogous systems for the Gaussian and Eisenstein integers.

Gaussian integers

We shall start by adding the digit $- 1$ to the Penney system; that is, we use $β = i - 1, 𝒟 = {0, \pm 1}$ . The natural question is whether every Gaussian integer has a NAF representation in this system. It is not hard to find that the answer is negative. For example, the number $i$ is odd, so its representation would have to end in either $1$ or $- 1$ , but after subtracting either digit and dividing by $i - 1$ , we are left with another odd number, forcing us to add another non-zero digit.

However, we can add two more digits without violating the useful property that the set of digits is closed under multiplication: $i$ and $- i$ . As with $- 1$ , we will denote $- i$ as $\overline{i}$ when used as a digit. The resulting system is the main subject of this project, so we shall give it a name.

Definition 2.1. The extended Penney system is the positional numeration system with

β = i - 1

and

𝒟 = {0, \pm 1, \pm i}

Obviously, most Gaussian integers can be represented in multiple ways in this system. However, they can even have multiple NAF representations, for example ${(1)}_{i - 1} = {(i 0 \overline{1})}_{i - 1} = 1$ . This suggests that we could restrict the possible representations even further in order to possibly obtain even better results in terms of average weight. It turns out that a simple generalization of the NAF condition is sufficient.

Definition 2.2. Let

w \in ℕ^{+}

. A positional representation

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

is in

w

-non-adjacent form (

w

-NAF) if every contiguous subsequence of length at most

w

contains at most one non-zero digit, that is,

\forall k \in ℕ, W (x_{k + w - 1}, \dots, x_{k}) \leq 1 .

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

1

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

\forall k \in ℕ, \sum_{j = k}^{k + w - 1} | x_{j} | \leq 1 .

Note. Trivially, every representation is

1

-NAF and the

2

-NAF condition is equivalent to the original NAF condition.

Lemma 2.3. Let

x

be an odd Gaussian integer. Then there exists exactly one

x_{0} \in {\pm 1, \pm i}

such that

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

Proof. Notice that

(2 + 2 i) | 4

. Let

x = a + b i, a, b \in ℤ

. Consider the possible congruence classes of

a, b

modulo

4

, which cannot have the same parity since

x

is odd:

$a \equiv 0 (m o d 4) \land b \equiv 1 (m o d 4) ⟹ x \equiv i (m o d 4) ⟹ x \equiv i (m o d 2 + 2 i)$ ,
$a \equiv 0 (m o d 4) \land b \equiv - 1 (m o d 4) ⟹ x \equiv - i (m o d 4) ⟹ x \equiv - i (m o d 2 + 2 i)$ ,
$a \equiv 2 (m o d 4) \land b \equiv 1 (m o d 4) ⟹ x \equiv 2 + i (m o d 4) ⟹ x \equiv - i (m o d 2 + 2 i)$ ,
$a \equiv 2 (m o d 4) \land b \equiv - 1 (m o d 4) ⟹ x \equiv 2 - i (m o d 4) ⟹ x \equiv i (m o d 2 + 2 i)$ ,
$a \equiv 1 (m o d 4) \land b \equiv 0 (m o d 4) ⟹ x \equiv 1 (m o d 4) ⟹ x \equiv 1 (m o d 2 + 2 i)$ ,
$a \equiv - 1 (m o d 4) \land b \equiv 0 (m o d 4) ⟹ x \equiv - 1 (m o d 4) ⟹ x \equiv - 1 (m o d 2 + 2 i)$ ,
$a \equiv 1 (m o d 4) \land b \equiv 2 (m o d 4) ⟹ x \equiv 1 + 2 i (m o d 4) ⟹ x \equiv - 1 (m o d 2 + 2 i)$ ,
$a \equiv - 1 (m o d 4) \land b \equiv 2 (m o d 4) ⟹ x \equiv - 1 + 2 i (m o d 4) ⟹ x \equiv 1 (m o d 2 + 2 i)$ .

This shows that

x_{0}

exists. It is also unique because none of

{\pm 1, \pm i}

are congruent modulo

2 + 2 i

Theorem 2.4. Every

x \in ℤ [i]

has exactly one reduced

3

-NAF representation

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

in the extended Penney system.

Proof. Once again, we will use a modular algorithm to find the representation. If

x

is even, then the last digit has to be

0

. If

x

is odd, we have a choice between four digits:

\pm 1

and

\pm i

, but in order to fulfill the

3

-NAF constraint, we need the following two digits to be zeros, meaning that

x - x_{0}

has to be divisible by

{(i - 1)}^{3} = 2 + 2 i

. Lemma 2.3 ensures that there is precisely one choice. Either way, we continue by finding the representation of

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

. It remains to be proven that this procedure terminates. This can be done using the exact same argument as in the proof of Theorem [t-penney-uniq], except with different representations for small numbers:

\begin{aligned} 0 & = {()}_{i - 1}, \\ 1 & = {(1)}_{i - 1}, & i & = {(i)}_{i - 1}, & - 1 & = {(\overline{1})}_{i - 1}, & - i & = {(\overline{i})}_{i - 1}, \\ 1 + i & = {(\overline{i} 0)}_{i - 1}, & - 1 + i & = {(10)}_{i - 1}, & - 1 - i & = {(i 0)}_{i - 1}, & 1 - i & = {(\overline{1} 0)}_{i - 1}, \\ 2 & = {(i 00)}_{i - 1}, & 2 i & = {(\overline{1} 00)}_{i - 1}, & - 2 & = {(\overline{i} 00)}_{i - 1}, & - 2 i & = {(100)}_{i - 1}, \\ 2 + i & = {(100 \overline{i})}_{i - 1}, & - 1 + 2 i & = {(i 001)}_{i - 1}, & - 2 - i & = {(\overline{1} 00 i)}_{i - 1}, & 1 - 2 i & = {(\overline{i} 00 \overline{1})}_{i - 1}, \\ 1 + 2 i & = {(100 \overline{1})}_{i - 1}, & - 2 + i & = {(i 00 \overline{i})}_{i - 1}, & - 1 - 2 i & = {(\overline{1} 001)}_{i - 1}, & 2 - i & = {(\overline{i} 00 i)}_{i - 1} . \end{aligned}

Example. Let us find the

3

-NAF representation of

- 3 + 11 i

in the extended Penney system. Because the number is even, we start by writing a

0

and dividing by

i - 1

\frac{- 3 + 11 i}{i - 1} = 7 - 4 i .

This number is odd, so we have to find an

x_{1} \in {\pm 1, \pm i}

such that

x_{1} \equiv 7 - 4 i (m o d 2 + 2 i)

. We choose

x_{1} = - 1

because

(7 - 4 i) - (- 1) = 8 - 4 i

is divisible by

2 + 2 i

. Now, we could divide

8 - 4 i

i - 1

and continue. However, we know that the next two digits will be zeros, so we might as well write them immediately and divide by

2 + 2 i

directly:

\frac{8 - 4 i}{2 + 2 i} = 1 - 3 i .

We see that this is an even number, so we write another

0

and divide by

i - 1

, yielding

- 2 + i

. This number is odd, so we need to find a digit which, when subtracted, gives a number divisible by

2 + 2 i

. Such a digit is

- i

, giving

- 2 + 2 i

. Again, we can write two zeros and directly divide by

2 + 2 i

, getting

i

. This is just a single digit, so we write it down and terminate, getting the result

- 3 + 11 i = {(i 00 \overline{i} 000 \overline{1} 0)}_{i - 1} .

Now that we have proven that the $3$ -NAF extended Penney system is usable for uniquely (up to leading zeros) representing Gaussian integers, the next step is to find out how it performs in terms of the Hamming weight. Like in Lemma [t-naf-subst], it can be proven that every possible extended-Penney representation can be converted into an equivalent $3$ -NAF representation using a set of substitutions that never increase the Hamming weight. However, this set consists of a total of $312$ substitutions and requires temporarily switching to a larger set of digits. Therefore, we are going to avoid this method of proving the optimality of the representations and leave it for the next chapter, which is going to introduce a transducer for converting any representation to $3$ -NAF. What we can prove right now, however, is a result analogous to Theorem [t-naf-ratio]: the asymptotic behavior of the ratio of non-zero digits to all digits.

Theorem 2.5. Let

a_{n}

be the number of all (not necessarily reduced)

3

-NAF extended Penney system 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}{4}

. That is, for an average sufficiently long

3

-NAF extended Penney system representation, about

\frac{1}{4}

of its digits are non-zeros.

Proof. Let us find an explicit formula for

a_{n}

and

b_{n}

. We can think of

3

-NAF extended Penney system representations as consisting of five kinds of “blocks”:

0, 00 i, 001, 00 \overline{1} and 0 \overline{i}

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

a_{n - 2}

and

b_{n - 2}

, but this does not matter when

n \to \infty

. Analougously as in the proof of Theorem [t-naf-ratio], we derive

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

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

and find a recurrence relation for

a_{n}

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

Solving this recurrence using its characteristic polynomial

λ^{3} - λ^{2} - 4 = (λ - 2) (λ^{2} + λ + 2) = (λ - 2) (λ - κ) (λ - \overline{κ}),

where

κ = \frac{- 1 + \sqrt{7} i}{2}

, we get

a_{n} = α 2^{n} + β κ^{n} + γ {\overline{κ}}^{n}

for some

α, β, γ \in ℂ

. Finding a recurrence for

b_{n}

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

Homogenous solution:

b_{n}^{hom} = \tilde{α} 2^{n} + \tilde{β} κ^{n} + \tilde{γ} {\overline{κ}}^{n}

Particular solution:

b_{n}^{par} = μ n 2^{n} + ν n κ^{n} + ω n {\overline{κ}}^{n}

It is evident from the proof of Theorem [t-naf-ratio] that we only need to find the value of

μ

, since

| κ | = \sqrt{2} < 2

. Therefore, when substituting in the recurrence, we only consider terms with

2^{n}

μ n 2^{n} - μ (n - 1) 2^{n - 1} - 4 μ (n - 3) 2^{n - 3} = 4 α 2^{n - 3}

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

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

Substituting into the limit:

\lim_{n \to \infty} \frac{b_{n}}{n a_{n}} = \lim_{n \to \infty} \frac{\tilde{α} 2^{n} + \tilde{β} κ^{n} + \tilde{γ} {\overline{κ}}^{n} + \frac{α}{4} n 2^{n} + ν n κ^{n} + ω n {\overline{κ}}^{n}}{α n 2^{n} + β n κ^{n} + γ n {\overline{κ}}^{n}} = \frac{1}{4}

Notice that this is more efficient in terms of the non-zero digits ratio than if we were to represent Gaussian integers by representing the real and imaginary parts separately using the binary NAF system, which would yield a ratio of $\frac{1}{3}$ as shown in Theorem [t-naf-ratio].

Representation of complex numbers in redundant numeration systems | w-NAF representations of complex integers

Gaussian integers

Eisenstein integers

Representation of complex numbers in redundant numeration systems | $w$ -NAF representations of complex integers