Two Unequal Products
I’ve been watching some of Timothy Gowers’ videos in which he documents his attempts to solve various mathematics problems. Gowers’ goal is to provide some examples of the mathematical thought process for other to study. I don’t have any deep insights on this to share, but watching the mental process of a serious mathematician as he tackles a problem is certainly interesting. And the problems are interesting themselves.
The second problem Gowers tackles is the topic of this post. He solves it, but the solution doesn’t feel particularly satisfying. It doesn’t feel satisfying to him, either, so he tries another path towards a simpler solution that doesn’t pan out. Here, I take a pass.
The Problem
Here’s Gowers’ statement of the problem:
Prove that for every positive integer $n$, there do not exist positive integers $a$, $b$, $c$, $d$ with $ad=bc$ and $n^2 < a < b < c < d < (n+1)^2$.
I suggest that you take some time to think this through and go watch Gowers’ videos before reading on. Below is my solution. I took a lot longer to get to this than Gowers, but the result seems reasonably elegant.
Some Intuition
Before jumping into it, I want to say a few words about my intuition for the problem. Clearly, if the numbers $a$, $b$, $c$, and $d$ were arbitrary reals or rationals, then it would be easy to come up with values that make this work. So for this to fail, we’re going to have to make use of properties that are special to the integers.
In particular, I want to use the inequality to generate some extra space that I can use to show that the gap between $n^2$ and $(n+1)^2$ isn’t large enough to hold our numbers. My initial attempts were to observe that over the integers, $a>n^2$ means that $a\geq n^2+1$, that $b\geq n^2+2$, etc. But I wasn’t able to use this by itself to generate a large enough gap for the proposition to fail.
The other property of integers is that they factor. And putting this together with the observation above does generate enough space. Let’s see how this works.
My Solution
Assume that the statement were true; we’ll derive a contradiction. Given that $ad=bc$, we can write
\[\tag{1} {ad \over b} = c\]Since these are all positive integers, we can expand out $a$ and $d$ as products of (non-distinct) primes: $a = p_1 p_2 \ldots p_m$ and $d = q_1 q_2 \ldots q_n$. And since the result of the division is an integer, we can see that $b$ must be the product of a subset of these $p$ and $q$ values, with $c$ being the product of the remaining factors. Explicitly, we can rewrite equation (1) as:
\[{ { p_1 p_2 \ldots p_m q_1 q_2 \ldots q_n } \over { p_{\alpha_1}\ldots p_{\alpha_k} q_{\beta_1}\ldots q_{\beta_l} } } = { p_{\gamma_1}\ldots p_{\gamma_i} q_{\delta_1}\ldots q_{\delta_j} }\]Where the $p_\alpha$s and $p_\gamma$s account for all of the $p_1,\ldots,p_m$ and $q_\beta$s and $q_\delta$s account for all of the $q_1,\ldots,q_n$. If we collect up all of the $p$ terms used to create $b$ as $a_1$, and the leftover ones as $a_2$, and do likewise for the $q$ terms to create $d_1$ and $d_2$, we can rewrite the whole thing as:
\[\tag{2} { {a_1 a_2 d_1 d_2} \over {a_1 d_1} } = a_2 d_2 \quad\text{where}\quad \begin{cases} a = a_1 a_2\\ b = a_1 d_1\\ c = a_2 d_2\\ d = d_1 d_2 \end{cases}\]All of these terms are still positive integers (possibly 1), but we now have:
\[n^2 < \overbrace{a_1 a_2 < \underbrace{a_1 d_1} } < a_2 d_2 < \underbrace{d_1 d_2} < (n+1)^2\]Comparing the indicated terms, we can extract:
\[\begin{align}\tag{3} d_1 > a_2 &\implies d_1 \geq a_2 +1\\ d_2 > a_1 &\implies d_2 \geq a_1 +1 \end{align}\]These implications make use of the fact that the terms are all integers. Now we can see that:
\[\begin{aligned} \boxed{n^2 + 2n + 1} = (n+1)^2 &> d \\ &= d_1 d_2 \\ &\geq (a_2 + 1)(a_1 + 1) \\ &= a_1 a_2 + a_1 + a_2 + 1 \\ &> \boxed{n^2 + a_1 + a_2 + 1} \end{aligned}\]Has this forced enough space to generate a contradiction? Together, the boxed terms tell us that:
\[\begin{aligned} 2n &> a_1 + a_2 \\ 4n^2 &> a_1^2 + 2a_1 a_2 + a_2^2 \\ 4a_1 a_2 &> a_1^2 + 2a_1 a_2 + a_2^2 \\ 0 &> a_1^2 - 2a_1 a_2 + a_2^2 \\ 0 &> (a_1 - a_2)^2 \end{aligned}\]And this last statement cannot hold for positive integers $a_1$ and $a_2$, so our assumption that $ad = bc$ must fail.
Discussion
Making use of a few properties of the integers – factorization and discreteness – pays off. By cleanly factoring them in step (2), and developing an inequality on the factors in step (3), we’re able to then amplify the difference of the product enough to generate a contradiction.
