# Gcd of linear function

$$\DeclareMathOperator\gcd{gcd}$$Take $$q\in \mathbb N$$ and $$X>0$$ ($$q$$ not necessarily smaller than $$X$$). A sum such as $$\sum_{d\leq X}(q,d)$$ is easily seen to be $$\ll q^\epsilon (X+q)$$ so that the gcd doesn't make the sum much larger than how it would be without it — the values for which $$(q,d)$$ are significant are rare.

If I have instead a sum like $$\sum_{dd'\leq X}(q,d+d')$$ can I still conclude a similar bound, thinking that the $$d+d'$$ should give just as "random values" to $$(q,d+d')$$ as did $$d$$ to $$(q,d)$$? Or is this completely the wrong way to think about it?

It's of course similar to asking about $$\sum_{\substack{dd'\leq X\\q\mid d+d'}}1$$ which seems easy enough but I'm still a bit unsure… is this even $$\ll (qX)^\epsilon (X/q+1)$$?

• Which definition of $\ll$ are you using here? I'm used to seeing it to mean something approximating little-o notation, but for $q = 2$, the sum is around $\frac{3}{2} X$, if I'm not mistaken. Sep 22 '20 at 21:03
• If $q = \prod p_i^{n_i}$ is held constant, then the first sum is approximately $\prod (1 + \frac{p_i - 1}{p_i} n_i) X$ for large $X$. There may be few significant large contributors, but if the number of contributors is comparable to $X$, then that can be a large contribution on its own. Sep 22 '20 at 21:26
• $\ll$ means the usual one ($X\ll Y$ if $|X|<CY$, for some positive $C$). Sep 22 '20 at 22:14
• hmm not sure about your second comment (if $q$ is constant then the gcd is irrelevant given the bounds i'm trying for. are you sure that's what you mean or maybe i misunderstood? Sep 22 '20 at 22:16
• I probably should have written $X \prod (1 + \frac{p_i - 1}{p_i} n_i)$ for clarity, but otherwise yes. And that also should disprove the assertion if we instead let $q$ grow: consider $q_i = X_i = 2^i$; then the sum is $(1 + \frac{i}{2}) X$, which is eventually larger than $C (X + q)$ for any $C$. Sep 22 '20 at 22:31

1. We have $$\sum_{\substack{dd'\leq X\\q\mid d+d'\\d\leq d'}}1 =\sum_{d\leq\sqrt{X}}\sum_{\substack{d'\leq X/d\\q\mid d+d'\\d\leq d'}}1 \leq\sum_{d\leq\sqrt{X}}\sum_{\substack{c\leq 2X/d\\q\mid c}}1 \leq\sum_{d\leq\sqrt{X}}\frac{2X}{qd}<\frac{2X(1+\log\sqrt{X})}{q}.$$ We get the same bound when the roles of $$d$$ and $$d'$$ are interchanged, hence in the end $$\sum_{\substack{dd'\leq X\\q\mid d+d'}}1<\frac{2X(2+\log X)}{q}\ll_\epsilon\frac{X^{1+\epsilon}}{q}.$$
2. From the last inequality we infer $$\sum_{dd'\leq X}(q,d+d')\leq \sum_{r\mid q}r\sum_{\substack{dd'\leq X\\r\mid d+d'}}1 \ll_\epsilon\sum_{r\mid q}r\frac{X^{1+\epsilon}}{r}\ll_\epsilon (qX)^\epsilon X.$$