On a conjecture of Graham concerning greatest common divisors

Abstract:

Let ${a_1} < {a_2} < \cdots < {a_n}$ be a finite sequence of positive integers. R. L. Graham has conjectured that ${\max _{i,j}}\{ {a_i}/({a_i},{a_j})\} \geqslant n$. The following are proved: (1) If ${a_l} = p$, a prime, for some l and $p \ne ({a_i} + {a_j})/2,1 \leqslant i < j \leqslant n$, then the conjecture holds. (2) Given a finite sequence of positive integers ${k_1} < {k_2} < \cdots < {k_m}$, where ${k_I} = p$, a prime, for some I and ${k_m} < n$, consider the set of all positive integral multiples of ${k_1},{k_2}, \ldots ,{k_m}$ which are $< n$. Denote these multiples by ${a_1} < {a_2} < \cdots < {a_q}$. Define ${P_n}$ to be a set consisting of the integers ${a_1} < {a_2} < \cdots < {a_q} < {a_{q + 1}} < \cdots < {a_{q + r}}$ where r is maximal, such that $n \leqslant {a_{q + 1}}$ and ${\max _{i,j}}\{ {a_i}/({a_i},{a_j})\} < n$. Thus \[ {P_n} = {P_n}({k_1},{k_2}, \ldots ,{k_m}).\] Then (a) $|{P_n}| \geqslant n$ for at most finitely many n. (b) If $|{P_n}| < n$ for $n < \mathrm {l.c.m.}\{ k_1, k_2, \ldots , k_m \}$ then $|{P_n}| < n$ for all positive integers n.