On a conjecture of R. L. Graham (Q1344001)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On a conjecture of R. L. Graham |
scientific article |
Statements
On a conjecture of R. L. Graham (English)
0 references
7 November 1995
0 references
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\).
0 references
reduced ratio
0 references
Graham conjecture
0 references
primitive set
0 references
strong Graham conjecture
0 references
distribution of primes
0 references
weak error term
0 references