Comments on Stan Wagon's Powers of Two Problem.
Charlotte Darroch, Sep 22 2022

I watched the latest Numberphile video about the powers of two problem and subsequently read Smith's ingenious 4-cycle argument for bounding a(n). I suspected that perhaps longer even-length cycles might also be excluded. However, I was quite mistaken and found infinitely many examples of 6-cycles where each adjacent pair is a power of two. So I describe it here, along with a couple of other thoughts about the problem. I'm not sure these thoughts actually lead to anything though.

Let the 6-cycle be t1, ..., t6 and let t3 = (t1-t2)/2, t4 = (t1+3t2)/2, t5 = -t2 and t6 = t1+2t2. Then if b1 = t1+t2, b2 = t2+t3, ..., b5 = t5+t6 and b6 = t6+t1, then we have b1 = b3 = b5 = 2b2 = 2b4 = b6/2.

Then provided t1 and t2 have the same parity, sum to a power of 2, t2 =/= 0 and t1 is not in {-5t2, -3t2, -t2, t2, 3t2, 5t2}, then all of the b terms are powers of two and all the t terms are distinct.

I thought it was interesting that there's so much more freedom on the 6-cycle. I also showed that if a 6-cycle has b1, b3 and b5 distinct, then it either has a 4-cycle (which of course is impossible), or it has b1 = b4, b2 = b5, b3 = b6, i.e. opposite edges are equal.

I wonder if there are further forbidden subgraphs relevant to this problem, or if the graphs in the problem have a forbidden subgraph characterisation. Isn't the set of possible graphs closed under taking subgraphs, and therefore under taking induced subgraphs? Doesn't this imply a (possibly infinite) set of excluded induced subgraphs completely characterising the set of possible graphs? Even if so, this is less useful than a minor-closed family.

Kind regards,
Charlotte Darroch