Erdos Problem 394 and the average order of t_2: a counterexample to the strong form

Jeff Pickhardt

Loading document…

Erdos Problem 394 and the average order of t_2: a counterexample to the strong form

Abstract

For n≥1 let t2(n) be the least m≥1 with n|m(m+ 1). Erd˝os Problem 394 [3] asks, in its weak form, whether n≤x t2(n) ≪x2/(log x)c for some c > 0; the remarks to the problem record a strong form due to Erd˝os and Hall, that the sum is o x2/(log x)c for every c<log 2. We give a counterexample to the strong form. Writing n = ab with a prime and b squarefree, each of the 2ω(n) coprime splittings of n imposes a condition on a that depends only on amodulo a divisor of b, and bijectively so; a union bound over the divisors of a fixed bthen produces a set of admissible residues of density ≥31 32 , and Brun–Titchmarsh supplies a positive proportion of primes in those classes. This yields x2 t2(n) ≫ (log x)1/2 log log x , n≤x hence n≤x t2(n) ≫c x2/(log x)c for every fixed c > 1 2 , and the strong form fails for every c ∈(1 2 ,log 2). The proof is elementary given Brun–Titchmarsh, Mertens’ theorem and the prime number theorem; the factor log log x is an artifact of the argument. The same bound constrains the exponent in the weak form: any admissible c satisfies c ≤ 1 2 . Heuristics and computation, which we do not claim as proof, indicate that 1 2 is attained, i.e. n≤x t2(n) ≍x2(log x)−1/2, and identify the source of the discrepancy with log 2: that exponent governs a typical n, whereas the sum is dominated by nwith atypically few prime factors, for which the relevant mean is (log x)−1/2.

File Details

v1 paper.pdf