ogeometrie: august 2022

LEMMA Let $P(X)=\sum_{j=0}^pa_jX^{p-j}$ be a polynomial with integer coefficients, divisible by the polynomial $X^2+\mu X+\nu\;\in \mathbb{Z}[X]$. Then the quotient of the division $P\;:\;(X^2+\mu X+\nu)$ has integer coefficients.

Proof of Lemma

Let the result of the division be $$Q(X)=P(X) \;:\;(X^2+\mu X+\nu)=\sum_{j=0}^{p-2}b_jX^{p-2-j}.$$

Identifying the coefficients of the indeterminates $X^k,\;k=p,\;p-1,\cdots,\;1,\;0$ in the equation $P(X)=(X^2+\mu X+\nu)\cdot Q(X)$, i.e.

$$\sum_{j=0}^pa_jX^{p-j}=(X^2+\mu X+\nu)(b_0X^{p-2}+b_1X^{p-3}+\cdots+b_{p-3}X+b_{p-2})$$

we get equations

$$\begin{cases}a_0=b_0\\ a_1=b_1+\mu b_0\\ a_2=b_2+\mu b_1+\nu b_0\\\;\vdots \\a_j=b_j+\mu b_{j-1}+\nu b_{j-2}\\\;\vdots \\a_{p-2}=b_{p-2}+\mu b_{p-3}+\nu b_{p-4}\\a_{p-1}=\mu b_{p-2}+\nu b_{p-3}\\a_p=\nu b_{p-2}\;.\end{cases}$$

Obviously that $b_0=a_0,\;b_1=a_1-\mu b_0,\;\cdots,\;b_{p-2}=a_{p-2}-\mu b_{p-3}-\nu b_{p-4}\in \mathbb{Z}$.

end $\square$ Lemma

SOLUTION of PROBLEM {unfinished}

Demonstration_CiP of UNIQUENESS

If a certain number $z$ admits two representations

$$z=\sum_{k=0}^m\varepsilon_k(1+\imath)^k=\sum_{l=0}^n\varepsilon'_l(1+\imath)^l\;\;\;\;\varepsilon,\;\varepsilon' \in \{0,1\}$$

then there is a relationship of this kind

$$\sum_{j=0}^p \delta_j(1+\imath)^j=0\;,\;\;\delta_j\in \{-1,0,1\}. \tag{1}$$

We will prove that in (1), all $\delta_j$ must be $0$.

We assume that the opposite occurs. If $p$ is the largest index for which $\delta_j \neq 0$, then, possibly changing the $\pm$ signs, we obtain that the equation (renumbering also the coefficients)

$X^p+\delta_1X^{p-1}+\cdots+\delta_{p-1}X+\delta_p=0,\;\;\;\delta_j \in \{-1,0,1\} \tag{2}$

has the root $1+\imath$. The equation being with real number coefficients, it will also have the root $1-\imath$ (and with the same order of multiplicity). So we have divisibility

$$X^p+\delta_1 X^{p-1}+\cdots +\delta_{p-1}X+\delta_p\;\vdots\;(X-1-\imath)(X-1+\imath).$$

Then there exists a polynomial $Q(X)\in \mathbb{Z}[X]$ (cf. LEMMA) with the property

$$(X^2-2X+2)\cdot Q(X)=X^p+\cdots+\delta_{p-1}X+\delta_p.$$

Taking $X=0$ into this equality, we will have $2\cdot Q(0)=\delta_p\;$. So $\delta_p\; \vdots \;2$ and how $\delta_p=0,\;\pm 1$ it results $\delta_p=0$.

Dividing the equation (2) by $X$, we get the new equation

$$X^{p-1}+\delta_1X^{p-2}+\cdots +\delta_{p-2}X+\delta_{p-1}=0,$$

having a root $1+\imath$; it turns out the same that $\delta_{p-1}=0$, and so on...

$\blacksquare$

Demonstration_CiP of implication

$z$ can be represented $\;\Rightarrow\;\imath-z\;$ cannot

Let's assume that both $z$ and $\imath-z$ admit the representations

$$z=\sum_{k=0}^n\varepsilon_k(1+\imath)^k,\;\;\imath-z=\sum_{l=0}^m\varepsilon_l'(1+\imath)^l,\;\varepsilon_k,\varepsilon_l' \in \{0,1\}.$$

$$\Rightarrow\;\imath =\sum_{k=0}^n \varepsilon_k(1+\imath)^k+\sum_{l=0}^m\varepsilon_l'(1+\imath)^l$$

$$\Rightarrow\;\imath =\sum_{j=0}^p \alpha_j(1+\imath)^j,\;\alpha_j \in \{0,1,2\}. \tag{3}$$

We consider the polynomial

$$\sum_{j=0}^p\alpha_j(1+X)^j-X,\;\;\alpha_j \in \{0,1,2\}.$$

The relation (3) tells us that this polynomial has root $\imath$, and being with real coefficients it will also have root $-\imath$. So the polynomial is divisible by $X^2+1$, that is, there exists the polynomial $S(X) \in \mathbb{Z}[X]$ (cf. LEMMA) such that

$$(X^2+1)S(X)=\sum_{j=0}^p\alpha_j(1+X)^j-X.$$

Taking $X=-1$ into the above equation, we get $2\cdot S(-1)=1$, impossible in integer numbers.

$\blacksquare \blacksquare$

Conclusion. So far we have demonstrated

$z$ can be represented $\Rightarrow\;\imath-z$ cannot

or equivalent

$\imath-z$ can be represented $\Rightarrow\;z$ cannot.

It remains to be shown

$\imath-z$ cannot be represented $\;\Rightarrow\;\;z$ can it

or equivalent

$z$ cannot be represented $\;\Rightarrow\;\imath -z$ can it.

By reduction to the absurd, we should obtain a contradiction from the fact that $z$ and $\imath -z$ cannot be represented.[???]

$\ddagger$Digression. On a page of James Propp (one of the authors of the problem) I found a discussion of the same phenomenon. Here’s a picture (looks like a Dragon) showing all 256 of the Gaussian integers expressible in the form

a(1+i)7 + b(1+i)6 + c(1+i)5 + d(1+i)4 + e(1+i)3 + f(1+i)2 + g(1+i)1 + h(1+i)0

where each of the numbers a,b,c,d,e,f,g,h is either 0 or 1.

I think the following note is the key to solving the problem:

[Note: After this article “went to press” Tom Karzes and Steve Lucas and I proved that the set of nonexpressible Gaussian integers is the set of expressible Gaussian integers rotated by 180 degrees about the complex number i/2.]

In reality, the $180^{\circ}$-rotation around $\imath /2$ is the symmetry with respect to this point. As you can see in the figure, the point reflection of $A$ w.r.t. point $S$ is the point $A'$.