Let $R(X)$ be the region defined by

$$\displaystyle R(X) = \{(a,b,c) \in \mathbb{R}^3 \colon |b| \leq a \leq c, \, a,c \geq 1, \, a(4ac-b^2) \leq X\}.$$

I want to know how to estimate the sum

$$\displaystyle \sum_{(a,b,c) \in R(X) \cap \mathbb{Z}^3} 2^{\omega(4ac-b^2)},$$

where $\omega(n)$ denotes the number of prime divisors of $n$. An upper bound suffices.

One can show that

$$\displaystyle \sum_{(a,b,c) \in R(X) \cap \mathbb{Z}^3} 1 = O (X \log X),$$

and it's known that the average of $2^{\omega(n)}$ over $n \leq X$ is of order $\log X$. Therefore, the expected upper bound should be about $O(X (\log X)^2)$.

  • 2
    $\begingroup$ It would be nice to mention what is the meaning of $R(X)$ is terms of definite binary quadratic forms. $\endgroup$
    – Luc Guyot
    Oct 31, 2017 at 10:09

1 Answer 1


Your guess is correct. Since $2^{\omega(n)} = \sum_{d | n} \mu^2(d)$ one has $$ S = \sum_{(a,b,c) \in R(X)} 2^{\omega(4ac-b^2)} = \sum_{d \leq X} \mu^2(d) |R_d(X)| $$ where $R_d(X)$ is the set of integer triples $(a,b,c) \in R(X)$ such that $4ac \equiv b^2 \pmod d$.

Let $d$ be a squarefree integer. Let $a,b$ be such that $|b| \leq a$ and let $s = \mathrm{gcd}(4a,d)$. Then for $(a,b,c)$ to be in $R_d(X)$ one must have $s | b^2$, or equivalently $s |b$ since $s$ is squarefree, and also $c \equiv (4a/s)^{-1} b^2 \ \mathrm{mod} \ d/s$. The number of integers $c$ like that, with $a \leq c \leq b^2/(4a) + X/(4a^2)$ is

$$ \leq \frac{s}{d}( \frac{b^2}{4a} + \frac{X}{4a^2} - a) + 1 \leq \frac{s}{d}( \frac{X}{4a^2} - \frac{3 a}{4}) + 1\leq\frac{sX}{4 a^2d} + \mathrm{1}_{as \leq 4d/3}. $$

Moreover the number of integers $b$ such that $|b| \leq a$ and $s | b$ is $$ \leq \frac{2a}{s} + 2. $$ Since the constraint $X \geq a(4ac-b^2)$ yields $ad \leq X$, we have $$ |R_d(X)| \ll \sum_{ad \leq X} (\frac{sX}{a^2d} + \mathrm{1}_{as \leq 4d/3})(\frac{a}{s} + 1) \\ \ll \sum_{ad \leq X} ( \frac{X}{ad} + \frac{sX}{a^2d} + \frac{a}{s} \mathrm{1}_{as \leq 4d/3} + 1 ) \ll \frac{X \log X}{d} + \frac{X}{d} + \sum_{ ad \leq X} ( \frac{sX}{a^2d} + \mathrm{1}_{as \leq d} \frac{a}{s} ). $$ Summing over $d$ we get $$ S \ll X \log^2(X) + \sum_{s} \sum_{ad \leq X \\ s|4a , s|d} ( \frac{sX}{a^2d} + \mathrm{1}_{as \leq 4d/3} \frac{a}{s} ). $$ For each $s$, the inner sum is $$ \ll \sum_{ad \leq X/s^2 } ( \frac{X}{s^2 a^2d} + \mathrm{1}_{as \leq 16d/3} a ) $$ The first sum is $\ll X s^{-2}$, while in the second we have the constraint $a^2 \ll X s^{-3}$ which yields $$ \ll \sum_{a \ll X^{1/2} s^{-3/2}} a \ll X s^{-3} + X^{1/2} s^{-3/2}. $$ So the global sum over $s$ is $\ll X$ and we are done.

Remark: one should be able to extract from this proof an asymptotic formula of the form $c X \log^2(X) + O(X \log X)$.

  • $\begingroup$ There seems o be a mistake in the inequality $\frac{s}{d}( \frac{X}{4a^2} - \frac{3 a}{4}) + 1\leq\frac{sX}{4 a^2d} + \mathrm{1}_{as \leq d}. $. Namely, if $d<as<4d/3$ then the inequality fails. $\endgroup$
    – Dr. Pi
    Oct 31, 2017 at 13:01
  • $\begingroup$ Oh, absolutely. It should be $as \leq 4 d/3$ instead. It does not really affect the proof though. $\endgroup$
    – js21
    Oct 31, 2017 at 13:16
  • 1
    $\begingroup$ Well it does not affect the proof but was apparently worth a downvote :) $\endgroup$
    – js21
    Oct 31, 2017 at 13:20
  • $\begingroup$ cool, i corrected all typos. There were a few more other than $as\leq 4d/3$. $\endgroup$
    – Dr. Pi
    Oct 31, 2017 at 13:51
  • $\begingroup$ not sure if my edits were saved. One more typo is:The first sum is ≪Xs−2 X s 2 , while --->The first sum is ≪Xs−2 \log X X s 2 , while $\endgroup$
    – Dr. Pi
    Oct 31, 2017 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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