Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Statement and standing
Put . There exist one infinite set and constants and such that
and, for every real ,
A diagonal representation is counted once. The original author-recorded argument received an independent whole-argument refutation-failed review, followed by a PASS from a distinct contract grader. These records concern the exact reviewed subject.
This native text is an author-prepared retention of that proof. The review and grade do not allocate a claim identity, confer a numerical tier, or assert native formal verification. Their source-reading and historical-attribution limits remain in force. In particular, the reviewer did not authenticate the author's Cilleruelo attribution, L2 standing, or historical reading assertions.
The result improves the explicit loss in the L4 statement, whose loss is . It does not improve the exponent , assert a current public record or priority, or resolve the square-root lower-density question in Erdős Problem 158. L4's statement, proof and historical standing are not amended here.
The construction follows the shifted discrete-logarithm method of Cilleruelo, Infinite Sidon sequences, arXiv:1209.0326v2, 15 May 2013, and the capacity-two collision-plane argument recorded in native L4. The changed ingredient is the growth of the auxiliary-prime sizes. The essential arithmetic and selection deductions are supplied below; the L4 density theorem is not being applied to a schedule outside its statement.
All unspecified logarithms in the proof have base two. Natural logarithms appear as . Implied constants are independent of the lower shell, the auxiliary-prime outcome, and the eventual real cutoff. They may depend on the fixed number .
Auxiliary primes and deterministic scales
For define
The integers strictly increase. For example, the real function increases by more than one when an integer is increased by one. Its ceiling therefore increases by at least one. Let be independent and uniform over the finite set of primes
Bertrand's postulate makes every such set nonempty. The intervals in (2) are disjoint even when successive exponents differ by one, so all selected primes are distinct. Define
For every outcome,
The following growth estimates will control every error term:
For the first estimate, the upper bound follows by replacing every by in the summands. The last summands give the lower bound, since each is at least . The remaining assertions follow directly; in particular .
The prime number theorem, specialized to , gives , uniformly after enlarging a constant to include the finitely many small . Unique factorization and the disjoint intervals recover the entire tuple from its product. Consequently, for every integer ,
The last bound uses . It holds with the same constant after conditioning on any prescribed values of : these coordinates are independent of the first . A countable product of the finite probability spaces provides one probability space for all ; only finite cylinder conditioning is used below.
Source shells and digital properties
Choose one deterministic sufficiently large for all eventual uniform comparisons below, and in particular for whenever . Define disjoint source shells and their upper endpoints by
Each such source prime exceeds every with . The prime number theorem gives
Indeed, the discarded lower interval has at most integers, and . Thus no short-interval prime theorem is needed. The shells are nonempty eventually.
Fix a primitive root modulo each selected prime . For , let , for , be the unique integer in with , and put for . Set
Cyclicity of the nonzero prime-field residues supplies the digit, since the interval contains exactly consecutive exponent classes. Mixed-radix uniqueness follows by reduction modulo the first radix, subtraction, division, and induction. It gives . The last nonzero digit identifies the shell. Inside one shell, equal labels imply , and , proving that is injective.
Every sum of two labels has no carries. If its shell indices are , its digits lie in the disjoint ranges
Thus every representation of a given integer uses the same unordered shell pair. For a same-shell equality, exponentiating each digit gives equality of prime products modulo . Both products are at most because . They are equal as integers, so unique factorization identifies the unordered pair, including diagonals.
For unequal shells write
Equal sums imply equality under the map
The upper digits give the first congruence; the lower digits give the second. The converse is not asserted. Both projections within a fiber are injective: fix one coordinate, cancel it modulo , and use ; or combine congruences modulo and and use . Cancellations are valid because the source primes exceed all auxiliary prime factors concerned.
Two distinct points of a fiber have a nonzero upper difference divisible by and a nonzero product difference divisible by . The latter products differ by unique factorization and disjointness of source shells. Together with (3), these facts force
Let count three-element subsets of a fiber, summed over all fibers. It vanishes outside (11). Order a triple's upper coordinates as , and call their corresponding distinct lower coordinates . There are unique integers with
Here are positive with , and are nonzero and distinct. Both signs of must be counted.
Fixed-modulus estimate in the lower part of the band
For this section put
Then and . Elimination in (12) gives
for an integer with ; coprimality of justifies the integer . When , all of
hold uniformly for sufficiently large . The logarithms of the four ratios to be made less than one are bounded above, respectively, by
The first three have fixed negative multiples of plus . The fourth is at most , with negative coefficient. If , the first equation in (13), reduced modulo , would imply , contradicting (14). Thus .
Fix and let . If , put and . Direct elimination and completion of a product give
For clarity, (13) first yields ; substitute and and complete the two factors. The integer is nonzero: otherwise the braces vanish, whence , contrary to .
Every factor in has absolute value at most for a fixed constant. The elementary uniform divisor bound
bounds its ordered signed factor pairs. To obtain (17), set for . In the prime factorization of , primes at most contribute at most to . For larger primes, the sum of exponents is at most , and . Both contributions are .
Each factor pair in (16) determines , then , then by the second equation of (13), and finally by (12). Every division has a nonzero denominator. Invalid reconstructions can be discarded.
If , write , with and . Then , for a nonzero integer . Set . Equations (12) give
By (14), and , so the distinct primes both divide . But , forcing and hence , a contradiction.
A triple forces . There are at most , , and possibilities for the gap pair, signed offset pair, and . Combining these with (17) proves, uniformly when ,
The inequality also holds when there are no triples. Its main exponent comes from and .
Integer points on a collision plane
We need a lattice estimate with its line term retained. If is primitive and nonzero, the lattice has rank two and covolume . If is its shortest nonzero vector length, then
Here is an elementary justification. If , then and the assertion about rank and covolume is immediate. Otherwise let , choose , and choose . The vectors
have determinant one, and the first two have cross product . They give the stated lattice basis and covolume. A shortest vector has coprime coordinates in any lattice basis, and thus extends to a basis. Reduce the other basis vector modulo it until the parallel component has absolute value at most . Its perpendicular height then satisfies and . Counting lattice lines in a ball of radius , and points per line, gives , which is (19).
For fixed upper primes and offsets in (12), elimination of gives
Let and let . Put . If , the number of integer points of (20) in is at most
To prove this, first divide by their positive greatest common divisor. The normal vector is primitive: a common prime different from all would divide both reduced offsets, and a prime equal to one of the cannot divide the two other, nonzero, smaller coefficients. Its norm is at least .
For a vector in its kernel, use , to write the equation as
If , coprimality of forces both braces to vanish. The vector is then a nonzero integer multiple of unless . Thus every nonzero kernel vector has norm at least . Substitute this and the determinant bound into (19) to obtain (21).
Averaging over the lower modulus
Fix in (11), and condition on , fixing . In this section use the deterministic bounds
Every actual triple has and , with . These ranges are fixed under the conditioning. If or there is no triple. For any fixed actual upper-prime triple, offset pair, and lower integer point in (20), the only possible value of is
If it is not an allowed positive integer product, its probability is zero. Otherwise (5) bounds its conditional probability by . Summing the point indicators is legitimate even when different points yield the same product .
The small-coefficient hypothesis of (21) is uniform throughout (11), because the offsets and their difference have magnitude less than , and
The right side is at most a fixed negative multiple of plus , by (11) and (4). Therefore once the deterministic threshold is large enough.
There are at most first upper primes and at most gap pairs. We use
Indeed, , so summing in gives at most , and . Over the signed offset pairs, the sums of are at most , respectively. The latter intentionally uses only ; a sharper noncritical estimate is unnecessary.
Summing (21), using (5), (24), and , gives
Both and the source endpoint factor are absorbed into the error . The four main exponent coefficients, in units of , are
The first minus the fourth is , since has . The third minus the fourth is . Define
The bound (25) is uniform in the conditioned outcome. Averaging its finite conditional expectations proves
Critical exponent, summability, and simultaneous selection
Put . For the sign, follows from , whose square is an exact strict comparison. On , the coefficient in (18) is at most
Its divisor error is , uniformly in , so this whole range has an eventual fixed exponential saving, for instance .
On , the function decreases and is at most . The function increases, and throughout the strict band (11) it satisfies
The last equality uses . No favorable spacing between and the boundary is assumed. In particular (28) covers shell pairs arbitrarily close to the critical boundary, with the same constant in the error of (27).
Write . There are fewer than terms, so (18) and (27) give one deterministic constant such that
for all sufficiently large . Markov's inequality implies
The probabilities are summable. The first Borel--Cantelli lemma, or just the union bound on all failures after followed by , shows that almost every infinite auxiliary-prime sequence has only finitely many exceptions. Fix one such sequence. Since ,
holds for all sufficiently large in this one sequence. The threshold here may depend on the chosen outcome; the constants preceding the probabilistic choice do not. No event independence is needed in this step.
For each , form a simple three-uniform hypergraph on the full shell . An upper three-set is an edge if it occurs in a fiber triple with any full lower shell , . Its edge count satisfies . This definition is made before choosing any shell subsets.
A three-uniform hypergraph on vertices with edges has an independent subset of size
If , retain everything. Otherwise retain each vertex with probability . Expected retained vertices minus retained edges equal . Delete one vertex from every remaining edge in an outcome attaining at least that expectation. If the difference is at least ; otherwise it is . This proves (31).
Equations (7), (30), and (31) supply independent subsets with
for all sufficiently large , with one constant for the fixed outcome. Choose, for example, the lexicographically first maximum independent subset of each finite shell. Choose the empty subset in the finitely many exceptional earlier shells, and put
This specifies one set. If an integer had three distinct unordered representations using it, (9) would identify a common shell pair. The same-shell uniqueness already proved excludes that case, including every diagonal. Otherwise (10) puts the representations in one fiber with three distinct upper primes. Those primes form an edge inside , a contradiction. Using full lower shells in the edge definition makes all choices simultaneous; later shell choices introduce no missed obstruction. Hence for every integer .
Every real cutoff and the sharper loss
For sufficiently large real , let be the unique index with and put . Every selected label from shell lies below , so injectivity and (32) give
Both sides of the physical cutoff comparison are explicit:
In particular , and (4) gives . Combining (34) and (35), then enlarging the constant for all sufficiently large , yields
Conversion to natural logarithms gives (1). The selected shell sizes in (32) tend to infinity because , so is infinite. The argument is uniform over every real cutoff, not just the shell endpoints. Since the loss is , this same set also satisfies eventually for each fixed .
External inputs and reading boundary
The standard external inputs are Bertrand's postulate in the form ``every integer m>=1 has a prime m<q<=2m'', cyclicity of the nonzero residue group of a prime field, the prime number theorem , and the countable product of finite probability spaces. Markov and the summable-event argument are used explicitly above. The precise standard-source locators used in L4 are: Erdős (1932), Beweis eines Satzes von Tschebyschef, §5, printed pp. 197-198; Conrad, Cyclicity of (Z/(p))^×, Theorem 2.6, p. 3; Zagier (1997), Newman's Short Proof of the Prime Number Theorem, printed p. 705; and Durrett, Probability: Theory and Examples, version 5 dated 11 January 2019, Theorems 2.1.21, 1.6.4, and 2.3.1. Their theorem interfaces are consumed as standard external results. This note does not claim a fresh visual or whole-proof audit of those sources.
The original author reported reading the full native L4 and L2 statements and proofs, whose recorded standing at that reading was tier 0. The author also reported visually reading the selected Cilleruelo manuscript on pp. 1, 2, and 9 for its representation convention, Theorem 1.2, and independent auxiliary-prime/product-probability mechanism. Its density theorem is background, not a premise of (1). These are retained historical author assertions, not reading claims made by the independent reviewer or by this filing operation. The canonical source index identifies the selected arXiv:1209.0326v2 manuscript, dated 15 May 2013.
No computation, formal verification, or public novelty conclusion is claimed by this argument. Subsequent independent review is recorded separately above, with its exact external-source interfaces, artifact identities, actual reading depth, and distinct grader's scope.