Potential solution to Sloane's "Powers of 2" problem? Neil Sloane gave a problem in a recent Numberphile video here. It seems like there's a solution. But Sloane said it's unsolved and very hard so maybe not. But I'll try to outline the idea for the solution and I'm hoping to know: would an approach along these lines work?
The problem is to find four distinct integers, $a,b,c,d\in \mathbb{Z}$ such that as many pair-wise sums as possible are powers of two. For instance $a,b,c,d=-1,3,5,11$ gives four such pair-wise sums
$$-1+3=2\quad 3+5=8\quad -1+5=4\quad 5+11=16 $$
out of a possible six (the powers of two themselves don't need to be distinct). Sloane said four sums is the best if $a,b,c,d$ are bounded but that five sums (though highly suspected impossible) was not disproven for the unbounded case.
Here's an approach that would seem to be capable of proving five sums impossible.
Firstly, five sums would imply that some three of $a,b,c,d$ give powers of two for all pair-wise sums (since a graph on 4 elements with 5 distinct edges has at least one 3-clique). Without loss of generality we can suppose
$$a+b=2^p\quad a+c=2^q\quad b+c=2^r$$
for non-negative integers $p,q,r\in\mathbb{N}$. But this also gives us linear expressions for $a,b,$ and $c$ in terms of powers of two:
$$2^p+2^q-2^r=2a\quad 2^p-2^q+2^r=2b\quad -2^p+2^q+2^r=2c$$
And we can divide through by $2$ getting $a,b,$ and $c$ alone
$$a=2^{p-1}+2^{q-1}-2^{r-1}\quad b=2^{p-1}-2^{q-1}+2^{r-1}\quad c=-2^{p-1}+2^{q-1}+2^{r-1}$$
Any distinct choice of $p,q,r$ gives us three of the five desired pair-wise sums. To achieve five, we need $d$ to sum to a power of 2 with two of $a,b,$ and $c$. Without loss of generality, say with $a$ and $b$:
$$a+d=2^{p-1}+2^{q-1}-2^{r-1}+d=2^m$$
$$b+d=2^{p-1}-2^{q-1}+2^{r-1}+d=2^n$$
And rearranging to get $d$ alone, we get an equality of powers of two:
$$d=2^m-2^{p-1}-2^{q-1}+2^{r-1}=2^n-2^{p-1}+2^{q-1}-2^{r-1}$$
Cancelling terms (like $-2^{p-1}$) and rearranging again, we get
$$2^m+2^r=2^n+2^q$$
This, of course, implies that $\{m,r\}=\{n,q\}$. This is probably the jump in logic where this approach fails. The intuition is that we can think of a sum of powers of two like a binary number, with the exponents indicating the indices of the $1$'s in the binary digit expansion of the number. So the aforementioned equation could be read as "we have two equal binary numbers with two $1$'s in each binary digit expansion" -- wouldn't it follow that the $1$'s have to be in the same positions in both such numbers? The analogy fails a bit if $m=r$. But in that case, wouldn't it still be apt to determine the LHS as a binary number with a single $1$ digit? But even in that case $n=q=m=r$ is the only solution and we still have $\{m,r\}=\{n,q\}$.
Anyways, there are two ways to realize $\{m,r\}=\{n,q\}$. Case 1 is that $m=n$ and $r=q$. In this case, $a=b=2^{p-1}$ and thus our $a,b,c,d$ are not distinct. Case 2 is that $m=q$ and $r=n$. In this case $d=-2^{p-1}+2^{q-1}+2^{r-1}=c$ and again our $a,b,c,d$ are not distinct. Thus the assumption that there exist distinct $a,b,c,d\in\mathbb{Z}$ such that five of their pairwise sums are powers of two was incorrect.
Am I missing something? There's no way something Neil Sloane calls "very hard" has a solution this straight-forward right? He did talk about extending the problem to more than four integers; perhaps he meant they don't know the optimal in general?
EDIT: Looks like I wasn't the first to think of this. Someone named T. Ranha suggested the same approach in a comment on the video: "... Bringing 2^B to the other side we get: 2^C+2^D=2^E+2^B. Now lets look at the problem in binary. A power of 2 in binary is a single 1 at some place in the number. The sum of two different powers of 2 are therefore two 1s somewhere in a string of 0s. In the case of equal powers of 2, there is only one 1. In both cases, there is a 1:1 correspondence between the terms and the sums. Therefore we can conclude that B=C or B=D. The first one leads to c=d and the second one leads to a=b. Both are contradictons and therefore the assumption that it is possible, was wrong."
 A: Long story short, this approach works and was not known at the time of filming the video in question. But it has been discovered since along with more powerful techniques.
Sloane's general question (given $n$ distinct integers, how many of their pair-wise sums can be a power of $2$) is largely a graph theory problem; in particular a sub-graph avoidance problem.
To see the connection, imagine the $n$ distinct integers are vertices and two such vertices are connected by an edge if they sum to a power of $2$. The approach I outlined in my question above really amounts to saying that no two $3$-cliques share an edge in such a graph. But as pointed out in Numberphile's follow up post, we can do better. Such a graph cannot contain any loop of four vertices. In other words, such a graph avoids the sub-graph $C_4$.
To prove this, suppose we had such a loop with integers $a,b,c,d$:
$$a+b=2^w\quad b+c = 2^x\quad c+d = 2^y\quad d+a=2^z$$
In such a case, $2^w+2^y=2^x+2^z$. And as deduced in the question statement, this implies $\{w,y\}=\{x,z\}$. WLOG we can suppose $w=x$ and $y=z$. But if this is so, then
$$a-c = (a+b)-(b+c)=2^w-2^x=0$$
and we have that $a=c$ and our integers are not distinct.
This also implies that no two $3$-cliques can share an edge since a $C_4$ sub-graph would exist if so. Accordingly, any two $3$-cliques can share at most one vertex.
And I'll add here (I'm not sure it's been shown elsewhere) that if two $3$-cliques do share a vertex, then they don't share a vertex with any third $3$-clique. In other words, the kinds of graphs in question not only avoid $C_4$ but also avoid the sub-graph formed by daisy-chaining together three $3$-cliques (a sort of three-winged butterfly graph).
As shown in the question statement, if any three integers $a,b,$ and $c$ form a $3$-clique, we can express each integer in terms of the relevant powers of two.
$$a=2^{p-1}+2^{q-1}-2^{r-1}$$
$$b=2^{p-1}-2^{q-1}+2^{r-1}$$
$$c=-2^{p-1}+2^{q-1}+2^{r-1}$$
And suppose now that the clique $\{a,b,c\}$ overlaps a vertex, say $c$, with another clique $\{c,d,e\}$. In this second clique, $c$ will have a different parametrization as a sum of powers of two. WLOG we can suppose:
$$c=-2^{p-1}+2^{q-1}+2^{r-1}=-2^{x-1}+2^{y-1}+2^{z-1}$$
Rearranging a bit and we see that we have two equal sums of powers of $2$:
$$2^x+2^q+2^r=2^p+2^y+2^z$$
There are two possible types of integer solutions here.
Type 1 is that $x,q,r$ are distinct and that $\{x,q,r\}=\{p,y,z\}$. In this case we must have $p=x$ since $p=q$ and $p=r$ make $a,b,$ and $c$ no longer distinct. Thus we have $\{q,r\}=\{y,z\}$ and WLOG we can suppose $q=y$ and $r=z$. But now this means $\{p,q,r\}=\{x,y,z\}$ and our two cliques actually the same clique. Or in otherwords, they don't just overlap one vertex, but all three.
Type 2 is that $x,q,r$ are not distinct. If so, we can't have $q=r$ since this would  $a=b$ are not distinct. So WLOG we can suppose $x=q$ and by similar reasoning on the LHS that $p=y$. The only solution in such a case is to set $z=x+1=q+1$ and $r=p+1=y+1$. Thus we have essentially parametrized in two variables all solutions taking the shape of the butterfly graph. The vertices of the two cliques are
$$\{2^{x-1}-2^{y-1}, 2^{y-1}-2^{x-1}+2^{y}, 2^{x-1}+2^{y-1}\}$$
$$\{2^{y-1}+2^{x-1}, 2^{x-1}-2^{y-1}+2^{x}, 2^{y-1}-2^{x-1}\}$$
where $2^{x-1}+2^{y-1}$ is the shared vertex and the edges are
$$\{y, x, y+1\}\quad\text{and}\quad\{x,y,x+1\}$$
For an example, pick $x=1$ and $y=3$. The vertices created by this choice are $\{-3, 11, 5\}$ and $\{5, -1, 3\}$. And in fact, this exact sub-graph appears in the best-known solution for $n=10$ shown at this timestamp.
After a few sketches of this parametrization in my notebook, it was easy to convince myself that it cannot be overlapped with another such parametrization to create a daisy-chain of three $3$-cliques (we could call such a sub-graph a "three-wing butterfly" maybe? not sure if there's a standard name for it). In a nutshell, this is because all possible overlappings of two of these parametrizations forces a relationship on $x$ and $y$ which in turns forces two edges in a single clique to have the same value. This isn't a problem in itself since the powers of two associated with the edges need not necesarily be distinct. However, two equal edges in the same $3$-clique forces two vertices in the clique to be equal as well.
All in all, if we have a graph with $n$ distinct integers as vertices and edges where two such integers sum to a power of $2$, then such a graph avoids both $C_4$ and the "three-wing butterfly" as sub-graphs. The obvious conjecture here is that this is a sufficient condition. I.e. that any graph avoiding these two sub-graphs can be realized by some choice of distinct integers. I think the smallest unknown case is $n=10$, for which $15$ pair-wise sums (or, equivalently, edges) has been realized but $16$ has not been ruled out as a possible improvement. So a good test for this conjecture would be to see if there are any graphs on $10$ vertices avoiding the two relevant sub-graphs which have $16$ edges. If there aren't, we move on to $11$ vertices. If there are such graphs, then studying them to learn why they can't be realized (or how to realize them if they can be) will likely the fastest way to progress the state of this problem. But I know little about generating graphs so this is as far as I go.
EDIT: The best you can do with $n=10$ distinct integers is $15$ sums. I ended up writing a graph generating program and found that there's only one graph up to isomorphism with 10 vertices, 16 edges, and which avoids both $C_4$ and the "three winged butterfly" as a sub-graphs. The graph is two regular old butterfly sub-graphs (each accounting for 5 of the 10 vertices and 6 of the 16 edges) with 4 edges between the two of them.
It took about 12 cases to check but I managed to show that there's no way to realize this graph as a set of distinct integers with edges corresponding to pair-wise sums that are powers of two. I did this using the parametrization given earlier in this answer for the butterfly subgraph (i.e. two 3-cliques that share a vertex) which, right out of the gate, lets us parametrize all 10 distinct integers using only 4 variables. From there I tried adding in those 4 edges that span between the two butterfly sub-graphs and found that any way you do it forces duplicate values within one or both of the butterfly sub-graphs.
Long-term this approach is way too tedious to make any substantial headway on finding optimal solutions for larger $n$. Probably gonna need some more lemmas/theorems about these kinds of graphs -- or at the very least, some computer algebra software that can quickly check if a given graph can be realized with distinct integers whose edges correspond to pair-wise sums as powers of two.
One approach is to generate a sequence of sub-graphs that must be avoided. The process would be like this: for a given $n$ generate the graphs with as many edges as possible that avoid all such sub-graphs. Then check if any can be realized with distinct integers under the powers of two correspondance. If any can, continue to $n+1$. Otherwise, add those graphs to the list of sub-graphs that must be avoided and check the same family of graphs but having one less edge and repeat. Currently the sequence goes $C_4, B_7, B_{10}, ...$ where $B_7$ is just the three-winged butterfly graph and $B_10$ is the graph mentioned above. A decent graph generating program and a system-of-sums-of-powers-of-two solver could probably knock out up to $n=50$ along these lines.
