Many whole numbers are a prime plus a power of two, such as 5, 7 and 11. In 1934 Romanoff proved that a positive proportion of all whole numbers arise this way, and numerical studies suggest that the proportion is a little over 0.43. Proved lower bounds are far smaller: the best in the literature was 0.10788, from a method of Elsholtz and Schlage-Puchta. This paper proves that the proportion is at least 0.109406, and, assuming a bound that Johnston and Trudgian deduce from Lichtman's Theorems 1.2 and 1.7, at least 0.117953.
Abstract
Let d be the lower density of the set of integers of the form p + 2a with p prime and a ≥ 1. We prove that d ≥ 0.109406, and, assuming a bound that Johnston and Trudgian deduce from Lichtman’s Theorems 1.2 and 1.7, that d ≥ 0.117953. The best lower bound in the literature was 0.10788, from the method of Elsholtz and Schlage-Puchta. That method splits the integers into residue classes modulo a fixed integer l and bounds, in each class, the number of pairs of representations of the same integer by a sieve bound with the constant 8. We use the modulus l = 3·5·7·11·13·17·31·41·241 and bound the singular series with the prime factors of 2t − 1 for t ≤ 1200, which gives the first bound. The bound of Johnston and Trudgian gives the constant 6.7814 for the total over all classes, but their argument does not give it for a single class. For the second bound we use both constants. A linear program finds the distribution of the pairs over the classes that minimizes the resulting bound for d, and an exact Lagrangian certificate bounds its minimum from below.
Illustration of the residue patterns behind the bounds. Whether n − 2ᵃ is free of the primes 3, 5, 7, 11, 13, 17, 31, 41 and 241 depends only on n modulo their product l = 78187414305 and on a modulo 120, the period of the powers of 2 modulo l. Top: five residue classes k modulo l. Around each circle are the 120 exponents r, starting at the top and running clockwise; the nine rings, from 3 inside to 241 outside, are filled where that prime divides k − 2ʳ, and the yellow dots mark the exponents that are left, those for which no prime factor of l divides k − 2ʳ. From left to right the classes keep 2, 24, 40, 54 and 78 of the 120 exponents. Bottom: the share of all classes modulo l that keep s exponents, for s from 0 to 120, computed exactly from the nine primes: a prime p removes the exponents r ≡ j modulo the order of 2 mod p in the classes with k ≡ 2ʲ mod p, and none in the others. The yellow dots mark the five classes above: the smallest positive s (its bar is too short to see), the quartiles and the 95th percentile. The number of representations n = p + 2ᵃ in a class grows in proportion to the number of exponents it keeps. The paper bounds the pairs of representations class by class and, for the conditional bound, also in total over all classes.
