1
$\begingroup$

$\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)$?

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – user44191
    Sep 22, 2020 at 21:03
  • $\begingroup$ 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. $\endgroup$
    – user44191
    Sep 22, 2020 at 21:26
  • 2
    $\begingroup$ $\ll $ means the usual one ($X\ll Y $ if $|X|<CY$, for some positive $C$). $\endgroup$
    – tomos
    Sep 22, 2020 at 22:14
  • $\begingroup$ 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? $\endgroup$
    – tomos
    Sep 22, 2020 at 22:16
  • $\begingroup$ 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$. $\endgroup$
    – user44191
    Sep 22, 2020 at 22:31

1 Answer 1

1
$\begingroup$

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.$$

$\endgroup$
1
  • 1
    $\begingroup$ top! thanks a lot! ^ ^ $\endgroup$
    – tomos
    Sep 24, 2020 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.