This note extends the divisor-sum collision argument to inputs whose two largest primes leave a small cofactor. The full conjecture remains open. Work is tracked in issue #47.
Counting a bilinear congruence in a box
For positive integers with , and any integer , write
Let be the number of residue pairs satisfying . Take two intervals containing and consecutive integers, respectively. For any coprime to , restrict to one residue class each modulo . Let be the resulting numbers of choices in the two intervals. The number of pairs in the restricted box with is
This follows from completion and the Weil bound for Kloosterman sums, as used for modular hyperbolas by Shparlinski, §3.1. The factors involving gcds handle nonunit coefficients and nonunit right-hand sides.
Write and define
We first bound these sums for prime power moduli. The Chinese remainder theorem multiplies the bounds, with unit rescalings of the two frequencies that preserve the gcds.
For the elementary product congruence put . Partition this sum by . Then , where , and with a unit modulo . The congruence fixes modulo and summing over its lifts gives zero unless . If , this part of the sum is times the Kloosterman sum modulo with frequencies . Because , we have
The Weil bound applied separately to these parts gives . For , the Kloosterman sums become Ramanujan sums, each of absolute value at most . This gives .
Now take a prime power . If , the affine change , transforms into a product-congruence sum modulo with unit frequency rescalings. If , then is a unit at because . For , a trivial bound suffices, since each gives a unique . For , use the same change of variables modulo . The variables range over , and the condition becomes . The additive projections for the two restrictions express as an average of over lifts of the frequencies modulo , up to factors of modulus one and a unit rescaling by the inverse of . If the two frequencies are divisible by , the probability that both lifts are divisible by is . Otherwise the gcd valuation is fixed. Thus the average of is at most . In this case and . When one frequency is zero and , the other coordinate is uniform since every coordinate determines the other one uniquely. Combining all prime powers gives
The second estimate also holds with the coordinates exchanged.
Let be the sum of over the respective restricted interval. For each , the geometric-series bound gives
Indeed the chosen integers run through a progression of step , and multiplying the frequencies by permutes the nonzero multiples of modulo . In the Fourier expansion the zero pair contributes . For the other pairs, bound by the sum of over the divisors dividing both frequencies when both are nonzero. The two geometric-series bounds give a total frequency weight at most . When exactly one frequency is zero, use there and bound in the other coordinate by the sum of over . This gives a weight at most . Dividing by and applying the respective complete-sum bounds gives the stated box estimate.
We also use the bound
For each prime power with , the coefficient is a unit, so every has a unique . If , the congruence is equivalent to . For each , the count is , which gives the bound by the Chinese remainder theorem.
A preimage theorem below the square root
Theorem. Let consist of composite integers with largest prime factor at most whose two largest prime factors, counted with multiplicity, have product at least . For every set of natural density zero,
The family has positive natural density.
Reduction and the collision equation
First fix and apply the argument to the subfamily whose two largest prime factors have product at least . Work in . A repeated prime factor of size at least occurs on inputs. Write the remaining inputs as , where are the two largest primes, coprime to . We have
We may discard an arbitrarily small upper proportion of inputs to require that with a prime coprime to , for some fixed . In fact, the inputs with cost , by bounding the number of choices of by and summing prime reciprocals over . If the largest prime of is below and , the -smooth part of exceeds . This costs by the mean of the logarithm of that smooth part. First choose small and then small.
Use the small-prime conditions in the main research note for each of , with and . Require , , and the reciprocal-divisor condition for with threshold . The same transfer of exceptional sets by prime reciprocal sums works here, since both primes have a fixed power lower bound. In particular, . It suffices to bound the second moment on the retained set by . Dependence on the allowed exceptional proportion is harmless.
For a collision with , the small-prime parts are equal since . Put
Both coefficient pairs are coprime. Put and . For fixed , the collision condition is , with as above. Define the normalized determinant . The zero-determinant proposition in the main note bounds the off-diagonal collisions with by . We now take . Two facts are
Since , every common divisor of divides . Also .
Sieving three prime variables with the fourth fixed
Split the choices of into ranges with a power of two. For a fixed pair of tails and a fixed , split into intervals of the same kind. For each interval for there are possible intervals for since . In particular and . Over the entire box consider pairs with . These determine the integer . The retained collisions require all prime and all above , where is a sufficiently small fixed constant depending on .
For any squarefree coprime to , let be the number of residue pairs for which , where . It is multiplicative by the Chinese remainder theorem. By the box estimate, the number of pairs with is
In each residue pair the numbers of terms in the two intervals are and . Rounding these factors is absorbed by the error using .
Use Selberg's upper-bound sieve, Theorem 21.1 with the primes not dividing , and . We have and
The two axes already give points. When , the curve contributes at least points and intersects the axes in at most two. This follows by completing the product if is a unit and by counting a line otherwise. The upper bound follows from at most two lines or a hyperbola plus the axes.
The reciprocal of the Selberg denominator is at most a constant times over the permitted primes up to . Indeed, the Euler product with local weights defines a distribution on products of these primes in which each prime is present with probability . The expected logarithm of the product is at most , so at least half the weight is on products at most , which are included in the denominator. By Mertens' theorem the reciprocal is therefore
The retained totient bound on bounds the factor for . For , primes up to contribute , primes between and cost by Mertens, and the reciprocal-divisor condition for bounds the product over the remaining primes.
Thus the main contribution per box is at most a constant times
The sieve error costs the displayed box error without times , since the sieve weights the errors for by at most .
Summing the errors
Fix the tails and and write and . Then and are coprime since . For and with , the condition puts in at most one residue class modulo because are coprime. Even over all integers in the dyadic interval,
Here since and . With , the sum of the first error term is , at most since . For the second term use and , so its sum is at most . We have .
Summing these bounds over and the pairs of boxes gives exponents at most
respectively. Both are less than for sufficiently small fixed , so the total error is .
Summing the main term
All prime factors of exceed . If is such a factor, it divides none of . Indeed by the condition . Together with and this gives . Then and the gcd conditions on give . Also when .
For , the sum of over the eligible is at most even over integers. There are eligible divisors of , so this range saves a power of and contributes in total. For , Brun–Titchmarsh bounds the sum of over the primes in the required class by . A class sharing a prime with contains no eligible . Thus summing the main term over costs at most
Here the sum of over eligible divisors of is bounded by a constant times : at each prime the sum over all exponents is and the ratio to is .
For each fixed with small-prime part , we claim that the weighted sum of over the retained tails is
To prove this, set and . Primes in cost a bounded factor by Mertens. Primes above cost a bounded factor because . Let sum over the primes of in . For , is bounded. For , the bound gives in all cases. For fixed and an eligible in this interval, the determinant is a polynomial of degree at most two in , since
Modulo the constant term is . The polynomial has at most two roots, and each residue class has prime reciprocal sum over up to by Brun–Titchmarsh. The unrestricted reciprocal sum over those is . Since , by the Euler product over the -rough factors of . Consequently the term from costs at most this bound times . This proves the claim.
Now sum over the pairs of dyadic intervals for . The reciprocal sum over with is also . The two tail sums therefore give for each . The sum of over -smooth integers is by Mertens' theorem. The main terms, errors and diagonal together give , as required. Cauchy–Schwarz now proves the assertion on the retained inputs, and the discarded upper proportion can be taken arbitrarily small.
Density beyond the dominant-prime family
The family is disjoint from the family in the main note, which has . For the subfamily with , we obtain
For a count in , put and . The exponent of is . Away from the boundaries the region is and . For each there the prime number theorem counts choices of . The integer reciprocal sum in and prime reciprocal sum in converge to the integral
by partial summation and the prime number theorem. Boundary strips of width tending to zero cost a vanishing proportion by the same upper estimates. Summing the dyadic counts proves the density formula, also at . By continuity, the density of the inputs lost by using tends to zero as . The preimage assertion thus holds on all of . The union has density
approximately .
Refinement using the cofactor and prime exponents
Use the same largest two prime factors in decreasing order, counted with multiplicity, and put . Let consist of composite inputs with and logarithmic coordinates , in the region
Corollary. For every natural density-zero set , the inputs in with have density zero. The union has natural density approximately .
It suffices to prove the corollary on closed rectangles strictly inside the region. The boundaries have density zero by the logarithmic prime-and-integer reciprocal count above. More precisely, omit strips of an arbitrarily small fixed width along the boundary, cover the remaining compact subset by finitely many sufficiently small rectangles, and sum the preimage bounds for these rectangles. The preimage assertion persists under such a finite union, so each second moment needs only to count within one rectangle.
Suppose a rectangle is centered at with side lengths at most . On , the tails of both inputs have size , and have size . The discarded inputs and small-prime conditions are treated as before. The main-term bound also goes through: the region has and , so the prime intervals in have a power margin above the moduli . The only change is to keep the sizes in the error terms, using
The first term in the box error, after summing over and the two tails, uses and therefore has two exponents and , up to . The second term uses and gives the exponents and , up to the same error. The first two exponents are strictly below one in the interior. For the last two we have and throughout the region. Taking and the sieve exponent small enough proves the power saving on the rectangle.
To compute the density, the upper boundary for is , with respective intervals , , and . The lower boundary is . The integral giving the density of is
This uses the same prime number theorem count on and the integral of with respect to . Since on , its density adds to that of .