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

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?

• I took the liberty of clarifying the terminology, as both 0 and 1 are considered digits, leading to confusion (at least for me). Perhaps also update the title? – Per Alexandersson Aug 9 '14 at 8:39
• @PerAlexandersson: Thanks. I think your edit in the text makes it clear enough. Alternatively I could have just said "sum of digits." – Vesselin Dimitrov Aug 9 '14 at 8:50
• A similar question is here :mathoverflow.net/questions/172706/primes-dividing-2a2b-1 – Konstantinos Gaitanas Aug 9 '14 at 15:11
• Not an answer to your question, but Skalba has shown that if the order of 2 mod p exceeds $p^{4/5}$, then p divides some number of the form $2^a + 2^b+1$. We don't know that Skalba's criterion holds for a full density of primes of $p$, but we expect it to do so (e.g., that follows from GRH). He also shows that if $2^m-1$ has fewer than $\log{m}/\log{3}$ prime divisors (counted with multiplicity), then there is a prime dividing $2^m-1$ not dividing any number of the form $2^a+2^b+1$. See: Skałba, Mariusz, Two conjectures on primes dividing $2^a+2^b+1$, Elem. Math. 59 (2004), no. 4, 171–173. – so-called friend Don Aug 10 '14 at 5:23
• @so-calledfriendDon: Thank you! And Skalba's result follows immediately from the Weil bound for the Fermat curve. (Also, it is true with any exponent $>3/4$.) So we known under GRH that indeed a full density of the primes divide such a number; and the question is whether this is strong enough to expect a positive density of integers to have the same property. – Vesselin Dimitrov Aug 10 '14 at 7:47

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$.

• Thank you for your answer, but please note that that question I asked was whether the density of such $a$ [dividing a number with bounded digit sum], was positive, or zero. It is indeed obvious that this density cannot be $1$, and I had also noted, in the text of the question, the observation you make in your first paragraph. – Vesselin Dimitrov Aug 12 '14 at 18:05
• The first half of my answer didn't make much sense. I deleted it and expanded the second half. – Jan-Christoph Schlage-Puchta Aug 17 '14 at 9:56
• Very nice, thank you very much! Do you know if (for every $\epsilon > 0$) there should be a positive density of integers all of whose prime factors satisfy $\mathrm{ord}_p^{\times}{2} > p^{1-\epsilon}$? If this is true for some $\epsilon < 1/4$, then the argument with Weil's bound for the Fermat curve will show that also a positive density of the integers have a multiple with digit sum $3$; this is because all mod $p$ points on the Fermat curve of exponent $(p-1)/r$ lift to $p$-adic points. Or is almost every $n$ divisible by some prime for which $2$ has order $< p^{1-\epsilon}$? – Vesselin Dimitrov Aug 18 '14 at 18:53
• As far as I know it is an unsolved problem whether there exist infinitely many primes with $\mathrm{ord}^\times_p(2)$ significantly bigger than $\sqrt{p}$. Also glueing together different prime factors is more difficult than usual: If $p, q$ are prime numbers with $(p-1, q-1)$ large, then solutions of $2^{e_1}+2^{e_2}+2^{e_3}\equiv0\pmod{p}$ and $\pmod{q}$ might exist, while a solution $\pmod{pq}$ need not exist. As far as I know this incompatibility of powers of 2 was first exploited by Erd\H os and van der Corput n their work on integers of the form $p+2^a$. – Jan-Christoph Schlage-Puchta Aug 20 '14 at 10:53
• Thank you! I hadn't taken into account this incompatibility for powers of $2$ mod distinct prime powers. – Vesselin Dimitrov Aug 20 '14 at 13:57