MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I came across the following simple question: what odd integer squares have exactly 3 ones in their binary expansion?

After looking at it for a while I convinced myself that the only solutions to $r^2 = 1+ 2^m + 2^n$ (with $n > m \ge 3$) are $n=2m-2$ (the "trivial" case) and $(m,n) = (4,5),(4,9)$ (the "sporadic" cases). My first attempt was to analyze things 2-adically: write out the Taylor Series: $f(x) = 1 - 2 \sum_{n=1}^{\infty} (-1)^n C_{n-1} x^n$, where $C_n = \frac{1}{n+1} \binom{2n}{n}$ is the $n$-th Catalan number, and $v_2(x) > 0$. We have $f(x)^2 = 1 + 4x$, so that $a_m := \sqrt{1+2^m} = f(2^{m-2})$ (Note that $1+2^m$ is not a rational square when $m \ne 3$). If such an integer $r$ exists, then we must have $r \equiv \epsilon(a_m + 2^{n-1}) \bmod {2^{n+1}}$, where $\epsilon = \pm 1, \pm (1+2^n)$ is one of the 4 square roots of 1 modulo $2^{n+1}$. Also, we must have $r < 2^{(n+1)/2}$. To get rid of the annoying cases, take all of this modulo $2^{n-1}$, where we find that the top $(n-3)/2$ bits of $a_m \bmod 2^{n-1}$ must be either all 0's or all 1's. By writing out the first few terms of $f(x)$ I found that there's a run of $m-2$ 0's which corresponds to the trivial solution, and a run of $m-1$ 1's which corresponds to the sporadic solution (the condition that $m-1 \ge (n-3)/2$ limits the possible $m$'s and $n$'s to a small set). However, I don't see any easy way to show that there are no long "runs" of 1's or 0's among the higher bits of $a_m$ (by the bits, I mean to write out $a_m = \sum_{n=0}^{\infty} b_{m,n} 2^n$, where $b_{m,n} \in \{0,1\}$). Such a statement would be to the effect that we can't approximate $a_m$ too closely by small integers -- this is the sort of $p$-adic Diophantine approximation statement that I would think should be true, but I can't find it.

Absent that, another approach is via $S$-unit equations. This show (see below) that for each $m$, there are only a finite number $n$'s for which $1+2^m + 2^n$ is a rational square, but I'd like to prove (with the exception of the sporadic solution) that there is exactly 1. Since, as I mentioned above, $1+2^m$ is not a rational square when $m > 3$, denote by $K = K_m = \mathbb{Q}(\sqrt{1+2^m})$. It's easy to see that the prime 2 splits in $K$: call $\frak{a},\frak{a}'$ the ideals above 2. Let $k>0$ denote the order of $\frak{a}$ in the ideal class group of $K$ and $\beta$ a generator of the principal ideal $\frak{a}^k$. Also denote conjugation of $K/\mathbb{Q}$ by $\quad '$. Then we have $r+\sqrt{1+2^m} = \epsilon \beta^t 2^u$, for some non-negative integers $t,u$ and $\epsilon \in K$ is a unit. Note that we might need to look at $r-\sqrt{1+2^m}$ instead. By taking norms we see that $2^{2n} = 2^{2u + kt}$, so that $2n = 2u+kt$. By noting that $\epsilon \beta^t 2^u - \epsilon' {\beta'}^t 2^u = 2 \sqrt{1+2^m}$, we see that $u=0,1$. For each of those values we then have an equation of the form $\alpha - \alpha' = \gamma$, where $\gamma$ is fixed, and $\alpha,\alpha'$ are $S$-units (here $S$ consists of the primes above 2), so we know that there are only a finite number of solutions. Any suggestions as to how to proceed to show that my initial guesses are correct?

share|cite|improve this question
And $7^2=1+2^4+2^5$.. – Pietro Majer Apr 2 '13 at 20:15
Fun question. May I suggest that you separate more clearly, typographically, your question proper from the attempts you made to solve it, for example by beginning a new paragraph with "my first attempt"? – Joël Apr 2 '13 at 20:16
up vote 14 down vote accepted

This was solved in a paper of Szalay (in Indag. Math. in 2002), using lower bounds for approximations to $\sqrt{2}$ by rationals with denominators of the form $2^k$ (obtained by Beukers using Pad\'e approximations to $\sqrt{1-z}$).

share|cite|improve this answer
@Mike: Thanks for the reference. Here's a link to the paper . The heavy lifting was done by Beukers, who showed that there are only at most 4 solutions to $x^2 - D = 2^n$ (variables, $x$ and $n$) – Victor Miller Apr 3 '13 at 1:39
@Mike: I can see why you were familiar with Szalay's paper. You were being too modest not mentioning your preprint: – Victor Miller Apr 3 '13 at 1:46
Thanks, Victor. If you read the paper, you'll see that I have much to be modest about... – Mike Bennett Apr 3 '13 at 3:06
@Mike, You're welcome. I just finished looking at your paper in more detail. Your 3-adic argument for the corresponding base 3 problem is similar to the 2-adic argument that I gave above (though the 2-adic case is a bit simpler since you only have 0/1 coefficients). All I was missing (which is what I alluded to at the end of the paragraph) is the Pade approximation to $\sqrt{1+x}$ that you got from Beukers. – Victor Miller Apr 3 '13 at 13:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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