Asymptotics on certain number of polynomials

39 Views Asked by At

I want to count number of polynomials $f(x) = (ax - b) (cx - d)$ with $a, b, c, d \in\mathbb{Z}$ such that the each coefficients of $f(x)$ lies in $\{-L, -L+1, \ldots, -1, 0, 1, \ldots, L-1, L\}$ and $a$ and $c$ are relatively prime.

Note that $f(x) = acx^{2} - x (ad + bc) + bd $.

If the coefficient of $x$ was not there and $a$ and $c$ were not stipulated to be coprime, then I know that number of ways to choose $a, b, c, d$ such that $|ac|\leq L$ and $|bd|\leq L$ is $O(L^{2}\log(L)^{2})$. This is because choosing $a$ and $c$ (or $b$ and $d$) is $\sim \sum_{i\leq L}d(i) = O (L\log(L))$.

Since we require $a$ and $c$ to be coprime and $|ad + bc| \leq L$; I naively still expect the asymptotics to be smaller. However, I cannot come up with an argument to justify/rebuke this.

1

There are 1 best solutions below

2
On BEST ANSWER

Approximately, it doesn’t matter. The coprime piece is mostly irrelevant - if both of them are a multiple of $g$, instead of $L log L$ you have $L/g^2 log (L/g^2)$, so you have a lower bound of $L log L - L/4 log L -L/9 log L -L/16 log L ... > .3 L log L$, so it’s just a constant factor bad. Similarly, if $ad$ and $bc$ are opposite signs, then it’s always good. So at least half of such sets work.

Note that there still are some duplicates (ex: if a and b have common factors), so you’d have to be careful to get this rigorously, but generally asymptotically speaking I don’t think it matters.