Farey sequence and Graham's conjectures (Q1981607)

Let \(F_n\) be the set of Farey fractions of order \(n\). For a subset \(S\subseteq F_n\), consider the set of corresponding quotients of the form \(\mathcal{Q}(S)=\{\frac xy:x,y\in S,\, x\le y\}\). The author raises the question of classifying subsets \(S\) with the property that \(\mathcal{Q}(S)=F_n\). It is immediate that the sets \(S_1=\{0,\frac1n,\frac1{n-1}\dots,\frac11\}\) and \(S_2=\{0,\frac1n,\frac2n,\dots,\frac nn\}\) are two solutions to this equation. The paper under review resolves this question completely by showing the following. In the first place, if \(\mathcal{Q}(S)\subseteq F_n\), then \(S\) has at most \(n+1\) elements. The set equality has only two solutions \(S=S_i\) indicated above. Moreover, with one exception, these two sets are also the only sets \(S\) of order \(n+1\) which satisfy this relation. The exceptional case occurs for \(n=4\), with \(S=\{0,\frac13,\frac12,\frac23,1\}\). The author deduces these results by showing that they are equivalent to something known in the literature as ``Graham's greatest common divisor problem''. The latter problem has now been settled, with the complete solution finally obtained by \textit{R. Balasubramanian} and \textit{K. Soundararajan} [Acta Arith. 75, No. 1, 1--38 (1996; Zbl 0853.11002)].