On generalizations of a problem of Diophantus (Q1766830): Difference between revisions

For any integer \(k\geq 2\) let \(V_k\) be the set of \(k\)th perfect powers. Given finite sets of positive integers \({\mathcal A}\) and \({\mathcal B}\), the authors determine nontrivial upper bounds for the number of pairs \((a,b)\) with \(a\in {\mathcal A}\) and \(b\in {\mathcal B}\) such that \(ab+1\in V_k\). For example, assuming that \(| {\mathcal A}| \geq | {\mathcal B}| \), the above number is bounded above by \(7.64| {\mathcal A}| | {\mathcal B}| ^{2/3}\) if \(k= 3\) and \(5.47| {\mathcal A}| | {\mathcal B}| ^{1/2}\) if \(k\geq 4\). When \(k=2\), they only have a much weaker result only when \({\mathcal A}={\mathcal B}\). As a corollary to their result, they deduce that if \({\mathcal A}\subset \{1,\dots,N\}\) is a set such that \(ab+1\) is perfect power whenever \(a\neq b\) are in \({\mathcal A}\), then \(| {\mathcal A}| =O((\log N/\log\log N)^2)\), improving upon a result of \textit{K. Gyarmati, A. Sárközy} and \textit{C. L. Stewart} [``On shifted products which are powers'', Mathematika 49, No. 1--2, 227--230 (2004; Zbl 1047.11029)]. They also determine an upper bound for the cardinality of a set \({\mathcal A}\subset \{1,\dots,N\}\) such that \(a^2+b^2\) is a perfect square whenever \(a\neq b\) are in \({\mathcal A}\). The proofs ingeniously combine earlier work on sets \({\mathcal A}\) of positive integers such that \(ab+1\in V_k\) for all \(a\neq b\) in \({\mathcal A}\) due to Dujella (for \(k=2\)) and Bugeaud and Dujella (for \(k\geq 3\)) with Turán type upper bounds for the maximum number of edges of a graph with \(n\) vertices which does not contain certain subgraphs (complete, or complete bipartite, etc.). Reviewer's remark. Some of the results of the paper under review were recently sharpened both by the reviewer and by C. L. Stewart.