How many quadratics factorise?

Write down a quadratic. What is the probability that it factorises? Paging Prof. Dirichet…

post

Perhaps Prof. Dirichlet can help us with some maths for once...

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.

Quadratics of the form x² + bx + c which factorise, for b,c ≤ 20

Quadratics of the form $x^2 + bx + c$ which factorise, for $b,c \leq 20$.



Or if we zoom out a bit,
Quadratics of the form x² + bx + c which factorise, for b,c ≤ 100.

Quadratics of the form $x^2 + bx + c$ which factorise, for $b,c \leq 100$.

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:

The orange lines c = bα - α² for α = 0, 1, 2, 3 superimposed on our existing plot

The orange lines $c = bα-α^2$ for $α = 0, 1, 2, 3$ superimposed on our existing plot

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

A generic line $c=bα-α^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:

Our plot with the lines $c = αb-α^2$ for $α$ 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:

$c=b^2/4$ marked in red: the integer pairs on this line are only crossed by an orange line once.

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!

Got it! Our expression for P(n) matches the brute force evaluation.

Got it! Our expression for $P(n)$ matches the brute force evaluation.


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…

Perfect match! The long-term behaviour becomes a good approximation from around n=20.

Perfect match! The long-term behaviour becomes a good approximation from around $n=20$.


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:

Adam is a postdoctoral researcher at Imperial College London, where he investigates weird, non-Newtonian fluids. If he’s not talking about the maths of chocolate fountains he is probably thinking about fonts, helping Professor Dirichlet answer your personal problems, and/or listening to BBC Radio 2.

Twitter  @Pecnut   Website  adamtownsend.com    + More articles by Adam

Matthew Scroggs is a PhD student at UCL working on finite and boundary element methods. His website, mscroggs.co.uk, is full of maths and now features a video of him completing a level of Pac-Man optimally.

Twitter  @mscroggs    Website  mscroggs.co.uk    + More articles by Matthew

You might also like…

One thought on “How many quadratics factorise?

Leave a Reply

Your email address will not be published. Required fields are marked *