4
$\begingroup$

Numberphile Youtube channel just made a video telling us about an open question regarding natural numbers and the powers of two.

In a nutshell, it states that there are no 4 integers whose sum of each two pairs is a power of two.

Let's start with a simpler example with 3 such numbers:

$-1,\ 3\ $ and $5$.

$$-1 + 3 = 2,\ {-1} + 5 = 4 = 2^{2},\ 3+5=8=2^{3}$$ While it's easy to find examples with 3 numbers, finding examples with 4 numbers is not so easy.

In the video, Neil Sloane states that it's an open question, and the best solution known so far has 4 pairs. I thought it looks like a fun problem to play around with so I've written it in formal math:

Let $x,\ y,\ z,\ q \in \mathbb{Z}$ for the sake of nontriviality assume they are different. And right $a,\ b,\ c,\ d,\ e,\ f \in \mathbb{N}$ some given constants.

Well, we have the following equation system:

$$ x+y=2^a\ [1] $$ $$ x+z=2^b\ [2] $$ $$ x+q=2^c\ [3] $$ $$ y+z=2^d\ [4] $$ $$ y+q=2^e\ [5]$$ $$ z+q=2^f\ [6] $$

After solving the first 4 equations we get:

$$x = 2^{a-1} + 2^{b-1} - 2^{d-1}\ [7]$$ $$y = 2^{a-1} + 2^{d-1} - 2^{b-1}\ [8]$$ $$z = 2^{b-1} + 2^{d-1} - 2^{a-1}\ [9]$$ $$q = 2^c - 2^{a-1} - 2^{b-1} + 2^{d-1}\ [10]$$

All nice and dandy. Let's continue with the last 2 equations. Replace y, z, and q with their other forms and get the following equations:

$$2^c+2^d-2^b = 2^e\ [11]$$ $$2^c+2^d-2^a = 2^f\ [12]$$

I conjectured that these equations have no nontrivial natural solutions. So I asked it here on StackExchange and concluded it has none, just as suspected.

This means that the equations $[11]$ and $[12]$ have no valid solutions, and thus the (problem or) "square" with 4 integers cannot be completed.

Q.E.D.

But it seems too easy to be a complete and correct proof. I made some mistakes and it's not valid. I had fun playing around with it. I am curious to know where the mistakes are and why it's not valid.

Note that this proof can be generalized to any number of variables. The only exception where it doesn't work is for 2 variables ($x+y=2^a$ it works since there are infinitely many solutions), and for 3 variables, where the number of equations is equal to the number of variables.

$\endgroup$
7
  • 2
    $\begingroup$ If I understand your post correctly, this was noted at the end of the video itself, see numberphile.com/stop-press $\endgroup$
    – Arthur
    Commented Sep 25, 2022 at 9:29
  • $\begingroup$ @Arthur Thanks, but is my proof right? Does it have any mistakes? $\endgroup$ Commented Sep 25, 2022 at 9:42
  • 1
    $\begingroup$ The solutions only for those equations are $\{c,d\} = \{e,b\} = \{a.f\}$, and there's a nice graphical proof, that you can't get distinct $\{x,y,z,q\}$ when those hold. So, baring any error in the computations (which I haven't fully checked), the proof seems correct. $\endgroup$ Commented Sep 25, 2022 at 11:21
  • 2
    $\begingroup$ It looks correct, actually all you need is $[4]-[1]+[3]$ to get $z+q=2^d-2^a+2^c$. And since $z+q=2^f$ you get $2^d+2^c=2^a+2^f$. Then either $f=d$ and $f=c$ and both lead to contradiction with the original numbers being distinct. I am honestly not sure why the original video claims this problem is open/impossible... $\endgroup$
    – Sil
    Commented Sep 25, 2022 at 13:18
  • 1
    $\begingroup$ I believe there's a misunderstanding in what the original unsolved problem is. In the video he shows we can make 4 powers of 2, and this is the best known solution we can do. Getting all 6 pairs to be powers of 2 is impossible. The question is, can we do better? Is it possible to get 5 powers of 2? That would mean writing the equations out with one of the 6 equations not equal to a power of 2. $\endgroup$
    – Merosity
    Commented Sep 25, 2022 at 19:00

2 Answers 2

3
$\begingroup$

It seems correct, however if you want to strip out unnecessary parts you can just evaluate $[4]-[1]+[3]$ to get $z+q=2^d-2^a+2^c$. Since $z+q=2^f$, you get $2^d+2^c=2^a+2^f$ and as you already noticed, then either $d=a$ or $d=f$. That means $y+z=2^d=2^a=x+y$ and $z=x$ (impossible), or $y+z=2^d=2^f=z+q$ and $y=q$ (again impossible).

This proves it is impossible to have all six pairs to be a powers of two. But, if you look close enough, you might notice we haven't used all equations (for example $[5]$ wasn't used at any point), so this is actually also proof for impossibility of five pairs.

Anyway as also pointed out in comments, after the video has been recorded there was a progress on the problem (including solution of the four numbers case) (https://www.numberphile.com/stop-press). It's probably not surprise that the proof uses the same idea as above.

$\endgroup$
0
1
$\begingroup$

The two final equations can be deduced directly by the compatibility conditions of linear systems $$\det\begin{vmatrix}1&1&0&0&2^a\\1&0&1&0&2^b\\1&0&0&1&2^c\\0&1&1&0&2^d\\1&1&0&1&2^e\end{vmatrix}=2(2^b-2^c-2^d+2^e)=0$$ and similarly with $$\det\begin{vmatrix}1&1&0&0&2^a\\1&0&1&0&2^b\\1&0&0&1&2^c\\0&1&1&0&2^d\\0&0&1&1&2^f\end{vmatrix}=2(2^a-2^c-2^d+2^f)=0$$ from which $$2^c+2^d=2^b+2^e=2^a+2^f$$ Taking for example,$$2^b+2^e=2^a+2^f$$ this is possible only when the minimum exponents in both sides are equal because if not we would have by division the false equality $odd=even$ but this implies the equality of the other exponents.

We are done.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .