Erdős Problem #236

Erdős Problem #236 (Round 2)

1) ROUND-2 OBJECTIVE

Path (C): obstruction/gap-closure. Round 1 proved only a first-moment statement, \[ \frac{1}{N}\sum_{n\le N} f(n)\to \frac{1}{\log 2}, \] which implies $f(n)=o(\log n)$ for a density-$1$ set of integers but says nothing about the size of rare exceptional values. The strict next step is to control correlations among the events "$n-2^k$ is prime". I will prove a second-moment bound \[ \sum_{n\le N} f(n)^2 \ll N\log\log N, \] which is substantially stronger than Round 1 and yields a quadratic tail bound for large values of $f(n)$.

2) Round-1 FOUNDATION USED

I use the following Round-1 results without re-proving them.

• Round-1 Lemma 236.1: the trivial pointwise bound $f(n)\ll \log n$.
• Round-1 Lemma 236.2: assuming the prime number theorem, \[ \frac{1}{N}\sum_{n\le N} f(n)\to \frac{1}{\log 2}. \]
• Round-1 Corollary 236.3: for every fixed $\varepsilon>0$, \[ \frac{1}{N}\#\{n\le N:f(n)\ge \varepsilon \log N\}\to 0. \]

3) NEW INSIGHT / TOOL (ROUND-2)

The new structural observation is that the differences between two powers of $2$ factor as \[ 2^j-2^k = 2^k(2^{j-k}-1). \] Thus pair correlations of the translate set $\{n-2^k\}$ reduce to prime-pair counts with differences of the very special form $2^k(2^m-1)$. Combined with the Selberg-sieve prime-pair upper bound and the classical estimate \[ \frac{m}{\phi(m)}\ll \log\log(3m), \] this yields a workable second moment.

4) ATTACK PLAN (ROUND-2)

After Round 1, the exact gap was the lack of any control on exceptional $n$ where many of the numbers $n-2^k$ are prime simultaneously. The claim now to prove is:

Claim 236-R2. Assuming the prime number theorem and the standard Selberg-sieve upper bound for prime pairs, \[ \sum_{n\le N} f(n)^2 \ll N\log\log N. \] Hence for every $\lambda\ge 1$, \[ \#\{n\le N:f(n)\ge \lambda\}\ll \frac{N\log\log N}{\lambda^2}. \]

This overcomes the Round-1 obstacle of having only first-moment information.

5) WORK (ROUND-2)

Let \[ f(n)=\#\{k\ge 0:2^k<n,\ n-2^k\text{ is prime}\}. \] As in Problem #234, I use the standard prime-pair upper bound \[ \Pi(X;h)\ll \frac{h}{\phi(h)}\frac{X}{(\log X)^2} \qquad (h\ge 2), \] uniformly for $X\ge h+2$.

The only extra elementary input is the standard estimate \[ \frac{m}{\phi(m)}\ll \log\log(3m) \qquad (m\ge 1). \]

Theorem 236.2.1. Assume the prime number theorem and the prime-pair upper bound above. Then \[ \sum_{n\le N} f(n)^2 \ll N\log\log N. \]

Proof. Let \[ K:=\left\lfloor \log_2\!\left(\frac{N}{4}\right)\right\rfloor. \] There are at most two powers of $2$ in the interval $(N/4,N]$, so for every $n\le N$, \[ f(n)\le g(n)+2, \] where \[ g(n):=\#\{0\le k\le K: n-2^k\text{ is prime}\}. \] Hence \[ f(n)^2\le 2g(n)^2+8, \] and therefore \[ \sum_{n\le N} f(n)^2 \ll N + \sum_{n\le N} g(n)^2. \] So it remains to bound \[ M(N):=\sum_{n\le N} g(n)^2. \]

Expanding the square gives \[ M(N)=\sum_{0\le j,k\le K} S_{j,k}(N), \] where \[ S_{j,k}(N):=\#\{n\le N: n-2^j\text{ and }n-2^k\text{ are both prime}\}. \]

Diagonal terms.

Off-diagonal terms with one exponent equal to $0$.

Remaining off-diagonal terms.

Corollary 236.2.2 (quadratic tail bound). For every $\lambda\ge 1$, \[ \#\{n\le N:f(n)\ge \lambda\}\ll \frac{N\log\log N}{\lambda^2}. \] In particular, for every fixed $\varepsilon>0$, \[ \frac{1}{N}\#\{n\le N:f(n)\ge (\log\log N)^{1/2+\varepsilon}\}\to 0. \]

Proof. Apply Chebyshev's inequality to Theorem 236.2.1: \[ \lambda^2\#\{n\le N:f(n)\ge \lambda\} \le \sum_{n\le N} f(n)^2 \ll N\log\log N. \] Taking $\lambda=(\log\log N)^{1/2+\varepsilon}$ yields the second statement. $\square$

6) ADVERSARIAL VERIFICATION

• Did I lose control of large exponents $2^k>N/4$? No. There are at most two such exponents, so their total contribution is absorbed in the inequality $f(n)^2\le 2g(n)^2+8$.

• Was the prime-pair theorem used only where $X\asymp N$? Yes. I applied it only after restricting to $j,k\le K$, which ensures $N-2^j\ge 3N/4$.

• What about odd differences? Those occur only when one exponent is $0$. I handled them separately and used the parity obstruction rather than the sieve.

• Could the sum over $m$ be underestimated? No. The combinatorial count of pairs with $j-k=m$ is exactly $K-m$ for $1\le m\le K-1$.

• Does this prove the original pointwise conjecture? No. The second moment still allows a sparse exceptional set of integers with much larger $f(n)$, so the uniform statement $f(n)=o(\log n)$ remains open.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The strict new progress beyond Round 1 is the second-moment theorem \[ \sum_{n\le N} f(n)^2 \ll N\log\log N, \] which implies the tail bound \[ \#\{n\le N:f(n)\ge \lambda\}\ll \frac{N\log\log N}{\lambda^2}. \] This is substantially stronger than the previous first-moment argument and shows that values as large as $(\log\log N)^{1/2+\varepsilon}$ already occur on a density-$0$ set.

The remaining gap is still the genuinely difficult one: excluding a sparse exceptional sequence $n_j$ with $f(n_j)$ as large as a positive proportion of $\log n_j$.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 58%

References

Only references actually used or checked in this round are listed.

1. T. F. Bloom, Erdős Problem #234, erdosproblems.com, accessed 2026-03-07.
2. T. F. Bloom, Erdős Problem #236, erdosproblems.com, accessed 2026-03-07.
3. T. F. Bloom, Erdős Problem #238, erdosproblems.com, accessed 2026-03-07.
4. H. Halberstam and H.-E. Richert, Sieve Methods, Academic Press, 1974.
5. H. L. Montgomery and R. C. Vaughan, Multiplicative Number Theory I: Classical Theory, Cambridge University Press, 2007.

Erdős Problem #236: independent continuation

1) TARGET AND SOURCE AUDIT

All supplied versions considered: 236.tex. The source obtains a second-moment bound, which permits sparse exceptions. I instead examine the pointwise congruence obstruction and its exact scope.

2) WORK

Now let $\ell$ be any odd prime and let $r$ be the multiplicative order of $2$ modulo $\ell$. If $n\bmod\ell$ belongs to the subgroup generated by $2$, there is exactly one exponent class $k\equiv k_0\pmod r$ for which $\ell\mid n-2^k$. Among these exponents at most one can contribute a prime, namely the exponent (if any) satisfying $2^k=n-\ell$. Writing $K=\lfloor\log_2 n\rfloor$, we obtain \[ f(n)\le (1-1/r)(K+1)+2. \] In particular for odd $n$ not divisible by three, $r=2$ gives $f(n)\le\tfrac12\log_2 n+O(1)$.

For several primes these forbidden exponent classes can be combined exactly modulo the least common multiple of their orders. If their union covers a proportion $\theta$ of exponent classes, then $f(n)\le(1-\theta)(K+1)+O(\operatorname{lcm}(r_1,\ldots,r_s)+s)$. This follows by counting complete periods and allowing one exceptional prime equality for each modulus.

3) ADVERSARIAL VERIFICATION

4) FINAL

5) SOURCES CHECKED

6) COMPLETION ESTIMATE

Erdős Problem #236

1. FORMAL RESTATEMENT.

   For an integer $n\ge 1$, define \[ f(n) := \left|\{k\in\mathbb{N}\cup\{0\}: 2^k < n\ \text{and}\ n-2^k\ \text{is prime}\}\right|. \] (Equivalently, $f(n)$ is the number of representations $n=p+2^k$ with $p$ prime and $k\ge 0$.)

   Claim/conjecture. As $n\to\infty$, \[ f(n) = o(\log n), \] meaning: for every $\varepsilon>0$ there exists $n_0(\varepsilon)$ such that $f(n)\le \varepsilon\log n$ for all $n\ge n_0(\varepsilon)$.

2. QUICK LITERATURE/CONTEXT CHECK.

   This is a "prime + power of two" representation-count problem. Heuristics suggest $f(n)$ is typically $\asymp 1$, since there are $\asymp \log n$ possible exponents $k$ and each $n-2^k$ has "probability" $\asymp 1/\log n$ of being prime.

   Known results discussed in the problem literature include (i) lower bounds showing $f(n)$ can be large infinitely often (Erdős obtained $f(n)\gg \log\log n$ infinitely often), and (ii) results of Vaughan bounding the rarity of integers $n$ for which $n-2^k$ is prime for all $2^k<n$.

3. ATTACK PLAN.

   Proof strategies.

   • $P1$ Seek a uniform sieve/large-sieve upper bound for the number of $k$ such that $n-2^k$ is prime; any bound $f(n)\ll \log n/\omega(n)$ with $\omega(n)\to\infty$ would imply the conjecture.
   • $P2$ Control correlations of the set $\{n-2^k\}$ modulo many small primes to show that too many of them must be composite.

   Disproof/construction strategies.

   • $D1$ Try to construct an explicit sequence $n_j$ for which $n_j-2^k$ is prime for $\gg \log n_j$ values of $k$ (this would contradict the conjecture). Any such construction would be extremely strong, akin to producing very long "prime constellations" along the translate of the power-of-two set.

   Best path chosen here. In this write-up, the proof track $P1$--$P2$ stalls at producing a pointwise $o(\log n)$ upper bound, and the disproof track $D1$ would require constructing an explicit $n$ with $\gg \log n$ prime values among the translate $\{n-2^k\}$. Accordingly, I establish rigorous "first-moment" information: the average size of $f(n)$ is bounded (indeed tends to a constant), which implies $f(n)=o(\log n)$ for almost all $n$ but leaves open the required uniform bound for all $n$.

4. WORK.

   Lemma 236.1 (Trivial pointwise bound).

   For all $n\ge 1$, \[ f(n) \le \lfloor \log_2(n-1)\rfloor + 1 \ll \log n. \]
   Proof: If $2^k<n$ then $k\le \lfloor\log_2(n-1)\rfloor$. For each admissible $k$ there is at most one representation $n=(n-2^k)+2^k$, so $f(n)$ is at most the number of such $k$. ∎

   Lemma 236.2 (Average order of $f(n)$).

   Assume the Prime Number Theorem. Then, as $N\to\infty$, \[ \frac{1}{N}\sum_{n\le N} f(n) \to \frac{1}{\log 2}. \]
   Proof: By definition, \[ \sum_{n\le N} f(n) =\sum_{n\le N}\ \sum_{\substack{k\ge 0\\2^k<n}} \mathbf{1}_{\mathbb{P}}(n-2^k), \] where $\mathbf{1}_{\mathbb{P}}(m)$ is $1$ if $m$ is prime and $0$ otherwise. Interchanging the order of summation (all terms are nonnegative and the range is finite) gives \[ \sum_{n\le N} f(n) =\sum_{k\ge 0}\ \sum_{\substack{n\le N\\2^k<n}} \mathbf{1}_{\mathbb{P}}(n-2^k). \] For fixed $k$, make the substitution $p=n-2^k$. Then $p$ runs over primes with $p\le N-2^k$, and the condition $2^k<n$ is equivalent to $p\ge 1$ which is automatic for primes. Thus the inner sum equals $\pi(N-2^k)$, and we obtain the exact identity \[ \sum_{n\le N} f(n)=\sum_{0\le k\le \lfloor\log_2 N\rfloor} \pi(N-2^k). \] Let $K:=\lfloor\log_2 N\rfloor$. For each fixed $k\le K$, we have $N-2^k\asymp N$, and by the Prime Number Theorem, \[ \pi(N-2^k)=\frac{N-2^k}{\log N}+o\!\left(\frac{N}{\log N}\right) \qquad (N\to\infty), \] uniformly for $0\le k\le K$ because $\log(N-2^k)=\log N+O(1)$ on this range. Summing over $k$ yields \[ \sum_{n\le N} f(n) =\frac{1}{\log N}\sum_{k=0}^{K}(N-2^k) +o\!\left(\frac{KN}{\log N}\right). \] Compute the finite geometric sum: \[ \sum_{k=0}^{K}(N-2^k)=(K+1)N-(2^{K+1}-1)=(K+1)N+O(N), \] since $2^{K}\le N<2^{K+1}$ implies $2^{K+1}=O(N)$. Also, $K=(\log N)/(\log 2)+O(1)$, hence \[ \frac{1}{\log N}\sum_{k=0}^{K}(N-2^k)=\frac{(K+1)N}{\log N}+O\!\left(\frac{N}{\log N}\right)=\frac{N}{\log 2}+o(N). \] Finally, the error term satisfies \[ \frac{KN}{\log N}=\left(\frac{\log N}{\log 2}+O(1)\right)\frac{N}{\log N}=\frac{N}{\log 2}+O\!\left(\frac{N}{\log N}\right)=O(N), \] so multiplying by the little-$o(1)$ gives $o(N)$. Altogether, \[ \sum_{n\le N} f(n)=\frac{N}{\log 2}+o(N). \] Dividing by $N$ gives the claimed limit. ∎

   Corollary 236.3 (A density-one version of the conjecture).

   Assume Lemma 236.2. For any fixed $A>0$, \[ \left|\{n\le N: f(n)\ge A\log N\}\right| \ll \frac{N}{A\log N}. \] In particular, the set of $n$ for which $f(n)\ge A\log n$ has natural density $0$.
   Proof: For each $N$, \[ \sum_{n\le N} f(n) \ge \sum_{\substack{n\le N\\ f(n)\ge A\log N}} f(n) \ge A\log N\cdot \left|\{n\le N: f(n)\ge A\log N\}\right|. \] Rearrange and insert Lemma 236.2, which gives $\sum_{n\le N} f(n)\ll N$. ∎

   What this does not give. Corollary 236.3 is an "almost all $n$" statement. The conjecture asks for the stronger pointwise bound $f(n)=o(\log n)$ holding for every sufficiently large $n$, and the above averaging argument does not rule out a sparse exceptional sequence $n_j$ with $f(n_j)$ comparable to $\log n_j$.

5. VERIFICATION.
   • Quantifiers. Lemma 236.2 proves a limit for the average as $N\to\infty$ (not a pointwise estimate). All steps are finite sums; the only analytic input is PNT.
   • Edge cases. The definition allows $k=0$ (so $2^k=1$); also $p=2$ is allowed.
   • Uniformity in $k$. For $0\le k\le \log_2 N$, we indeed have $\log(N-2^k)=\log N+O(1)$, so PNT can be applied uniformly at the scale needed for an $o(N)$ aggregate error.

6. FINAL.

   UNRESOLVED.

   • (i) Strongest fully proved partial result obtained here. Assuming PNT, $\frac1N\sum_{n\le N} f(n)\to 1/\log 2$, hence $f(n)=o(\log n)$ for a density-one subset of integers $n$.
   • (ii) First gap. No argument here gives a uniform-in-$n$ improvement over the trivial bound $f(n)\ll \log n$; in particular it does not preclude a sparse exceptional sequence $n_j$ with $f(n_j)\asymp \log n_j$.
   • (iii) Top 3 next moves.
     • Develop a large-sieve/Selberg-sieve upper bound tailored to the set $\{n-2^k\}$ that holds uniformly in $n$.
     • Try to bound higher moments $\sum_{n\le N} f(n)^m$ sharply enough to force a global maximum bound on $f(n)$.
     • Explore whether results on primes in arithmetic progressions to moduli related to orders of $2$ can force many of the values $n-2^k$ to be composite.
   • (iv) What a minimal counterexample would likely look like. An explicit sequence $n_j\to\infty$ and a fixed $\delta>0$ with $f(n_j)\ge \delta\log n_j$ for all $j$, i.e. unusually many primes among the translate $\{n_j-2^k\}$.

7. COMPLETION ESTIMATE (MANDATORY).
   COMPLETION: 40%.