A Strong Form of a Problem of R. L. Graham
Let \(A= \{a_1,a_2,\dots, a_M\}\) be a set of positive integers with \(\text{gcd}(a_1,a_2,\dots, a_M)= 1\) and let \(G(A)\) denote the maximum of \(a_i/(a_i,a_j)\) over all \(i\), \(j\). Define the dual \(A^*\) of \(A\) by \(A^*= \{{L\over a_1}, {L\over a_2},\dots, {L\over a_M}\}\), where \(L= \text{lcm}[a_1,\dots, a_M]\); then \(G(A^*)= G(A)\). In [Acta Arith. 75, 1--38 (1996; Zbl 0853.11002)] \textit{R. Balasubramanian} and \textit{K. Soundararajan} proved that if \(M> 4\), then \(G(A)\geq M\), and moreover if \(G(A)= M\), then \(A\) or \(A^*\) is equal to \(\{1,2,\dots,M\}\). This result established for all \(M\) a conjecture made in 1970 by R. L. Graham which previously had been shown independently in the 1980's for all large \(M\) by M. Szegedy and A. Zaharescu. The objective of the current paper is to derive an extension of the above result by showing that if \(G(A)= N\) with \(N\) not too much larger than \(M\), then \(A\) or \(A^*\) lies in \(\{1,2,\dots,N\}\). Let \(f(N)\) denote the largest \(R\) such that for every set \(A\) of \(M\) positive integers with \(N- R\leq M\leq N\) and \(G(A)\leq N\), then either \(A\) or \(A^*\) is contained in \(\{1,2,\dots, N\}\). Then Theorem 1 states that \(f(N)\geq cN{\log\log N\over\log^2 N}\) for large \(N\), where \(c> 0\) is an absolute constant. The author remarks that the stronger result claimed without proof in the paper cited above appears to be too optimistic. In the other direction, the result \(f(N)\ll{N\over\log\log N}\) is established in Theorem 2 by a counterexample. The proof of Theorem 1 is delicate and intricate, and utilizes notation and lemmas from the paper cited above, and also from the present author's paper in [Combinatorica 23, 263--281 (2003; Zbl 1046.05077)] concerning the maximum number of \(k\)-term arithmetic progressions one can have such that any two of them have two elements in common.
- Some remarks on a number theoretic problem of Graham
- scientific article; zbMATH DE number 4162967
- The Proof of a Conjecture of Graham for Sequences Containing Primes
- On a Conjecture of Graham Concerning Greatest Common Divisors
- Sets of integers with pairwise common divisor and a factor from a specified set of primes
- The solution of Graham's greatest common divisor problem
- On a conjecture of Graham
- On exceptions to Szegedy's theorem
- On a Conjecture of Graham
- scientific article; zbMATH DE number 1113596
This page was built for publication: A Strong Form of a Problem of R. L. Graham
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4824415)