On divisibility properties of integers of the form \(ab+1\) (Q5948351): Difference between revisions

\textit{P. Erdős} and \textit{A. Sárközy} [Acta Math. Hung. 50, 117--122 (1987; Zbl 0625.10038)] asked how large \(|\mathcal{A}|\) with \({\mathcal A} \subseteq \{1,2,\cdots, N\}\) can be if \(a+a'\) is square-free for all \(a,a' \in {\mathcal A}\). They proved that there exist such sets \({\mathcal A}\) with \(|{\mathcal{A}}|\gg \log N\). As an upper bound, they obtained \(|{\mathcal{A}}|\ll N^{3/4}\log N\). In the paper under review, the author asks related questions about sums of two sets \({\mathcal A,\mathcal B}\) and about the multiplicative analogue. Theorem 1: If \({\mathcal A,\mathcal B}\subseteq \{1,2,\cdots, N\}\) and all \(ab+1\) are square-free for all \(a \in {\mathcal A}, b \in {\mathcal B}\), then \(|{\mathcal A}|\cdot |{\mathcal B}|\ll N^{3/2} (\log N)^2\). The proof makes use of an adaptation of the large sieve method due to \textit{A. Sárközy} [Acta Math. Hung. 60, 271--282 (1992; Zbl 0772.11037)]. Theorem 2: There exist sets \({\mathcal A, \mathcal B}\) with \(a+b\) square-free or \(ab+1\) square-free, respectively, with \(|{\mathcal A}|= |{\mathcal B}|\gg (\log N)^2\). Theorem 3: There exist sets \({\mathcal A}\) with \(a+a'\) square-free or \(aa'+1\) square-free, respectively, with \(|{\mathcal A}|\gg \log N\). The proofs of these two theorems are a very nice application of results from extremal graph theory (Turán's graph theorem and the Kővari-Sós-Turán theorem). In Theorems 2 and 3 one can refine the argument when making use of \(\sum_{p>y,\quad p \text{ prime }} {1\over p^2} \sim {1\over y \log y}\). This improves the result by a factor of \(\log \log N\).