A Deterministic Resolution of Erdos Problem #728 via Small-Prime Annihilation

Jeff Pickhardt

Loading document…

A Deterministic Resolution of Erdos Problem #728 via Small-Prime Annihilation

Abstract

We resolve the general form of a problem of Erd˝os, Graham, Ruzsa, and Straus (Erdos Problem #728) in the affirmative. For every pair of constants 0 < C1 < C2 and every fixed 0 <ϵ< 1 2 , there are infinitely many triples of positive integers (a,b,n) with ϵn≤a,b≤(1−ϵ)n such that a! b! |n! (a+ b−n)! and C1 log n<a+ b−n<C2 log n. The classical (1975) constructions reach only some sufficiently small constant multiple of log n; our result reaches an arbitrary prescribed constant multiple. The proof is elementary and self- contained, resting on Legendre’s formula, a cumulative form of Kummer’s theorem, Chebyshev- type prime bounds, and explicit counting. The key mechanism is a two-scale argument: we engineer N= a+bto lie in an arithmetic progression N ≡−1 (mod M), where M is a product of small prime powers of total logarithmic size only a small fraction of log N. This forces νp N k = 0 for every prime p up to a constant multiple of k= a+ b−n, an instance of the classical fact (Lucas [4]; Fine [5]) that a row of Pascal’s triangle avoids a prime p exactly when every base-p digit of N equals p−1, i.e. N ≡−1, so that small primes impose no constraint at all; a generic choice of N within the progression then tames the medium primes, and direct counting shows that medium and large primes together exclude only a vanishing proportion of central values of a. All constants are effective. While the annihilation device is classical, what is new here is that we deploy it partially and cheaply, annihilating only up to a constant multiple of k costs a fraction of log N uniformly in C, rather than the full log N of the classical lcm construction, which is what caps that method at a small constant. This method is determinstic, distinguishing it from a recently presented probabilistic solution to Erdos Problem #728. It’s also methodologically distinct from our companion paper solving the same problem.

File Details

v1 paper-small-prime-annihilation.pdf