How many quadratics factorise?

Privacy & Cookies: This site uses cookies. By continuing to use this website, you agree to their use.
To find out more, including how to control cookies, see here: Cookie Policy

Write down a quadratic—any quadratic you like, but let’s say it should have integer coefficients between 0 and 20. What is the probability that it factorises?

What I really mean is will it factorise ‘over the integers’. So
\[x^2 + 5x + 6 = (x+2)(x+3)\]is in, but
\[x^2 + 2x + 2 = (x + [1-\mathrm{i}]) (x + [1 + \mathrm{i}]) \quad \text{and} \quad x^2 – 2 = (x-\sqrt{2})(x+\sqrt{2})\]are out.

To make it simpler, we will look for quadratics of the form
\[x^2 + bx + c\]where $b$ and $c$ are both positive. Try extending it to negative coefficients yourself afterwards!

Let’s plot a graph of $c$ against $b$, and colour in the values where $x^2+bx+c$ factorises. We’re going to colour these in with a 1×1 box where the bottom-left corner is at the relevant coordinate.

Or if we zoom out a bit,

So the values of $b$ and $c$ which make our equation factorise nicely appear to lie on various straight lines. Which lines are they?

By completing the square (or the quadratic equation), our quadratic factorises if $b^2-4c$ is square. And if it’s square that means we can write it as
\[b^2-4c = (b-k)^2\]for some $k$.

Expanding the right-hand side then, and doing some algebra, we get
\begin{align}
b^2-4c &= (b-k)^2 \\
&= b^2-2bk + k^2 \\
\implies 4c &= 2bk-k^2 \\
\end{align}Now we can note that $k^2$ has to be even (because $4c$ and $2bk$ are both even) and so $k$ is even. Which means we can write $k = 2 \alpha$, for some $\alpha$, and hence
\[ \implies c = b\alpha-\alpha^2. \]

See what these lines look like for the first few $\alpha$s:

Great – our points really are lying on these lines! So our question now becomes:

How many integers $(b,c)$ lie on the lines $c=b\alpha-\alpha^2$, where $b$ and $c$ go up to a maximum number $n$?

But we have to be a little bit careful – notice how (3,2), (4,3), and (5,6) all have two lines going through them? If we keep on adding orange lines we’re going to get more crossings and so we will have to make sure we haven’t double-counted any points.

So the answer to our question is
\[\underbrace{\sum_{\alpha=0}^n (\text{# points on $c=b\alpha-\alpha^2$ where $c,b \leq n$})}_{(*)}-\underbrace{\text{double counting}}_{(**)}.\]

Points on each line

Let’s deal with $(*)$ first. In particular, let’s just look at the $\alpha=0$ line. How many integer points lie on that? Looking at the picture above, it’s $n+1$ (not just $n$ because we’re counting 0 as well.) So then

\[(*) = n + 1 + \sum_{\alpha=1}^n (\text{# points on $c=b\alpha-\alpha^2$ where $c,b \leq n$})\]

(I’ve done a pretty standard thing here of treating the $\alpha=0$ case separately. Can you see why?)

Then we can do the rest of the lines. Let’s draw a generic line $c=b\alpha-\alpha^2$:

Well first we should notice that on this line, integer $b$ means integer $c$. So we only have to count the number of integers on the $b$-axis that the line goes through. And that’s easy to do!

The first integer the line goes through is when $c=0$ (when $b=\alpha$), and then it goes through all the integers until when $c=n$, i.e. when $b = n/\alpha + \alpha$. Now of course this is not necessarily an integer, depending on $n$, and indeed you can see in the picture that it isn’t, so the last one is technically when
\[ b = \left\lfloor \frac{n}{\alpha} + \alpha \right\rfloor = \left\lfloor \frac{n}{\alpha}\right\rfloor + \alpha.\]In case you haven’t seen it before, the floor function $\lfloor x \rfloor$ rounds down $x$ to the nearest integer.

The number of integer $b$s between these points is therefore $(\lfloor n/\alpha \rfloor + \alpha) – \alpha + 1$ (where the $+1$ is again because of fences and fenceposts).

Well… almost. You might have spotted (!) that the last integer the line goes through is indeed when $b=\lfloor n/\alpha \rfloor+\alpha$ unless $\alpha = 1$ or $\alpha = n$, in which case the last one is when $b=n$ (proof is left as an exercise to the reader but it checks out!). Then the number of integer $b$s between these points is $n-\alpha + 1$.

So let’s take take the $\alpha=1$ and $\alpha=n$ case out of the sum, and we get
\begin{align}
(*) &= \overbrace{n + 1}^{\alpha=0} + \overbrace{n}^{\alpha=1} + \sum_{\alpha=2}^{n-1} \left( \left\lfloor \frac{n}{\alpha} \right\rfloor + 1\right) + \overbrace{1}^{\alpha=n}\\
&= n+1 + \sum_{\alpha=1}^{n} \left( \left\lfloor \frac{n}{\alpha} \right\rfloor + 1\right)-2 \\
&= n-1 + \sum_{\alpha=1}^{n} \left( \left\lfloor \frac{n}{\alpha} \right\rfloor + 1\right).
\end{align}Now, you may remember from James Cann’s excellent article in Chalkdust Issue 03 that
\[\sum_{\alpha=1}^n \left\lfloor \frac{n}{\alpha} \right\rfloor = D(n),\]the sum of Dirichlet’s divisor function! So we have
\begin{align}(*) &= n-1 + D(n) + n\\
&= 2n-1 + D(n).
\end{align}This is great because we know quite a lot about this function $D(n)$. But for now, let’s deal with that double counting.

Double counting

Recall that many of the points have two lines going through them. In fact, here’s the graph with all the lines for $\alpha$ up to 20:

Now you can see from the picture that we have double-counted many points. In fact, it looks like we might have double-counted every point but if you look carefully on the left-hand side you can see that’s not true: (4,4) for example only has one line going through it. So which points have we not double-counted?

Consider it this way: for a given point on the graph, which values of $\alpha$ are going to give us the lines which go through that point? In other words, given $b$ and $c$, and
\[ c = \alpha b-\alpha^2,\]what is $\alpha$?

Solving this quadratic tells us
\[\alpha = \frac{b + \sqrt{b^2 – 4c}}{2}\]which has two solutions (and so two lines going through that point) unless $b^2 = 4c$, in which case there is only one solution, and only one line.

So the points that are not double counted lie on the line $c = b^2/4$. Here’s $c = b^2/4$ marked in red:

So how many of them are there?

A similar logic to before applies. The first integer pair on the curve $c=b^2/4$ is (0,0). The last is $(2\sqrt{n},n)$. If you notice that only even values of $b$ give you integer values of $c$, then by the same logic as before you can work out that the number of integer pairs on this curve is
\[\lfloor \sqrt{n} \rfloor + 1.\]

So we have double counted all the points apart from this many. So we should add this to $(*)$ and then halve everything.

Putting it together

OK then, so we have that the number of pairs $(b,c)$ up to $n$ that give you a nice factorisable quadratic is
\[\frac{1}{2} \left( 2n-1 + D(n) + \lfloor \sqrt{n} \rfloor + 1\right) = n + \frac{D(n)}{2} + \frac{\lfloor\sqrt{n}\rfloor}{2}. \]

And to answer our original question—what is the probability $P(n)$ of our quadratic factorising if $0 \leq b,c \leq n$?—we must divide by the total number of possible values of $b$ and $c$, which is $(n+1)^2$, to get
\[\bbox[6pt,border:1px solid teal]{P(n) = \frac{n + \frac{D(n)}{2} + \frac{\lfloor\sqrt{n}\rfloor}{2}}{(n+1)^2}.}\]

Let’s plot it to make sure we’ve got it right!

And we do! We’ve brute-forced the question, trying each integer pair in turn, and plotted that in blue. It’s obscured (for $n\geq 1$) by our expression in orange, so we’ve got it right.

Long-term behaviour

Now it gets more interesting. So what happens if we pick any positive integers $b,c$, rather than capping them at $n$? What is the probability of our quadratic factorising as $n\to\infty$?

Recall that we know the long-term behaviour of Dirichlet’s counting function! As $n\to\infty$,
\[D(n) = n \log n + (2\gamma – 1)n + O(\sqrt{n}),\]where $\gamma$ is the Euler–Mascheroni constant, $\gamma \approx 0.57$.

So from our boxed result above, the number of points is
\begin{align}
P(n) =& \frac{1}{(n+1)^2}\left[ n + \frac{D(n)}{2} + \frac{\lfloor \sqrt{n} \rfloor}{2} \right] \\
\xrightarrow{n\to\infty}& \frac{1}{n^2}\left[ n + \frac{n \log n + (2\gamma-1)n + O(\sqrt{n})}{2} + \frac{O(\sqrt{n})}{2} \right] \\
=& \frac{1}{n} + \frac{\log n}{2n} + \frac{2\gamma-1}{2n} + O(n^{-3/2}),
\end{align}
i.e., as $n\to\infty$, the probability of our quadratic factorising is
\[\bbox[6pt,border:1px solid teal]{P(n) \to \frac{\log n}{2n} + \frac{2\gamma+1}{2n} + O(n^{-3/2}).}\]
Let’s see what that looks like vs the actual measurements…

Hoorah!

And indeed, as $n\to \infty$, as you might expect, our probability goes to 0. But it does so in this lovely controlled way.

Do you know a better approach to this problem? Let us know in the comments below!

Download the code

You can download the Python code used to generate these graphs from the GitHub repository. In particular:

• Code to recreate the graphs of $c$ vs $b$
• Code to recreate the graphs of $P(n)$ vs $n$