Mathematical proof: Five satellites needed for precise navigation

How does GPS work?

GPS satellites are equipped with an extremely accurate atomic clock and know their positions at all times. They continually transmit the time and their location using radio waves. A mobile phone or other navigation device receives these signals from all satellites within their line of sight. The difference between the arrival time at the local clock of the receiver and the transmission time recorded by the satellite clock corresponds to the time taken for the signal to travel from the satellite to the receiver (the "time of flight"). Since radio waves travel at the speed of light, the time of flight determines the distance covered by the signal. The satellite positions and the distances are used to calculate the position of the receiver using a system of equations.

This simplified description does not take into account the fact that the local clock in the receiver is not an atomic clock. If it is inaccurate by just one millionth of a second, the calculated position will be inaccurate by at least 300 meters. The GPS problem is the need for the phone or other navigation device to determine the precise time along with the location -- known in the theory of relativity as space-time.

If too few satellites are in the line of sight, the system no longer functions reliably and delivers multiple solutions, in other words several different locations where the receiver could be. This can lead to the situation where a phone indicates an incorrect location or no location at all. Until now the number of satellites needed to obtain unique solutions to the GPS problem has only been conjectured.

Five satellites for a precise location

Mireille Boutin, a professor of discrete algebra and geometry at TU/e and Gregor Kemper, a professor of algorithmic algebra at TUM, have now produced a mathematical proof showing that with five or more satellites, the exact position of the receiver can be uniquely determined in almost all cases. "Although this was a long-standing conjecture, nobody had managed to find a proof. And it was far from simple: We worked on the problem for over a year before we got there," says Gregor Kemper. At present every location on Earth has sight contact to at least four satellites at all times. "Roughly speaking, with only four satellites, the probability of having a unique solution to the GPS problem appears to be 50 percent. Proving that statement is one of our next projects," says Kemper. With three or fewer satellites in the line of sight, GPS navigation definitely does not work.

Geometry and uniqueness

The researchers arrived at the proof by characterizing the GPS problem in geometric terms. They found out that the position of the receiver cannot be uniquely determined if the satellites are located on a hyperboloid of revolution of two sheets. This is a curved surface that is open in all directions. Although this result is theoretical, it has the practical benefit of offering a better understanding of inaccuracies in determining positions.