Erdős Problem #406

Erdős Problem 406: a complete sparse-exponent bound

Statement and scope

The exact order of two modulo powers of three

More generally, raising $1+c3^t$ to an exponent coprime to $3$ leaves that valuation $t$. Hence $v_3(4^u-1)=1+v_3(u)$. An exponent $v$ with $2^v\equiv1\pmod{3^r}$ must be even, by reduction modulo $3$; writing $v=2u$, the preceding identity shows it must be divisible by $2\cdot3^{r-1}$. That exponent works, proving $2$. Since it equals the number of invertible residues modulo $3^r$, the powers of two traverse every such residue once per period.

Counting permitted low digits

For an integer $X\ge2$, choose $r$ minimally with $q_r>X$. Then $q_r\le3X$, and $0,1,\ldots,X$ occupy distinct exponent residues. Any fully admissible exponent belongs to $E_r$, even when leading zero digits have to be appended. With $\alpha=\log_3 2$, this proves \[ N(X)\le2^{r-1}=(q_r/2)^\alpha \le(3X/2)^\alpha. \tag{3} \] The constant is inessential; the important point is $\alpha<1$. An infinite set can obey $3$, so it cannot be interpreted as a finiteness proof.

The residue sets also admit an exact recursive sieve. Above each residue modulo $q_r$ there are three exponent lifts modulo $q_{r+1}$. Since $2^{q_r}\equiv1+c3^r\pmod{3^{r+1}}$ with $3\nmid c$, those lifts give all three possibilities for the next ternary digit. Exactly two survive, explaining the doubling $|E_{r+1}|=2|E_r|$. A coherent infinite branch describes a compatible system of exponent residues, not necessarily a single nonnegative integer exponent; compactness cannot turn this sieve into infinitely many integer solutions.

The other omitted digits and the carry interpretation

There is an exact binomial reformulation of the main question: \[ 3\nmid\binom{2^{n+1}}{2^n} \quad\Longleftrightarrow\quad 2^n\hbox{ has only ternary digits }0,1. \tag{4} \] Indeed Legendre's formula gives $v_3\binom{2m}{m}=(2s_3(m)-s_3(2m))/2$, which is the number of carries in adding $m$ to itself in base three. No carry occurs precisely when every digit of $m$ is $0$ or $1$; the lowest digit equal to $2$, if present, starts a carry. Put $m=2^n$ to obtain $4$.

Assessment and remaining gap

1) FORMAL RESTATEMENT

For an integer $k\ge 0$, write $2^k$ in base $3$: \[ 2^k=\sum_{j=0}^L d_j 3^j,\quad d_j\in\{0,1,2\},\ d_L\ne 0. \]

Question A. Are there only finitely many $k$ such that all ternary digits satisfy $d_j\in\{0,1\}$? Equivalently, are there only finitely many powers of $2$ that are sums of distinct powers of $3$?

Question B. Are there only finitely many $k$ such that all ternary digits satisfy $d_j\in\{1,2\}$ (i.e. no digit $0$ appears)?

Edge cases. $2^0=1$ has ternary representation $1$, which satisfies both digit restrictions.

2) QUICK LITERATURE/CONTEXT CHECK

I only restate what is in the problem statement.

The statement records: - The only known examples for digits $\{0,1\}$ seem to be $1$, $4$, $256$. - If only digits $\{1,2\}$ are allowed, $2^{15}$ seems to be the largest such power. - Saye computed that $2^n$ contains every ternary digit for $16\le n\le 5.9\times 10^{21}$.

3) ATTACK PLAN

Proof-track: - Translate the digit condition into a Diophantine equation in powers of $2$ and $3$. - Derive simple congruence restrictions.

Disproof-track: - Search for additional solutions computationally for moderate $k$.

Chosen path: give exact equivalence lemmas and confirm computationally up to $k\le 60$.

4) WORK

PHASE 1 — FAST REALITY CHECK (computed)

For $0\le k\le 60$: - The only $k$ for which the ternary digits of $2^k$ are all in $\{0,1\}$ are \[ k\in\{0,2,8\}, \] corresponding to $2^k\in\{1,4,256\}$. - The $k$ for which the ternary digits of $2^k$ are all in $\{1,2\}$ are \[ k\in\{0,1,2,3,4,15\}, \] so the largest such $k$ in this range is $15$ (value $2^{15}=32768$).

Lemma 1 (base-$3$ digit reformulation). For $k\ge 0$, $2^k$ has a ternary expansion using only digits $0$ and $1$ if and only if there exist distinct nonnegative integers $e_1<\cdots<e_t$ such that \[ 2^k=\sum_{i=1}^t 3^{e_i}. \]

Proof. ($\Rightarrow$) If the ternary digits of $2^k$ are in $\{0,1\}$, then \[ 2^k=\sum_{j=0}^L d_j 3^j \] with each $d_j\in\{0,1\}$. Let $\{e_1,\dots,e_t\}=\{j:\ d_j=1\}$. Then the sum is exactly $\sum_{i=1}^t 3^{e_i}$.

($\Leftarrow$) Conversely, if $2^k=\sum_{i=1}^t 3^{e_i}$ with distinct exponents, then in base $3$ this is precisely the expansion with digit $1$ in positions $e_i$ and digit $0$ elsewhere. Uniqueness of base-$3$ expansion ensures all digits are $0$ or $1$. $\square$

Lemma 2 (a necessary congruence condition for digits $\{0,1\}$). If $k\ge 0$ and $2^k$ has ternary digits only in $\{0,1\}$, then: (a) the least significant ternary digit is $1$ (i.e. $2^k\equiv 1\pmod 3$), and (b) $k$ is even.

Proof. If all ternary digits are in $\{0,1\}$, then modulo $3$ the number is congruent to its least significant digit $d_0\in\{0,1\}$. Since $2^k$ is not divisible by $3$, we must have $d_0=1$, i.e. $2^k\equiv 1\pmod 3$.

But $2\equiv -1\pmod 3$, so $2^k\equiv (-1)^k\pmod 3$. Therefore $2^k\equiv 1\pmod 3$ forces $(-1)^k\equiv 1\pmod 3$, i.e. $k$ is even. $\square$

5) VERIFICATION

- Lemma 1 is a direct unpacking of the definition of base-$3$ representation. - Lemma 2 matches the computed solutions: $k=0,2,8$ are all even and have $2^k\equiv 1\pmod 3$.

6) FINAL

UNRESOLVED

(i) Strongest fully proved partial result obtained here. - Exact equivalence between “digits $\{0,1\}$ in base $3$” and “sum of distinct powers of $3$” (Lemma 1). - Necessary condition: any such exponent $k$ must be even (Lemma 2). - Computation up to $k\le 60$ confirms only $k=0,2,8$ for digits $\{0,1\}$ and confirms $k=15$ as the largest solution in that range for digits $\{1,2\}$.

(ii) Exact first gap. Prove finiteness (or exhibit infinitely many) exponents $k$ such that $2^k$ is a sum of distinct powers of $3$.

(iii) Top 3 next moves (concrete targets). 1. Strengthen congruence obstructions by working modulo $3^r$ (which reads off the first $r$ ternary digits) and simultaneously modulo $2^s$. 2. Treat $2^k=\sum 3^{e_i}$ as an $S$-unit equation and attempt to apply explicit bounds on solutions in the $(2,3)$-unit group. 3. Push computation further using meet-in-the-middle for the subset-sum in powers of $3$ (for bounded digit length) to search for larger solutions.

(iv) What a minimal counterexample would likely look like. If infinitely many such $k$ exist, they would likely form a sparse sequence with rapidly growing ternary length and a rigid combinatorial structure of the set of exponents $\{e_i\}$ (since random subset sums of powers of $3$ rarely hit exact powers of $2$).