# [seqfan] Re: Project: sequences obtained from Gaussian Integers via Penney's binary method of encoding?

Андрей Заболотский zabolotis at mail.ru
Tue Sep 6 23:50:15 CEST 2016

> Solomon I. Khmelnik, "Specialized Digital Computer for Operations with Complex Numbers" (in Russian), Questions of Radio Electronics, volume 12, number 2, 1964.

It is available at  http://izdatelstwo.com/clicks/clicks.php?uri=lib.izdatelstwo.com/Papers2/s4.djvu

It is devoted to expansions of a complex number z of the form (1):
z = \sum_{k = -\infty}^M  \alpha_k \rho^k,
where "digits" \alpha_k are integers from the intevral 0..R-1 with some fixed integer R and some fixed complex number \rho ("base").

Therems 1--3 are a quotation from  http://bcpw.bg.pw.edu.pl/Content/1628/ZP_praca_BullMath57.pdf  ; theorems 4--7 are proved in the paper, and they state the following:

Theorem 4. For any complex number z and fixed R, there exists an expansion of the above-given form with \rho = \pm i \sqrt{R}.
Theorem 5. For any complex number z and fixed R, there exists an expansion of the above-given form with \rho = \sqrt{R/2} (-1 \pm i) if \sqrt{R/2} is a positive integer.
Theorem 6. If the expansions of theorem 4 are finite (k is bounded not only from above but also from below), then they are unique; for a given R, the numbers z = u + i v which have two or four distinct (infinite) expansions satisfy either u = V(R) or v = V(R) \sqrt{R}, or both these conditions, where
V(R) = \pm R^k/(1+R) + C R^{k+1},
k and C are any integers.
Theorem 7. If the expansions of theorem 5 are finite, then they are unique; for a given R, the numbers z = u + i v which have two or four distinct (infinite) expansions satisfy either u = V(R^2) or v = V(R^2) R, or both these conditions, with the same V(R).

So, theorems 5 and 7 describe the case of base i-1 if we set R=2 and ensure that all Gaussian integers can be uniquely and finitely expressed in that base, although not necessarily with "integer part" only.

Another paper by Khmelnik ("Positional Coding of Complex Numbers" (in Russian), Questions of Radio-electronics, v. 12, no. 9, p. 115, 1966,  http://izdatelstwo.com/clicks/clicks.php?uri=lib.izdatelstwo.com/Papers2/s5.djvu  ) provides the proofs for the following theorems:
Theorem 2. For fixed R and \rho, the sufficient condition for the existance of the expansion of the above-given form for any z is the existance of such expansions for z = R and z = -R where k in the sum runs through positive integers only in both cases.
Theorem 3. For any R, number \rho = \sqrt{R} exp(i \phi),  \cos\phi = (-\beta/(2\sqrt{R})) with integer \beta, 0 < \beta < min(R, 2\sqrt{R}), satisfies the condition of theorem 2.
Actually, there is a small mistake, and the boundaries for \beta are simply 0 < \beta < 2\sqrt{R}. \beta = R = 2 gives base i-1 again.

These two theorems do not ensure anything about the finiteness of the expansions for arbitrary z though. They do not say anything about the necessary condition as well.

>Воскресенье, 28 августа 2016, 12:51 +03:00 от Kevin Ryde via SeqFan <seqfan at list.seqfan.eu>:
>
>antti.karttunen at gmail.com (Antti Karttunen) writes:
>>
>> (but please tell if it is much older and discovered in some other country!)
>
>Another early reference but which I haven't actually seen
>
>    Solomon I. Khmelnik, "Specialized Digital Computer for Operations
>    with Complex Numbers" (in Russian), Questions of Radio Electronics,
>    volume 12, number 2, 1964.
>
>> Or are there better ones for Gaussian Integers?
>
>A few sequences go by square spiral (like Ulam plotted primes on).
>
>> A066321 "Binary representation of base i-1 expansion of n:
>
>Existing sequences I know,
>
>    A066321    N on X axis, being the base i-1 positive reals
>    A066322    diffs (N at X=16k+4) - (N at X=16k+3)
>    A066323    N on X axis, number of 1 bits
>    A137426    dY at N=2^k-1 (step to next replication level)
>    A003476    boundary length / 2
>                 recurrence a(n) = a(n-1) + 2*a(n-3)
>    A203175    boundary length, starting from 4
>                 (believe its recurrence is true)
>    A052537    boundary length part A, B or C, per Gilbert's paper
>
>"Boundary length" is with each Gaussian integer as a unit square.
>(I think the diffs question in A066322 would be answered from Penney,
>with X axis as hex digits 0,1,C,D, something, something :-).
>
>The correspondence of base i-1 to twindragon interior unit squares means
>various dragon curve sequences (like A003476) probably have
>interpretations in i-1, but maybe at a stretch.
>
>> "base i-1" is not really a good term to search for.
>
>I've been happy enough with i-1 in non-oeis things.  A few people call
>it twindragon because the limit fractal is the same, but for integers I
>find that unclear.
>
>Base i-m with other integer m is also possible, digits 0 to norm(i-m)-1.
>Gilbert's boundary calculation is for that general case.  I think the
>number of digits you then need in i-m to represent points relatively
>close to the origin becomes even bigger than say the 5 bits you noted
>for z=-1.
>
>http://www.math.uwaterloo.ca/~wgilbert/Research/GilbertFracDim.pdf
>
>--
>Seqfan Mailing list -  http://list.seqfan.eu/