A Deterministic, Pigeonhole Existence Proof of Erdos Problem #728

Jeff Pickhardt

Loading document…

A Deterministic, Pigeonhole Existence Proof of Erdos Problem #728

Abstract

We give a new, independent resolution of the general form of a problem of Erdos, Graham, Ruzsa, and Straus (Erdos Problem #728). 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; in fact for every prescribed C >0 we produce triples with (a+b−n)/log n→Cand a/n,b/n→1 2. The classical 1975 constructions reach only some sufficiently small constant multiple of log n; the content of #728 is the arbitrary constant. The proof is elementary and self-contained, using only Legendre’s formula, the carry form of Kummer’s theorem, the Chebyshev-type bound π(y) = O(y/log y) (proved from central binomial coefficients), and the pigeonhole principle. Its distinguishing feature is that it is a pure existence argument: unlike the two earlier proofs from this project, it constructs no witness and imposes no congruence. Instead it observes that the dangerous prime-power carry constraints can be enforced by placing a single multidimensional torus point into one of only exp(o(k)) boxes; a pigeonhole over exp(γk) multiples of k, followed by the difference of the extreme indices in a populous box, yields an admissible xat a prescribed exponential scale log x= (γ+ o(1))k. The free parameter γ >0 is what lets the logarithmic gap constant be prescribed. The proof was obtained by the Omniscience Research Agent at an order of magnitude lower cost than our two earlier proofs of the same problem—a total compute cost of around $0.10 USD.

File Details

v1 erdos728-pigeonhole.pdf