The Kissing Number

22 September 1991

Marvin Q. Mogul looked out of the window of his penthouse bubbledome at the red sands of Mars. As President of Mars Television his office was the highest in Syrtis City. It was on the second floor. The TV was blaring --- some silly report from Cosmic News Network about the Olympus Expedition finding ancient Martian artefacts. The newsreader seemed excited. Mogul cursed his rival at CosNN and turned the TV off. He had more important things to think about.

Spread across his desk were maps of the Martian surface. On a chair was a large globe of the planet, covered in sticky plastic disks. Every so often he fiddled with the globe, peeling disks off and replacing them elsewhere, drawing curved lines on the maps in pink felt-tip, before running his fingers through his thinning hair in a gesture of futility. Finally he reached for the phone. "Cressida, get Fogberry and Cosgrove over here at once, will you?" He resumed staring out of the window at the red sands of Mars.

It had all seemed so easy when, against heavy competition, he had secured the franchise to televise the new Martian colonies. If only it hadn't been for that confounded efficiency clause! His lawyers had assured him that it was harmless: all he had to do was to provide a more efficient service than his competitors promised in their bids. But now the Supreme Court had ruled that such clauses imposed the duty of performing as efficiently as possible. If at any later time anyone came up with a superior scheme, Mars TV would lose the franchise. Then the parent company, Communications Interplanetary, already much too highly leveraged, would run into really serious cash-flow problems, and --- well, it would be just too dreadful to contemplate.

Fergus Fogberry arrived. "Did you see the CosNN report on the Olympus Expedition, Marvin?"

Mogul grunted in irritation. Fogberry took the hint and shut up. Then he became aware of the maps, raised his eyebrows, and sat down. "Layouts, Marvin? I thought that was all settled months ago. Eight transmitters, one at each corner of an imaginary cube."

"It was all settled months ago, Fergus, but now it's unsettled, thanks to the Supreme Court. We can't just offer better coverage than the Arean Broadcasting Corporation or Phobos Booster Satellites did when they bid against us; we've got to offer the best possible coverage."

"Then do so. It may cost a bit more, but Mars TV is such a profit machine that ---"

"I don't mind spending the extra money, Fergus. I just don't know what the best coverage is!"

At that moment Basil Cosgrove turned up, panting heavily from an ill-judged short cut through Mars's thin atmosphere without putting on breathing equipment. "Hey! Did you see that CosNN report on the Olympus Expe--- " Fogberry waved at him to be quiet, while Mogul turned bright pink. Then they started to explain the problem to him all over again. They had scarcely started when Cosgrove interrupted.

"Sorry, Chief, but we need to sort out the details first. Like, what does the Supreme Court mean by 'best coverage'?"

"According to Porpustone, Porpustone, Green, and Porpustone, they effectively mean we have to provide televisual services to the largest possible area of Mars."

"Let's saturate the place, then," said Fogberry. "Put up so many transmitters that the coverage is one hundred per cent."

Mogul struck the side of his head with the heel of his hand. "Brilliant! Now why didn't I think of that? Cressida, get me Construction--- "

"Sorry Chief," said Cosgrove. "That won't work."

"Why not?"

"If two transmitters have overlapping zones, it causes interference. The picture goes fuzzy, or you see funny shadows and multiple images."

"That's a serious problem?"

"I'm afraid so," said Cosgrove. "Unless you want to lose the franchise. Transmit bad pictures and the opposition will use our intestines for bootlaces."

"Cancel that, Cressida," said Mogul.

"Could we squeeze any extra transmission zones in between the existing ones?" asked Fogberry.

"Depends how much room there is," said Cosgrove. "Each zone has angular diameter 60°, and that means --- "

"Hang on," said Mogul. "I know what a diameter is, but what's an angular diameter?"

"Mars," said Cosgrove, "is a sphere. The transmitters reach a zone that we tend to call 'circular', but actually it's a spherical cap with a circular boundary, a circle that's bent to fit on a sphere. The angular diameter is the angle formed at the centre by two points on opposite sides of the circular boundary, as far apart as possible (Fig.1)."

1 Mars TV's franchise bid: eight transmission zones in a cubic arrangement, each of angular diameter 60°. The gaps are too small to fit extra zones of the same size in between.

"And that's 60°."

"Right. Now, the arrangement that we indicated in our franchise bid involved eight transmitters, placed at the vertices of an imaginary cube (Fig.1). I calculate that the angular separation between neighbouring transmitters is...." his voice tailed off as he punched keys on a portable computer. "Hmm. A bit more than 70°. Good. So they don't overlap; in fact there's a 10° gap between them. Um. What was the question?"

"Can we fit any extra transmitters in between?"

"Let's see. The biggest gaps are where the centres of the faces of the cube would be. The angular separation from one vertex of the cube to the opposite one on a face is... hmmmm, 109°, give or take a bit. Each transmitter has an angular diameter of 60°, that is, an angular radius of 30°, so the gap between them is 109°–30°-30° = 49°. (See Fig.1)."

"Into which we want to fit a 60° transmission zone."

"Yes, Foggy my astute friend."

"So there isn't enough room."

"Precisely." They sat in silence for a few moments.

"Maybe we could shrink the zone, though," said Cosgrove. "Chief, ask Cressida to get Technics on the blower and find out what variability there is in zone settings." He turnd to Mogul. "And while she's doing that, Chief, I really do think you should catch CosNN's program on the Olympus --- well, maybe not, if it upsets you that much."

Cressida shortly got back to them. "Boss, I've found out how much variability there is."

"Great! How much?"

"None."

"None? None? What do you mean, none?" There was a muffled conversation on the other end of the line.

"It's the new system the manufacturers use," she said apologetically. "It's on the labels."

"What new system?" yelled Mogul. "What labels?"

"The labels on the boxes. They just say 'TV transmitter --- no user-serviceable parts inside.' We can't change the settings. It's 60° or nothing."

"That's the increasing sophistication of modern electronics for you, Chief," said Cosgrove. The gloomy silence descended once more.

"Wait a minute," said Mogul. "If we can't fit any more in, then we must have found the best arrangement. Cressida, get me Construction --- "

"Sorry, Chief, but it's not that simple. Just becase you can't add transmitters to the existing arrangement, doesn't mean that some totally diffferent arrangement might not work better."

"Cancel that, Cressida." They returned to peeling sticky disks off the globe and sticking them back on again.

"Put that one over --- " said Fogberry.

"No! If you put it --- " interrupted Cosgrove.

"I think we should rip them all off," began Mogul.

"We do, boss. All the time. Why, Lucky Starr alone --- "

"No, not the customers. I mean rip off the sticky disks and start again. Try to cram them together as much as possible, leave plenty of room for the rest."

"Oh, right. Hey, that looks good! How many have you got?" Mogul counted the disks, lost his way, and started again. Eventually they agreed there were eleven of them.

"It's a good job we tried this," said Marvin Mogul. "Imagine what would have happened if we'd stuck with the cube arrangement in our bid, and then some smart Alec at Cosmic News Network went to the Supreme Court with this arrangement instead."

"His name's Alec Smart, Chief, and --- "

"Cosgrove, I know who's Chief Executive at CosNN. I am merely making the point that ---"

"If Smart lives up to his name, he grabs the goodies."

"Precisely."

"So if we go for your new arrangement of eleven transmitters, and Smart manages to squeeze twelve in somehow, we're dead."

"I'm convinced eleven is the maximum," said Mogul. "I don't see any way to imp---"

"I've just got twelve disks on the globe," yelled Fogberry. (Fig.2)

2 If a regular icosahedron is used, twelve 60° zones can be fitted on to the sphere. But can thirteen be fitted in?

"--- other than an arrangement that looks remarkably like the one Fogberry's just blundered into."

"I put them at the vertices of an icosahedron," said Fogberry. "But there's still a lot of room. If they weren't sticky you could slide them about all over the place. Maybe there's room for a thirteenth?"

"I've got an idea," said Cosgrove. "If we take the total surface area of the sphere, and divide it by the area of one transmitter zone, that puts an upper limit on how many can be crammed in. Yes, I know we're not taking the gaps between disks into account, but at least we'll have something to go on."

"Excellent, Cosgrove. Proceed."

"Right. Let's assume the radius of Mars is 1."

"I hate to split hairs, Cosgrove, but it's 3390 km."

"One unit, I mean. It doesn't matter which units we use, but the numbers are easier if the radius is 1. Then the surface area is 4[pi]. The area of a 60° spherical cap is... hmmm... (2-[root]3)[pi], or about 0.2679[pi]. So the maximum number is 4[pi]/0.2679[pi] = 14.9, and it's got to be a whole number... Chief, the largest possible number of zones is 14."

"Thank you, Cosgrove, but that doesn't help use decide whether 12 is the best. It could be 13 or 14 instead."

"Sorry, Chief. It seemed worth a try. If only there was some way to relate it all to problems that have been solved before... Wait a minute."

"Cosgrove, if all you can do is ---"

"It's the kissing number!" said Cosgrove.

"Cosgrove, Mars TV does not transmit that sort of program." Mogul frowned. "Though maybe..."

"No, Chief. The kissing problem is about how many equal spheres can touch a single sphere of the same size. Without intersecting each other."

"I don't quite ---"

Cosgrove dug in his pockets and pulled out a handful of coins. "Think about it in two dimensions, first," he said. He put one coin down on the table. "I have to place as many other coins, all the same size as this one, so that they all touch it. What's the largest number I can manage?"

Mogul fiddled with the coins for a few seconds. "Six," he said. "They just fit round it."

"They form a regular hexagon," said Fogberry.

"Our problem's just like that, but with spheres," said Cosgrove. "Ball bearings rather than coins, arranged in three dimensions around a single central ball of the same size."

"Cosgrove, our transmitter zones are circles, not ball bearings."

"Spherical caps, actually, Chief. But that's not the point. Imagine two equal spheres touching. If you project one sphere radially onto the other, you get a spherical cap of angular diameter 60° (Fig.3). Any non-overlapping arrangement of 60° caps --- our zones --- corresponds to an arrangement of 'kissing' spheres. So our problem is the kissing number problem for three-dimensional spheres, thinly disguised."

3 Connection with the kissing problem.

"I thought spheres were always three-dimensional."

"Well, you can ask the same question in space of any number of dimensions. Let me dig out my old notes..." He muttered rapidly into a battered personal disorganizer. "Yes, look, here's a table of the best known results for dimensions up to 24 (Table 1).

The values show the range between the largest values yet achieved and the smallest upper limits yet established: those in bold are the final answers since the two limits are equal.

Dimension Kissing number Dimension Kissing number

They inspected Cosgrove's notebook. "The exact number is known for 1, 2, 3, 8, and 24 dimensions," said Cosgrove, "and no others". In five dimensions, for example, all we know is that the kissing number is somewhere between 40 and 46."

"You mean to say the answer is unknown in five dimensions, but known in eight? And twenty-four, for heaven's sake? " asked Mogul. "Why?"

"Well, in four dimensions an arrangement with 24 spheres is known; and it's also known you can't get more than 25. But nobody has yet closed the gap."

"Fine. But why are 8 and 24 dimensions easier than 5?"

"Andrew Odlyzko and Neil Sloane found a way to estimate a good upper bound," said Cosgrove. "It was so good it turned out to be the same as the best known arrangement of spheres. So that was that."

"It still doesn't explain why," said Fogberry. "It just says it's true."

"Well," said Cosgrove uncomfortably, "there's something rather unusual about space of 8 and 24 dimensions. All sorts of sphere-packing problems work out nicest in those dimensions."

(Readers of this department may find it hard to get hold of 24-dimensional spheres, but there are many similar problems they can tackle. For example, finding the smallest circle or square that will contain a given number (1, 2, 3, ... ) of dimes. Or finding kissing numbers for planar shapes such as pentagons or ellipses. If feeling really ambitious, they might like to tackle the problem of Martian transmitters, but with zones whose angular diameter differs from 60°. What is the largest angular diameter for which a given number of identical zones will fit on Mars without overlap? Answers are known for up to 12 zones, and there are some conjectured solutions for a few larger numbers.)

Mogul interrupted the discussion. "According to your table, the kissing number in three dimensions is known to be 12."

"Yes. Isaac Newton and David Gregory argued about it in 1694. Newton said the answer was 12, Gregory thought 13 might be possible. In the 19th Century C.Bender, R.Hoppe, and S.Günther offered proofs that Newton was right. A detailed proof was published in 1953 by K.Schütte and B.L.van der Waerden. The best known proof was found by John Leech in 1956 ---" Cosgrove paused for breath, then rushed ahead before anyone could stop him, " --- and even his proof is far from easy. One source of difficulty is that the arrangement isn't rigid: there's a lot of freedom to slide spheres around. In fact you can rearrange the 12 spheres in any way you like by sliding them without intersecting, always touching the central sphere. So they don't have to be at the vertices of an icosahedron, like Fogberry sug--- I mean, like you suggested, Chief. That's one reason why the 8- and 24-dimensional versions are solved: the answers there are unique. It's aways easier to pin down an answer when there's only one of it, so to speak."

"Who cares?" said Mogul. "We know that in three dimensions, 12 is the maximum, and we're safe if we use an icosahedral arrangement. Cressida, get me Construc--- "

"Chief, you know I've been trying to tell you about what Cosmic News Network said this mor---"

"I've told you, I'm not inter---"

"You should be. Seems that the Olympus Expedition found ancient Martian remains, including some very strange machinery. Martian science seems to have been a bit weird. What they didn't realise is that the machinery was still working. One of them pushed a few buttons, and ---"

The ground seemed to shake without actually moving. Everything suddenly looked different, but exactly the same. It was very disconcerting. Cosgrove stopped. "Oh-oh," he said. "They were right."

"Right about what?" snapped Mogul. "Well? Out with it, man!"

"A dimension-quake. Mars has just become four-dimensional."

"OK, so we increase that to 24 transmitters," said Mogul bravely, but his face was as white as a sheet. Cosgrove shook his head sadly. The ground shook again.

"Make it between 40 and 46 transmitters, Chief. CosNN says that if we're lucky, the effect will stop at five dimensions. Though if it gets up to eight, or twenty-four, we'll be sitting pretty. Provided you're willing to finance 196,560 transmitters."

"Cancel that, Cressida," said Mogul, in a voice of unnatural calm. He stared at Cosgrove as if he were some form of primitive Martian fungus. Then he picked up the globe of Mars, and threw it at him.

FURTHER READING

John Horton Conway and Neil J.A.Sloane, Sphere Packings, Lattices, and Groups, Springer-Verlag, New York 1988.

John Leech, The problem of the 13 spheres, Mathematical Gazette 40 (1956) 22-23.

Andrew Odlyzko and Neil J.A.Sloane, New bounds on the number of unit spheres that can touch a unit sphere in n dimensions, Journal of Combinatorial Theory series A 26 (1979) 210-214.

K.Schlütte and B.L. van der Waerden, Auf welcher Kugel haben 5, 6, 7, 8, oder 9 Punkte mit Mindestabstand Eins Platz? Mathematicsche Annalen 123 (1951) 96-124.

Ian Stewart, How to succeeed in stacking, New Scientist 1777 (13 July 1991) 29-32.