Patrick Stevens bio photo

Patrick Stevens

Former mathematics student at the University of Cambridge; now a software engineer.

Email Twitter Github Stackoverflow

Splitting questions

Splitting questions

I recently attended a talk by Tim Gowers on “how mathematicians can solve problems without thinking”. In the spirit of some of my previous posts about [discovering proofs], I thought I’d give an outline and demonstration of the technique he outlined. I’ll be using it to try and solve a problem I’ve never seen before.

The technique

Gowers calls his technique “splitting questions”. The idea is modelled on performing some kind of [binary search] through the space of possible proofs. Given a problem to solve, one identifies an easier question (a “splitting question”) that, if it were answered either negatively or positively, would make the problem easier in some way. Then, using this same technique, one determines the answer to the splitting question, and in this way, the original problem becomes easier. The aim is to get as far as possible by simply accumulating information about the original problem, rather than actually using inspiration and insight.

By way of an example, the question “are there infinitely many primes which are one more than a multiple of four?” has a possible splitting question “are there infinitely many primes?”. To that, the answer is yes, and this makes the original question easier because now we know we may call on having an infinite supply of primes.

Unseen problem

I looked this problem up from the British Maths Olympiad 2015, [paper 1][BMO 2015]. (In the talk, Gowers used an IMO shortlist candidate, but I don’t want this to take prohibitively long to write.)

Determine all functions \(\mathbb{N} \to \mathbb{N}\) such that if \(\dfrac{1}{a} + \dfrac{1}{b} = \dfrac{1}{c}\) then \(\dfrac{1}{f(a)} + \dfrac{1}{f(b)} = \dfrac{1}{f(c)}\).

We’ll call such functions allowable functions.

First splitting question

The very first thing which springs to mind is: “This is an existence question. Does there even exist an allowable \(f\)?” This is a suitable splitting question to begin with: if its answer is “no” then the problem is solved, while if the answer is “yes” then we may actually start working with something.

Of course, the answer is “yes: the identity function works”.

Second splitting question

The next idea for me is: “If we have one or two such functions, can we build another in some way?” I don’t really know where this idea came from, apart from a general “put things together to get another thing” intuition instilled by several lecturers: whenever they make a definition, they define ways to create a new thing given some old things.

This immediately points me to looking at multiplication by a constant: if \(f\) is an allowable function, then \(n \mapsto a f(n)\) is allowable, for any integer \(a\).

How about the “two such functions” bit? Nothing really springs to mind, apart from “Does multiplication of two allowable functions \(f, g\) yield an allowable function?” which on closer thought is sadly false unless for all \(a,b\) we have \(\dfrac{1}{f(a) g(b)} + \dfrac{1}{f(b) g(a)} = 0\), which can’t ever be true because \(f, g\) map into the positive integers.

Third splitting question

My next thought was: “Is this everything? Are the only such functions given by \(x \mapsto a x\) for some \(a\)?” However, I got distracted at this point, and cleared denominators to see what would happen. I wrote the line “\(ac + bc = ab \implies f(a) f(c) + f(b) f(c) = f(a) f(b)\)” and immediately thought of ring homomorphisms. \(\mathbb{N}\) isn’t a ring, but it makes me think, “What can we say if we’re working in the ring \(\mathbb{Z}\)?”.

The question seems to have become “Classify the ring homomorphisms \(\mathbb{Z} \to \mathbb{Z}\), and find which ones restrict to \(\mathbb{N} \to \mathbb{N}\).” Are they actually equivalent viewpoints? MAYBE. Yes: any ring homomorphism must trivially satisfy the “allowable when extended to \(\mathbb{Z}\)” condition, while any function which is allowable on \(\mathbb{Z}\) is indeed a homomorphism. I’ll prove that as a lemma.

Allowable functions on \(\mathbb{Z}\) are homomorphisms

Letting \(c = a\) in the definition of “allowable” as “\(ac + bc = ab \implies f(a) f(c) + f(b) f(c) = f(a) f(b)\)” yields \(a^2 = 0 \implies f(a)^2 + f(b) f(a) = f(a) f(b)\), which is equivalent to the statement \(f(0)^2 = 0\), and hence \(f(0) = 0\). Hence \(f\) does send the identity to the identity.

We still need \(f\) to preserve addition and multiplication. It’s enough for us to ensure that \(f(x+1) = f(x) + f(1)\) and that \(f(-x) = -f(x)\); that would give \(f(x+n) = f(x) + f(n)\) for all \(n \geq 0\) and then for all \(n < 0\). It would also give \(f(n m) = f(m + \dots + m) = n f(m)\).

What are the homomorphisms?

The next step tumbled into my mind without further prodding, so I don’t have splitting questions for it.

A homomorphism has an ideal as its kernel. The ideals in \(\mathbb{Z}\) are precisely things of the form “all multiples of \(a\) for some \(a\)”, since \(\mathbb{Z}\) is a principal ideal domain.

Splitting question: can we get away with restricting to \(\{0\}\) as the kernel? That is, can we insist that \(f\) be injective? (Of course, we could use the zero function, but that doesn’t restrict to \(\mathbb{N}\).)

Sub-question: can we make a homomorphism with \(ac+bc = ab \implies f(a) f(c) + f(b) f(c) = f(a) f(b)\) but \(f(2) = 0\)?

Well, any homomorphism would have to take the value \(0\) on all multiples of two, and would have to take the same value on all odd numbers. Since \(f(3) = f(1) f(3)\), we must have \(f\) being the indicator function on the odd numbers. Is this a homomorphism? No: \(f(2) = f(1+1) = 2 f(1)\).

That answers the sub-question, and shows me what should have been obvious from the start: all homomorphisms are determined by the image of \(1\), and each image of \(1\) determines a homomorphism.

That answers the main splitting question, too: yes, homomorphisms must be injective. Moreover, iff \(f(1) > 0\) then \(f\) restricts to \(\mathbb{N}\) to give an allowable function, which is of the form \(x \mapsto a x\) for some \(a\).

Summary

The allowable functions are precisely \(x \mapsto a x\) for some constant \(a \in \mathbb{N}\). This was obtained by first noting that all of those are indeed solutions, then showing that all solutions must be automorphisms of \(\mathbb{Z}\) restricted to \(\mathbb{N}\), then classifying the automorphisms of \(\mathbb{Z}\).

[discovering proofs]: [binary search]: [BMO 2015]: http://www.bmoc.maths.org/home/bmolot.pdf