The Lonely Runner Conjecture

Lonely RunnerThe eminent mathematician Carl Friedrich Gauss once said, “Mathematics is the queen of the sciences.”   Considering this statement to be true, it is easy to see the span of her kingdom.  From the design of airplane wings to the ever increasing speed of computation, the royal seal of mathematics is a permanent hallmark of industry and science.    Her practitioners, both pure and applied, have pushed the boundaries of current thought into the realm of new abstractions.

Sometimes these new areas are recreational in nature.  In 1967, the mathematician Jörg M. Wills proposed a conjecture that fully embodies such novelty.  The problem was later named by Luis Goddyn in 1998 as The Lonely Runner Conjecture.  The formal statement of the conjecture is the following:

The Lonely Runner Conjecture (1967): Suppose k runners having distinct constant speeds start at a common point and run laps on a circular track with circumference 1.  Then, for any given runner, there is a point in time at which each runner is a distance of at least 1/k along the track away from every other runner.

In pursuit of a counterexample or general proof, mathematicians have also explored specific values of k.  As of 2008, the conjecture has been proved for every value of k up to 7.   Interesting enough, the problem can be reformulated to the following question: Can the conjecture be proved for k > 7?  Reformulations of this character are particularly useful to researchers as they look for new perspectives and angles leading to an ultimate proof.

However, a final proof could remain mummified in the tomb of abstract mathematics for centuries.   Mathematicians normally employ one of three methods of proof in their tomb raiding; mathematical induction, direct deduction, or contradiction.    Of the three, it seems that mathematical induction or contradiction are the methods that will likely yield success for this particular problem.

Mathematical induction is a method that seeks to establish a statement true for the integers by evaluating a base step for a variable, say n, and then proceeding to show the statement is true for n + 1 in the inductive step.   The method of contradiction assumes a particular statement is true or false and proceeds to show a contradiction to the premise.    For The Lonely Runner Conjecture one could imagine how these two methods are used.

In the case of mathematical induction, one could possibly construct an algebraic reformulation of the conjecture that depends on the value of k, the number of runners.  With this, the base step of k = 7 runners could be used and is already shown to be true.   Assuming that the statement would be true for k, the hard part would be to show it true for k + 1.  Alternatively, one could use contradiction by assuming a counterexample exists for some k as a premise, and then show this premise contradicts fundamental logic.

These are just sketches of how one could approach a proof.    The conjecture has escaped all attempts for more than 46 years.  How would you try to prove it?  Would you use induction or contradiction?

It is not clear what will yield a final or partial answer.    The solution could emerge from the tomb this year or remain shrouded for centuries.  However, from the current state of industry and technology to a lonely runner sprinting on a track, the kingdom of mathematics is alive and well.

About Avery Carr

Avery Carr is a senior analyst and past senior editor for the American Mathematical Society Grad Blog. He and his wife, Alison, live in Olive Branch, MS.
This entry was posted in AMS, General, Math, Mathematics in Society, Mathematics Online, Uncategorized. Bookmark the permalink.

One Response to The Lonely Runner Conjecture

  1. David von Rudisill says:

    I would try proof by induction. The base case P(7) has already been proven, where
    P(k) is the proposition that the LRC is true for k runners.

    Of course, the real hard work lies in showing that P (k) → P (k +1).

Leave a Reply

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

HTML tags are not allowed.