How many integers divide a number that involves just three non-zero digits?

Question

Just to be concrete, consider the digits to be binary. Hasse showed that among all the primes, only a fraction of $17/24 < 1$ divide a number of the form $2^n+1$. As a result, the integers that divide a number with just two non-zero digits have zero density.

On the other hand, since $A + A = \mathbb{F}_p$ for a typical set $A \subset \mathbb{F}_p$ of cardinality, say, $> p/\log{p}$ (and much lower than that), and because under GRH and with probability $1$ there are at least as many powers of $2$ mod $p$, we expect a full density of the primes to divide a number of the form $2^m+2^n+1$. [Added: As shown by Skalba in the reference provided by "so-called friend Don," we can actually prove that this is true for all primes $p \gg_{\epsilon} 0$ having $r := \mathrm{ord}_p^{\times}2 > p^{\frac{3}{4}+\epsilon}$: consider Weil's bound for the Fermat curve of degree $(p-1)/r$. This applies also to the linked question. ]

So it would seem legitimate to ask if the probability might be positive for a random integer to have a multple composed of only three non-zero digits. Note that $2^k-1$ does not have this property for $k > 3$ (all its multiples have digit sum exceding $ck$), and this family already furnishes an infinite set of pairwise co-prime integers without the property.

Yet I thought it would be hard to believe that a random integer, with positive probability, will have a multiple with bounded digit sum. Is there a (better) heuristic for the expected number up to a given bound $X$ of the positive integers having a multiple of the form $2^m+2^n+1$? On the opposite extreme, wouldn't most $N$ require, for all their multiples, as many as $(1+o(1))\frac{\log{N}}{2\log{2}}$ binary ones?

Answer 1

For an integer $n$, call a prime divisor $p$ good, if the multiplicative order of $2$ modulo $p$ exceeds $p^{2/5}$, $p^2\nmid n$, and $(p-1, \varphi(n/p))<p^{1/5}$. If $p$ is a good prime divisor of $n$, then the multiplicative order of $2^{\varphi(n/p)}$ is $>p^{1/5}$, by the sum-product results of Bourgain there exists some $k$, such that for any $a$ there exist integers $e_{1,p}, \ldots, e_{k,p}$, such that $2^{e_{1,p}\varphi(n/p)}+\dots+2^{e_{k,p}\varphi(n/p)}\equiv a\pmod{p}$. Put $e_i=\sum_p e_{i,p}$, the sum taken over all good prime divisors of $n$. Then $e_i\equiv e_{i,p}\pmod{p-1}$ for all good $p$, thus $2^{e_1}+\dots+2^{e_k}\equiv a\pmod{\prod p}$. If $p$ is bad, then $2^{e_i}\equiv 1\pmod{p}$. We conclude that for a certain fixed $k$ the $k$-fold sum of the multiplicative subgroup generated by 2 contains a complete coset of the subgroup of $(\mathbb{Z}/n\mathbb{Z}, +)$ which is isomorphic to $(\mathbb{Z}/P\mathbb{Z}, +)$, where $P$ is the product of good prime divisors of $n$.

Next we give an upper bound for the average product of bad prime divisors. Since the number of primes such that 2 has small order is small, and almost all integers are almost squarefree, the only relevant part is the condition on $(p-1, \varphi(n/p))$. For a prime $p$ the number of $n\leq x$ such that $n$ has $<2\log\log x$ prime divisors and $p$ is a bad prime divisor of $n$ is at most $$ \underset{d>p^{1/(10\log\log x)}}{\sum_{d|p-1}}\underset{p\neq q}{\sum_{d|q-1}}\#\{n\leq x: pq|n\} \ll \underset{d>p^{1/(10\log\log x)}}{\sum_{d|p-1}} \frac{x\log\log x}{pd^{1-\epsilon}} \ll \frac{xd(p-1)\log\log x}{p^{1+1/(12\log\log x)}} $$ If $p>e^{40(\log\log x)(\log\log\log x)}$, this becomes $\ll\frac{xd(p-1)}{p\log^3 p}$. The sum over $p$ converges, hence we find that almost all $n\leq x$ have no bad prime divisor $p>e^{40(\log\log x)(\log\log\log x)}$.

Disregarding a set of density 0, the average logarithm of the product of the bad prime divisors of $n$ is at most the average logarithm of the product of the small prime disivors, which is $$ \ll \sum_{p\leq e^{40(\log\log x)(\log\log\log x)}} \frac{\log p}{p} \ll \log\log x\log\log\log x $$

We conclude that there is a constant $k$, such that for almost all $n$ have a divisor $d<(\log\log n)^2$, such that the $k$-fold sum of the subgroup generated by 2 covers modulo $n$ the arithmetic progression $k\pmod{d}$. For such $n$ every integer in the interval $[1, d]$ can be written as the sum of $\log d\ll\log\log\log n$ powers of 2, hence for almost all $n$ all residue classes modulo $n$ can be written as the sum of $\ll\log\log\log n$ powers of 2. In particular almost all $n$ divide some number with sum of digits $\ll\log\log\log n$.