Erdős Problem #1136

Erdős Problem 1136: avoiding sums that are powers of two

Statement and answer.

There is a set of positive integers of density $1/2$ for which no sum of two members, equal members allowed, is a power of two. Moreover no such set has lower density greater than $1/2$. The following gives an elementary reconstruction of the known answer recorded at https://www.erdosproblems.com/1136, attributed there to Müller.

Construction.

Take \[ A=\{2^i u:i\geq0,\ u\equiv3\pmod4,\ u>0\}. \] If $a=2^iu,b=2^jv$ lie in $A$, with $u,v\equiv3\pmod4$, and $i<j$, then \[ a+b=2^i(u+2^{j-i}v). \] Its odd part is the odd integer $u+2^{j-i}v\geq3$, so it is not a power of two. The case $j<i$ is symmetric. If $i=j$, then $u+v\equiv2\pmod4$ and $u+v\geq6$. Its odd part is again at least $3$, so this case is also excluded, including $a=b$.

For each fixed $i$, the members of $A$ with exact 2-adic valuation $i$ form the residue class $3\cdot2^i\pmod{2^{i+2}}$, of density $2^{-i-2}$. The union over $i<K$ has density $\sum_{i<K}2^{-i-2}$. All remaining members are divisible by $2^K$, so their upper density is at most $2^{-K}$. Letting $K\to\infty$ proves \[ d(A)=\sum_{i\geq0}2^{-i-2}=\frac12. \]

Optimality.

For any set $B$ with the required avoidance property, pair the integers of $[1,2^k-1]$ by $t\leftrightarrow2^k-t$. At most one member of each two-element pair can lie in $B$, and the fixed point $2^{k-1}$ cannot lie in $B$, since repeated summands are allowed. Thus \[ |B\cap[1,2^k-1]|\leq2^{k-1}-1. \] Taking this subsequence in the definition of lower density gives $\underline d(B)\leq1/2$. If the convention instead requires distinct summands, the fixed point may be included, changing the bound by only one and leaving the density conclusion unchanged.

Completion estimate.

The construction and sharp lower-density bound are both proved without external theorems. COMPLETION: 100%