Let $z$ be a complex non-zero number such that $Re(z),Im(z)\in \mathbb{Z}$. Prove that $z$ is uniquely representable as $a_0+a_1(1+i)+a_2(1+i)^2+\dots+a_n(1+i)^n$ where $n\geq 0$ and $a_j \in \{0,1\}$ and $a_n=1$. Time allowed for this problem was 1 hour.
Problem
Source: Iran 3rd round 2009 - final exam problem 6
Tags: induction, algorithm, function, trigonometry, number theory unsolved, number theory
Nanas
15.01.2015 21:49
We Can order the elements of set $\{ |z| : z \in \mathbb{Z}\left[ i \right] \}$ as $1=x_1 < x_2 < \cdots $. If $z$ can have the required representation, we say $z$ is good. Clearly if $x$ and $y$ are good, then $xy$ is good. We prove that if $z \in \mathbb{Z}\left[ i \right]$ with $|z| = x_i$ then $z$ is good. We use induction on $n$. Now if $n=1$, we have $z=1,-1,i,-i$. Clearly $1$ is good, and as $i = 1+ (1+i) + (1+i)^2 + (1+i)^3 + (1+i)^4 + (1+i)^5$, and $-1 = 1+ 0 \cdot (1+i) + (1+i)^2 + (1+i)^3 + (1+i)^4 + (1+i)^5$. By our observation $-i$ is also good. Now assume the statement is true for all $n \leq k$, and let $|z| = x_{k+1} $, we have by simple algebra $z= (1+i) z' + \delta $, where $z' \in \mathbb{Z}[i]$ and $\delta \in \{0,1\}$. We note that $\frac{|z-\delta|}{\sqrt{2}} = |z'|$.
Now if $\frac{|z-\delta|}{\sqrt{2}} \geq |z|$, we can simply let $z= a +bi$, to note that this happens if and only if $\delta =1$ and \[ (a-1)^2 + b^2 \geq 2(a^2 + b^2) \iff 1-2a \geq a^2 + b^2 \iff 2 geq (a-1)^2 + b^2 \], that is when $z=1,2i+1,2i,1+i$, where $2i+1= 1+(1+i)^2$ and $2i = (1+i)^2$, and the rest are easily seen correct.
if $|z| < \frac{|z-\delta|}{\sqrt{2}} $, so $|z'| < |z| =x_{k+1}$. So $z'$ is good, and clearly then $(1+i)z'$ is good with $a_0=0$, whence $z$ is good.
Uniqueness follow by a simple induction too but on the length of the expansion.
ZetaX
16.01.2015 00:52
This is actually proven the exact same way one shows that there is a (unique) representation in base $2$ (or $3$, $4$, ...). Which goes like this: Let $R$ be a nice enough set of numbers (exact assumptions left to the less lazy reader and not relevant here anyway) and let $b$ be the base. Let $D=\{d_1, ..., d_r\}$ be the "digits" we will use; for the sake of this post this at least means that they uniquely cover the residue classes $\mod b$; having $0 \in D$ is also a good idea. Note: this depends on $R$, for example we could use $0,1$ if the set is $\mathbb Z$ or $\mathbb N$ with $b=2$, but we would need a larger set, e.g. $0,1,i,1+i$, if the set is $\mathbb Z[i] = \{a+bi | a,b \in \mathbb Z\}$. We want to show that every element of $R$ can be (uniquely) written as $a_0+a_1b+...+a_n b^n$ with $a_i \in D$. Algorithm to show the existence: Let $x$ be the number we want to represent. a) Pick a $a_0 \in D$ such that $x \equiv a_0 \mod b$. b) Write $x = a_0 + bx^\prime$ for some $x^\prime \in R$. c) Go back to a) to represent $x^\prime$ in base $b$ as desired. Obviously, one needs to prove that this actually terminates. For example because we have $|x^\prime| < |x|$ for some suitable function $| \cdot |$ with values in nonnegative integers (e.g. $|a+bi| = a^2+b^2$). Uniqueness: Assume $a_0 + ... + a_m b^m = c_0 + ... + c_n b^n$. Looking $\mod b$ gives that $a_0 \equiv c_0 \mod b$ and thus $a_0 = c_0$. Now subtract them on both sides, divide by $b$ and get $a_1 + ... + a_m b^{m-1} = c_1 + ... + c_{n-1} b^{n-1}$. Rince and repeat.
Nanas
16.01.2015 01:02
That's exactly my motivation for the proof, I recalled that for natural numbers, and simply modified it in order to have $D=\{0,1\}$ and not $\{0,1,i\}$
yunxiu
21.01.2015 08:04
ZetaX wrote: c) Go back to a) to represent $x^\prime$ in base $b$ as desired. Obviously, one needs to prove that this actually terminates. For example because we have $|x^\prime| < |x|$ for some suitable function $| \cdot |$ with values in nonnegative integers (e.g. $|a+bi| = a^2+b^2$). . $ - 1 = 1 + (i - 1)(1 + i)$, but $\left| { - 1} \right| < \left| {i - 1} \right|$?
mavropnevma
21.01.2015 09:20
Nanas wrote: ... $i = 1+ (1+i) + (1+i)^2 + (1+i)^3 + (1+i)^4 + (1+i)^5$ ... No, $1+ (1+i) + (1+i)^2 + (1+i)^3 + (1+i)^4 + (1+i)^5 =$ $ \dfrac {(1+i)^6-1}{(1+i)-1} =$ $\dfrac {-8i-1}{i} =$ $ -8 + i \neq i$. In fact, $1+i = \sqrt{2}\left (\cos \dfrac {\pi}{4} + i\sin \dfrac {\pi}{4}\right )$, so $(1+i)^n = \sqrt{2^n}\left (\cos \dfrac {n\pi}{4} + i\sin \dfrac {n\pi}{4}\right )$, so for $n\geq 2$ the coefficient of $i$ in $(1+i)^n$ is even. Assume now $i = a_0 + a_1(1+i) + a_2(1+i)^2 + \cdots + a_{n-1}(1+i)^{n-1} + (1+i)^n$ for some $n$ and $a_j \in \{0,1\}$ for $0\leq j \leq n-1$. This forces $n\geq 1$ and $a_1=1$, and so $- (1+a_0) = i - a_0 - (1+i) = a_2(1+i)^2 + \cdots + a_{n-1}(1+i)^{n-1} + (1+i)^n$. But $- (1+a_0)\neq 0$, which forces $n\geq 2$ and $1+i \mid - (1+a_0)$, therefore $a_0=1$ and so $- (1+a_0) = -2 = (i-1)(1+i)$. Cancelling $1+i$ we get $i-1 = a_2(1+i) + \cdots + a_{n-1}(1+i)^{n-2} + (1+i)^{n-1}$. This forces $a_2=1$, so $(i-1)(1+i) = -2 = a_3(1+i)^2 + \cdots + a_{n-1}(1+i)^{n-2} + (1+i)^{n-1}$, thus $n\geq 3$ and cancelling $1+i$ we get $i-1 = a_3(1+i) + \cdots + a_{n-1}(1+i)^{n-3} + (1+i)^{n-2}$. This procedure repeats, and leads to an obvious contradiction. Therefore $i$ cannot be so represented, and the problem is wrong as stated.
ZetaX
21.01.2015 14:44
yunxiu wrote: ZetaX wrote: c) Go back to a) to represent $x^\prime$ in base $b$ as desired. Obviously, one needs to prove that this actually terminates. For example because we have $|x^\prime| < |x|$ for some suitable function $| \cdot |$ with values in nonnegative integers (e.g. $|a+bi| = a^2+b^2$). . $ - 1 = 1 + (i - 1)(1 + i)$, but $\left| { - 1} \right| < \left| {i - 1} \right|$? This shows that the usual modulus does not work. I did not check this special problem (as I don't find it particulary interesting), and as mavropnevma shows it is actually wrong.
IAmTheHazard
22.02.2021 00:13
If $(1+i)$ is replaced with $(-1+i)$ everywhere the problem should work. In fact for a fixed $k$, any such $z$ can be uniquely represented as $a_0+a_1(-k+i)+a_2(-k+i)^2+\cdots+a_n(-k+i)^n$ where $a_n \neq 0$ and $a_i \in \{0,1,\ldots n^2\}$.