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 '20 at 11:35
  • $\begingroup$ @Wolfgang Thanks for those observations! $\endgroup$ – Alan C Dec 3 '20 at 22:41

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 '20 at 5:06
  • $\begingroup$ Thank you for this reference! Quite an interesting title. $\endgroup$ – Alan C Dec 15 '20 at 3:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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