Extremal Problems for GCDs and LCMs in Higher Dimensions

Abstract

We study extremal problems for tuples of integers chosen from sets $A_i\subset [X_i,2X_i]$ for $1\le i\le k$, under large GCD and small LCM conditions. For the GCD problem, we extend the work of Green and Walker to higher dimensions. Specifically, for $k\ge 3$, if $\gcd (a_1,\dots ,a_k)\ge D$ for at least a proportion $\hat{I}´$ of the tuples in ${\prod }_{i=1}^k{A}_i$, then $$\prod _{i=1}^k|A_i|{\ll }_{k,\epsilon }\hat{I}{´}^{-k/(k-1)-\epsilon }\frac{{\prod }_{i=1}^k{X}_i}{D^k}.$$ The proof is based on a minimal counterexample argument and a new high-dimensional measure concentration lemma. We also establish a large sieve-type inequality to obtain a complementary estimate for the GCD problem. For the LCM problem, we use a quite different method to show that, for all $k\ge 2$, $$\prod _{i=1}^k|A_i|{\ll }_{k,\epsilon }\hat{I}{´}^{-k/(k-1)}\frac{L^{k/(k-1)+\epsilon }}{({\prod }_{i=1}^k{X}_i{)}^{1/(k-1)}},$$ whenever $\mathrm{lcm}(a_1,\dots ,a_k)\le L$ for at least a proportion $\hat{I}´$ of the $k$-tuples in ${\prod }_{i=1}^k{A}_i$. Finally, we show that these bounds are essentially best possible up to $\epsilon$-losses in the exponent.

20 pages