On a conjecture of R. L. Graham (Q1344001)

Let \(a\), \(b\) be positive integers, and define the reduced ratio of \(a\) and \(b\) to be \(a/ (a,b)\). R. L. Graham conjectured that the maximum of the reduced ratios of pairs in a finite set \(S\) of integers is at least \(| S|\); it is sufficient to prove this for primitive \(S\), i.e. sets \(S\) for which the g.c.d. of its members is 1. The strong Graham conjecture, which implies the Graham conjecture, asserts that if the maximum of the reduced ratios in a primitive set \(S\) is at most \(| S|\), then \(S\) is one of \(\{2,3, 4,6\}\), \(\{1, \ldots, n\}\), \(\{M(n)/ 1, \ldots, M(n)/n\}\), where \(M(n)\) denotes the l.c.m. of \(1, \ldots, n\). Previous proofs of the strong Graham conjecture for sufficiently large \(n\) (no explicit bound) use deep results on the distribution of primes. Now, the authors prove the strong conjecture for \(n\geq 10^{50, 000}\), using only the prime number theorem with moderately weak error term. It is noted however that, in a recent preprint, R. Balasubramanian and K. Soundararajan prove the strong conjecture for all \(n\).