Short version of my question: I'm interested in the following fact.

If $m,n$ are odd integers, then $m/n$ can be written as the ratio of two numbers of the form $\sum_{j=0}^\ell \epsilon_j 4^j$, where $\epsilon_j \in \{-1,0,1\}$.

More background:

Let $A = \{0,1,4,5,16,\ldots\}$ be the set of nonnegative integers whose base 4 expansion contains only the digits 0 and 1.

Given a number $r \in \mathbb Q \setminus \{0\}$, there is a unique way (up to sign) to write $r = 4^k \frac{m}{n}$, where (1) $k \in \mathbb Z$, (2) $m$ and $n$ are not divisible by 4, and (3) $\gcd(m, n) = 1$.

Then the following is true:

Theorem: Let $r \in \mathbb Q \setminus \{0\}$. Then $r \in \frac{A-A}{A-A} = \{ \frac{a-b}{c-d} ~|~ a,b,c,d \in A\}$ if and only if both $m$ and $n$ are odd.

The "only if" direction can be proved easily with elementary number theory. (Every nonzero element of $A-A$ contains an even number of factors of $2$.)

For the "if" direction, the only proof I know is in Section 10.3 of Mattila's Fourier Analysis and Hausdorff Dimension (and is based on Kenyon's 1997 paper Projecting the one-dimensional Sierpinski gasket). The proof looks at the Fourier transforms of measures defined on projections of the four-corner Cantor set. Actually, the textbook proves something else, and the theorem I stated above is a corollary. This leads me to wonder if there is an easier proof of the "if" direction of the theorem above (e.g., via elementary number theory).

  • 2
    $\begingroup$ I ran a little program for small $m,n$ looking for the smallest common factor needed. Already for $207/411 $, the smallest factor is $15203$. For $585/1171 $, the smallest factor is as much as $114411$, and for $3867 / 7735 $, it is already $2218921$. This suggests that a more elementary proof for the existence fo such a factor may be, so to say, hard to find. It seems like the smallest factor tends to be especially high when $n=\lambda m\pm1$ with $\lambda=2$ or $\lambda=8$. $\endgroup$
    – Wolfgang
    Dec 2, 2020 at 11:35
  • $\begingroup$ @Wolfgang Thanks for those observations! $\endgroup$
    – Alan C
    Dec 3, 2020 at 22:41

1 Answer 1


You can find an elementary proof in this paper with a very honest title:

J.H. Loxton, A.J. van der Poorten, "An awful problem about integers in base four" Acta Arith., 49 (1987), pp. 193-203

In the paper the authors prove that any integer $m$ with an even number of $2$'s in its prime factorization can be written as a number of the form $\frac{A-A}{A-A}$. This is derived as a simple corollary of the main theorem which says that $A_k+nA_k$ eventually has fewer than $4^k$ terms, for large enough $k$. Here $A_k$ denotes the members of $A$ with at most $k$ digits. Their proof applies verbatim to the set $mA_k+nA_k$, which then implies the claim in your question about fractions $m/n$.

I personally find this elementary proof to still be quite similar in spirit to Kenyon's argument. Self similarity and Fourier transforms aren't mentioned, but they are respectively replaced by the recurrence relations $$(mA_{k+1}+nA_{k+1})=(mA_k+nA_k)+4^{k}(mA_1+nA_1)$$ $$(mA_{k+1}+nA_{k+1})=4(mA_k+nA_k)+(mA_1+nA_1)$$ and the generating function $$\prod_{j=1}^k (1+\theta^{-m4^j})(1+\theta^{-n4^j})$$ respectively.

  • 7
    $\begingroup$ The title of the paper was very much in the spirit of Alf van der Poorten's personality. $\endgroup$
    – Terry Tao
    Dec 14, 2020 at 5:06
  • $\begingroup$ Thank you for this reference! Quite an interesting title. $\endgroup$
    – Alan C
    Dec 15, 2020 at 3:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.