Ahlfors and Beurling

Posted on 2012/07/28 by wdjoyner

This is an exposition on Ahlfors and Beurling, two mathematicians I admire. There is nothing original at all. Everything below is collected from Beckman’s excellent book [B], Wikipedia, and papers which I found on the internet using google searches.

The universe consists of Nine Worlds which are resting on an immense tree called Yggdrasil. Asgard is one of the Nine Worlds and is the country of the Norse Gods. Asgard is a land more fertile than any other, blessed also with a great abundance and its people excelled beyond all others in strength, beauty and talent. Odin is a major god and the ruler of Asgard. Odin has many great sons, among them, the brothers Baldur and Tyr. – Nortic legend

The tree Yggdrasil

Lars Ahlfors and Arne Beurling are among the greatest mathematicians in history. Eventually, they became became collaborators in research, and the best of friends.

Ahlfors

Baldur (or Baldr, Balder) is the god of innocence and piety. So bright and fair he is that light shines from his features. He is wise, eloquent, gentle, and righteous to such a degree that his judgments stand always unshaken. – Norse Legend

Finland was a part of Sweden from the 12th to 19th century and from 1809 to 1917 was part of the Russian Empire, although given some autonomy. The Parliament of Finland passed a Declaration of Independence from Russia in 1917, approved a month or so later by the Russian government. Finland fought World War II as essentially three separate conflicts:

the Winter War (1939-40), against the Soviet Union which forced Finland to cede 11% of its pre-war territory and 30% of its economic assets to the Soviet Union,
the Continuation War (1941-44), against the Soviet Union which forced Finland to pay $ 226,500,000 in reparations to the Soviet Union, while ultimately retaining its independence, and
the Lapland War (1944-45), against Nazi Germany.

Lars Ahlfors was born in Helsinki, Finland in 1907 during a time when Finland was under Russian rule. Sadly, his mother died in childbirth. His father was a Professor of Engineering at the Helsinki University of Technology. Ahlfors studied at University of Helsinki from 1924, graduating in 1928 having studied under Ernst Lindelöf and Rolf Nevanlinna. (Nevanlinna replaced Weyl in Zurich for the session 1928/29 while Weyl was on leave, and Ahlfors went to Zurich with him.) He completed his doctorate from the University of Helsinki in 1930. After he presented his doctoral thesis in 1930, he made a number of visits to Paris and other European centers from 1930-1932. He also taught (in Swedish) at Aaboe Academy in Turku from 1929 to 1932.

Ahlfors worked as an Associate Professor at the University of Helsinki from 1933 to 1936. In 1935-1938 Ahlfors visited Harvard University. From 1938-1943 he was a professor at the University of Helsinki.

As a Finn, he was required to serve in the military, for which he worked in a bomb shelter.

World War II presented many problems for Ahlfors and his wife and children. Due to travel restrictions and threats to his family, his wife and children left for Sweden early in the war, leaving Ahlfors behind. He left when he could and was professor at the Swiss Federal Institute of Technology at Zurich from 1945-1946 (he was only there for 1 year, though he was offered the post earlier). From 1946-1977, Ahlfors was professor at Harvard. He was the William Caspar Graustein Professor of Mathematics of Harvard from 1964-1977.

In 1936, the year the first Fields medals were awarded, he was one of the first two people to be given the Medal. He was an invited speaker at the ICM in 1962 and in 1978. He was selected for the Wihuri Sibelius Prize [W] in 1968, the Wolf Prize in Mathematics in 1981, and the AMS Steele Prize in 1982.

For a student of mathematics, a common introduction to Ahlfors was by reading his classic textbook on complex analysis which is still very highly regarded. It was Complex Analysis: an Introduction to the Theory of Analytic Functions of One Complex Variable.

Ahlfors’ first famous result was his proof of Denjoy’s conjecture, discussed next. If $f:{\mathbb{C}} \to {\mathbb{C}}$ is a function, the function $M(r, f) = \max_{0\leq \theta\leq 2\pi} |f(re^{i\theta} )|$ is called the maximum modulus of $f$ . The order of $f$ is

$\rho= \limsup_{r\to\infty} \frac{\log\log M(r,f)}{\log r}.$

For example, if $f(z) = e^{z^k}$ then we have $\rho=k$ . We say $f$ has an asymptotic value $\alpha$ if there is a curve $\Gamma$ connecting $0$ to $\infty$ such that $f (z) \to \alpha$ as $z \to \infty$ on $\Gamma$ . Denjoy (1907) asked the question “if $f$ has $k$ distinct finite asymptotic values, is the order of $f$ greater than or equal to $k/2$ ?” In his PhD thesis, Ahlfors proved the answer is yes.

Ahlfors also worked with Beurling on several papers, which shall be discussed below. Later in his career, Ahlfors worked on Kleinian groups, sometimes in collaboration with Lipman Bers.

A Kleinian group $G$ is a discrete subgroup of $PSL(2, {\mathbb{C}}).$ The group $PSL(2, {\mathbb{C}})$ of $2 \times 2$ complex matrices of determinant $1$ modulo its center may be represented as a group of conformal transformations of the Riemann sphere. The boundary of the closed ball is called the sphere at infinity, and is denoted $S_\infty$ . Consider $G$ as orientation preserving conformal maps of the open unit ball $S_\infty$ in ${\mathbb{R}}^3$ to itself. The orbit $Gp$ of a point $p$ will typically accumulate on the boundary of the closed ball. The set of accumulation points of $Gp$ in $S_\infty$ is called the limit set of $G$ . A Kleinian group is said to be of type $1$ if the limit set is the whole Riemann sphere, and of
type $2$ otherwise.

One of Ahlfors’ most well-known results is his “finiteness theorem,” which says that the ordinary set $\Omega$ of a (finitely generated) Kleinian group $G$ factored by the action of the group is an orbifold $\Omega/G$ of finite type. In other words, $\Omega/G$ has finitely many “marked” points and can be compactified by adding a finite number of points.

Ahlfors has remarked that perhaps of greater interest than the theorems that he has been able to prove were the ones he was not able to prove. For example, there is the assertion that the limit set of a finitely generated Kleinian group has two-dimensional Lebesgue measure zero. This has become known as the Ahlfors measure zero conjecture. It is still unsolved.

Beurling

Tyr is the god of war and he does nothing whatever for the promotion of concord. Tyr is bold and courageous – men call upon him in battle, and he gives them courage and heroism.

The eastern half of Sweden, present-day Finland, was lost to Russia in 1809. The last war in which Sweden was directly involved was in 1814, when Sweden by military means forced Norway into a personal union. Since then, Sweden has been at peace, practicing “non-participation in military alliances during peacetime and neutrality during wartime.”

During the German invasion of the Soviet Union, Sweden allowed the Wehrmacht to use Swedish railways to transport (June-July 1941) the German 163rd Infantry Division along with howitzers, tanks and anti-aircraft weapons and associated ammunition, from Norway to Finland. German soldiers traveling on leave between Norway and Germany were allowed passage through Sweden. Iron ore was sold to Germany throughout the war. And for the Allies, Sweden shared military intelligence and helped to train soldiers made up of refugees from Denmark and Norway. It also allowed the Allies to use Swedish airbases between 1944 and 1945.

Arne Carl-August Beurling (February 3, 1905 – November 20, 1986) was a Swedish mathematician and professor of mathematics at Uppsala University (1937-1954) and later at the Institute for Advanced Study in Princeton, New Jersey.

He was awarded the Swedish Academy of Sciences Prize 1937 and 1946, the Celsius Gold Medal 1961, and the University of Yeshiva Science Award 1963. In his honor a “Beurling Year” was held at the Mittag-Leffler Institute (Beurling was offered the directorship of the MLI but turned it down…) in Stockholm 1976/77.

Family: Father – Konrad Beurling; Mother – Elsa Raab Beurling (who divorced Konrad in 1908 and went back to using Baroness Elsa Raab); Great grandfather (on father’s side) – Pehl Beurling, whose father was a famous clock-maker. According to Beckman [B], Konrad had 14 children in wedlock, and “an unknown number” out of wedlock. (I don’t know if “unknown” means Konrad didn’t know or Beckman didn’t know:-)

Arne graduated high school in 1924 and went to the university in Uppsala. He got his undergaduate degree in 1926, masters in 1928.

In 1925 the Swedish General Staff contacted a commercial company to design a machine that would be superior to the German Enigma. Hagelin developed a prototype for evaluation called the B21. The B21 was approved for the Swedish General Staff and Hagelin also sold the machine to several other countries.

While working on his PhD, Beurling did his military service, excelling in a course in military cryptanalysis. In fact, this is a considerable understatement. Towards the end of the course, the instructor, a Naval officer named Anderberg, brought in a commercial crypto-machine, the Hagelin B21. The graduate student Beurling modestly asked if he could examine the machine over the weekend. The instructor okayed this simple request. The following Monday, Beurling told Anderberg that the machine had a weakness. Anderberg denied this claim and challenged him with a long crib. Beurling promply decrypted it, stunning Anderberg.

Some of Beurling’s other cryptographic feats:

Beurling broke the Geheimschreiber without having a copy of the
machine (see pp. 43-86 of Beckman [B]). (As the Geheimschreiber encrypted very high-level Nazi traffic, the military significance of this cannot be underestimated.)
Beurling broke several encrypted telegrams in Czech,
a language he did not know (see pp. 109-113 in Beckman [B]).

In mid-June 1941 Sweden told Great Britian of Germany’s plan to attack the Soviet Union, the attack to commence in late June 1941 (“Operation Barbarossa” – see pp. 120-121 in Beckman [B]). A spy then communicated this information to the Soviet Union (see Ulfving and Weierud [UF], page 22). At the time, the Soviets did not believe the information, thinking the British were only trying to trick them into attacking the Germans.

Beurling started teaching in the mathematics department of Uppsala University in 1932. His PhD was defended in 1933, though most of it was written much earlier. (He went on a long hunting trip with his father to Panama. Also, he did his military service at this time.) Beurling’s thesis contained a proof of the Denjoy conjecture, whose proof was found independently and published in his PhD by Ahlfors a few years earlier. Except for visiting positions, he stayed at Uppsala until he left to go to the Institute for Advanced Study in the 1950s.

A photo of Beurling taken by Annette-Marie Yxkull.

Consider a plane region $D$ and let $E$ be a subset of the boundary of $D$ . Consider a harmonic function in $D$ , denoted by $\omega (z,E,D)$ and known as the harmonic measure at $z$ of $E$ with respect to $D$ . It is defined by having boundary values $1$ on $E$ and $0$ on the rest of the
boundary. If it is known that $|\log f(z)|\leq \omega$ on the whole boundary, then, by the maximum principle, $|\log f(z_0)|\leq \omega(z_0,E, D)$ , for every interior point $z_0$ .

A difficult and important result is Beurling’s estimate for the harmonic measure expressed through the inequality

$\omega \leq \exp(-\lambda^2+1),$
where $\lambda =\lambda (z_0, E, D)$ is the extremal distance between $z_0$ and the boundary set $E$ . If $E$ is conformally equivalent to an arc on the unit circle there is also an opposite inequality

$\omega \geq \exp(-\lambda^2).$
These inequalities were strong enough for a proof of the Denjoy conjecture (independent of that of Ahlfors) concerning the number of asymptotic values of an entire function of finite order.

This may be Beurling’s most famous theorem: Let $H^2$ be the Hilbert space of holomorphic functions in the unit disk which belong to $L^2$ on $|z|= 1$ . Let $E$ be a closed subspace, invariant under multiplication by $z$ . Then there exists an inner function $\phi(z)$ , i.e. $|\phi(z)|<1$ , $|\phi(e^{i\theta})|=1$ a.e., such that $f\in E$ if and only if $f=\phi\cdot f_0$ , with $f_0\in H^2$.

Beurling’s first paper in harmonic analysis is an extension of the prime number theorem to generalized primes. Let $P: 1<p_1<p_2< \dots$ be the given sequence of "primes" and let

${\mathbb{Z}}_P = \{ p_1^{a_1}\dots p_k^{a_k}\ |\ a_i\in {\mathbb{Z}}\}$
be the "integers". Let $\pi_P (x)$ and $N_P(x)$ be the corresponding counting functions. Then $|N_P(x)-ax| 0$ , implies the prime-number theorem $\pi_P(x)\sim x/\log x$ if $\gamma >3/2$ but in a sense not if $\gamma <3/2$ .

If $P$ satisfies $\pi_P(x)\sim x/\log x$ then we call $P$ a Beurling prime number system. A question raised by Beurling remains open: what functions $E(x)$ are such that $|N_P(x)-x|0$ , then Olofsson [O] conjectures that

$\limsup_{x\to\infty} \frac{N_P(x)-x}{\ln x} >0,$
provided $P$ is different from the rational primes. Olofsson conjectures that Beurling’s question is addressed by any function $E(x)$ satisfying $E(x)=o(\ln x)$ .

This is just a small sampling of Beurling’s brilliant work.

Ahlfors and Beurling

Ahlfors once wrote “Arne Beurling was the best friend I ever had.” Ahlfors enjoyed the quiet life of a writer and mathematician, whereas Beurling loved the outdoors, sailing, hunting. They first met in 1934 at the Scandanavian Congress of Mathematicians held in Stockholm. They were both still single, although Ahlfors would marry the following year. Beurling had just gotten his PhD the previous year. After the 1934 Congress, while Ahlfors was still at Mittag-Leffler, he would often take the train up to Uppsala to visit Beurling. Much later, when Ahlfors was at Harvard, Beurling’s girlfriend Annette-Marie Yxhull wrote Ahlfors a latter, explaining how unhappy Beurling was at Uppsala (see Beckman [B]). Ahlfors acted quickly, obtaining a visiting position for his friend at Harvard. Later, Beurling was given a permanent position at the Institute for Advanced Study, no doubt with Ahlfors’ strong recommendation.

A photo of Ahlfors taken by A. Beurling.

Beurlings work with Ahlfors was in the field of quasiconformal mappings. Let $f:D \to D'$ be an orientation-preserving homeomorphism between open sets in the plane. If $f$ is continuously differentiable, then it is $K$ -quasiconformal if the derivative of at every point maps circles to ellipses with eccentricity bounded by $K$ . We say $f$ is quasiconformal if $f$ is $K$ -quasiconformal for some finite $K$ .

A quasiconformal map.

According to Ahlfors, in their joint paper [AB], the decisive idea was entirely due to Beurling. It deals with the boundary values of quasiconformal mappings. If $h(x)$ increases for $-\infty <x1$ ,

$1/\rho \leq \frac{h(x+t)-h(x)}{h(x)-h(x-t)} \leq \rho,$
for all $x$ and $t$ .

Bibliography

[AB] L. V. Ahlfors and A. Beurling, The boundary correspondence under
quasi-conformal mappings, Acta Math., 96 (1956), 125-142.

[B] B. Beckman, Codebreakers, AMS, 2002.

[O] R. Olofsson, Properties of the Beurling generalized primes, preprint, 2008.

[UF] The Geheimschreiber Secret, by Lars Ulfving, Frode Weierud, in Coding Theory and Cryptography: From Enigma and Geheimschreiber to Quantum Theory, Springer-Verlag, 2000.
paper in pdf or link at Frode’s cryptocellar

[W] Wihuri Sibelius Prize

The man who found God’s number

Posted on 2012/07/06 by wdjoyner

(added Sep. 2014: An updated version of this article will appear in the College Math Journal.)

We have an appetite for information, and especially for pattern, information that falls into meaningful arrays from which we can make rich inferences. Information can be costly to obtain and analyze, but because it offers an invaluable basis for action, nature evolves senses and minds to gather and process information appropriate to particular modes of life. Like other species, humans can assimilate information through the rapid processing that specialized pattern recognition allows, but unlike other species we also seek, shape, and share information in an open-ended way. Since pattern makes data swiftly intelligible, we actively pursue patterns…

Brian Boyd
(On the Origin of Stories, [B])

Introduction

The Rubik’s cube was a world-wide obsession in the early 1980, when Tomas Rokicki, a high school junior in Texas, got his first one. Around the same time, Tom began losing his sense of hearing.

During the 1980s there were Rubik’s cube solving contests (some even televised) but no one knew the smallest number of moves needed to solve the cube. This mysterious quantity, “God’s number,” was the number of moves needed to solve the cube in its most scrambled state. Although David Singmaster, cubologist extraordinaire, guessed it might be in the low 20s, no one had a serious conjecture as to what God’s number would actually be. The cube solving contest winners relied on knowing various solving strategies and very fast finger movement.

During that era, hearing aids were very primitive and no one knew how to restore hearing to those who were totally deaf. In the 1970s-1980s, hearing aids were so-called “in the ear” transistor devices. By the time Tom got his first one in the 1980s, they were small earbuds which fit inside the ear, but not reaching into the ear canal [T]. Unfortunately, the device was useless unless you had at least some hearing ability.

We do know, thanks to Tom Rokicki’s recent work, the value of God’s number (explained below). This was a very difficult problem to solve. Also, we do know, due to decades of work by many researchers, how to restore hearing to the totally deaf [W]. Thanks to two double cochlear implant surgeries, that Tom’s hearing is almost fully restored. Digitizing human hearing is a very difficult problem to solve.

The Rubik’s cube

The Rubik’s cube, or simply the cube for short, was unleashed on the world in the
mid 1970’s. It became a sensation world-wide but is still remains a popular mechanical puzzle for people of all ages. For the sake of orientation, here is a short description. Image a cube sitting on a table. This cube has six faces: up, down, left, right, front and back. Color each of the six faces with a different color. Now cut up the cube into 27 subcubes of equal size using slices parallel to the faces. In the mid 1970s, Erno Rubik, a Hungarian professor of architecture and design at a university in Budapest, did just this but also figured out an ingenious internal mechanism for connecting the 26 external subcubes in a way that allows them to be rotated around a center. This mechanism allows each face to be rotated by $90^o$ or $180^o$ or $270^o$ , clockwise or counterclockwise. The effect of this is that the centers of the faces do not change. If you imagine the front face of the cube as always facing you and that you are holding the cube with your right hand on the right face, the the total number $N$ of different positions that the cube could be scrambled is

$N = 8!\cdot 12!\cdot 2^{10}3^7=43252003274489856000 \cong 4.3\times 10^{19},$
or about 43 billion billion positions (see [J]). In the sense of Brian Boyd’s quotation, the Rubik’s cube is full of “patterns.”

Imagine having to search through this. How does it compare with finding a needle in a haystack? A straw of hay is about 1 gram. For a 200 pound haystack, that works out to about $100000=10^4$ straws in a haystack. In other words, finding a needle in a haystack is $10^{14}$ (“ten thousand billion”) times easier. How does it compare to the gross domestic product of the United States economy? This number $N$ is over one million times the size of the United States GDP. How does it compare to the distance to the moon in the sky? If you stacked sheets of paper on top of each other until their thickness grew to the moon, the number of sheets you uses would be over a million times smaller than this number $N$ . How does it compare to searching the largest publically known database that arose in commerce or government? The largest such database is at the World Data Centre for Climate [F], weighing in at about $6$ petabytes, or $6\times 10^{15}$ . Imagine having to search through this. The “Rubik’s cube database” is over $1000$ times larger. This number of cube positions is a very big number. This is what Tom is trying to search through.

I do not recall who gave me the cube, but I do remember quite clearly trying to solve it, and being surprised at how difficult it was. For months I tried to solve it, on and off, and just could not restore it; I could get two layers, but the last layer was just too difficult. Finally, I started keeping a notebook on the cube, and looked for some sequences (algorithms, I now know they are called) that would affect only a small portion of the cube, leaving the rest alone. At one point I had all the algorithms I needed except the one that permuted three corners. With a bit more work I finally figured out those pesky corners, and had a full solution. It took me about six months from originally getting the cube until this point! I did top corners first, then bottom corners, then top and bottom edges, and finally middle edges.

– Tom Rokicki

Since the late 1970’s, mathematicians and computer scientists have been wondering how many moves do you need to make to solve the Rubik’s cube, in the worst case scenario. There are two ways to measure the number of moves you make while manipulating the cube. One is called the quarter-turn metric. In this measurement, each quarter turn of any face of the cube, whether clockwise or counterclockwise, is called one move. The other is the face-turn metric. In this measurement, each turn of any face of the cube, whether by $90^o$ or $180^o$ or $270^o$ in either direction, is called one move. The use of the word “metric” is designed to suggest distance. How far from the solved position of the cube can you get? Starting from the solved position, how many moves would you have to make to scramble the cube into a position which is further from that solved position than any other? The answer depends on which metric you use. The exact answer is known as God’s number in the face-turn metric (resp., in the quarter-turn metric, if you prefer that measurement).

The determination of God’s number was the Mount Everest of mathematical questions
connected with the Rubik’s cube. With over $4.3\times 10^{19}$ possible positions, one might think that God’s number could be very large.

Hearing loss

The human ear is a complicated organ. In rough terms, here is how the hair cells in the inner ear contribute to hearing. Sound is basically a vibration of the molecules of the air created by small differences in air pressure. Different sound frequencies create different pressure differences. Deep inside the ear, in an area called the cochlea, is a surface called the basilar membrane of the inner ear. In very rough terms, you can think of this surface as like your skin with hair on it. When it experiences a sound, the hair on it will vibrate. Remarkably, different frequencies will cause hair in different locations on this surface to vibrate. It is as though a high-pitched frequency would vibrate the hair on your legs and not your arms, but a low-pitched frequency would vibrate the hair on your arms and not your legs. This “frequency-to-place” mapping is the way the ear sorts out different frequencies, enabling our brain to process that sound. In a normal ear, high-frequency sounds are registered by the hair cells located at the shallower end of the cochlea, but low frequency sounds are registered by the hair cells further inside. When these hair cells vibrate, they create a tiny electrical impulse which the nerve cells in the basilar membrane pass to the brain. The brain interprets this activity to determine which sound frequency is being heard.

If you lack hair cells, then this process completely breaks down and you cannot distinguish frequencies. The most beautiful music is merely noise.

Tom’s hearing

As Michael Chorost explains in his book Rebuilt [Ch], some teenagers in the 1980s developed hearing problems due to the fact that, in the United States, there was a Rubella outbreak in the 1960s. One of the consequences of this virus
was that some pregnant women exposed to Rubella gave birth to babies who were more likely to gradually lose cochlear hair cells starting in the 1980s during their teenage years. However, other illnesses can cause hearing loss and the cause of Tom’s hearing problems is not known.

Tom graduated from Wolfe City High School in 1981, got a bachelors degree in electrical engineering from Texas A+M University in 1985, and a Ph.D. at Stanford University in Computer Science in 1993. While this was going on, Tom was becoming deaf. Here is how he describes it:

I am post-lingually progressively deafened. I started losing my hearing in high school (no cause is known), and in college it became a huge problem. A very good friend’s parents noticed how deaf I was and sprung for hearing aids for me (I was working my way through school at the time; no way I could afford them) and they helped a lot but school was still a challenge. Once I started working full-time I could afford more and better hearing aids, but as the aids got better my hearing got worse, until I reached a point that hearing aids weren’t really helping much at all.

Recent progress on God’s number

As long ago as the early 1980’s it was known that every position the cube could be solved in $52$ moves or less [C20]. Here is a table of progress since then.

	Lower	Upper
Date	bound	bound	Notes and Links
July, 1981	18	52	Morwen Thistlethwaite
Dec., 1990	18	42	Hans Kloosterman
May, 1992	18	39	Michael Reid
May, 1992	18	37	Dik Winter (just one day later!)
Jan., 1995	18	29	Reid (analyzing
			Kociemba’s two-phase algorithm).
Jan., 1995	20	29	Reid: the “superflip” position
			(This is the position of the Rubik’s cube where the centers and corners are correct, and all edges are correctly placed but “flipped.”) requires 20 moves.
April, 2006	20	27	Silviu Radu
May, 2007	20	26	Dan Kunkle and Gene Cooperman
March, 2008	20	25	Tomas Rokicki
Aug., 2008	20	22	Rokicki and John Welborn
July, 2010	20	20	Rokicki, Herbert Kociemba, Morley Davidson,
			and John Dethridge determine God’s number!

For years, Tom Rokicki has been working on lowering the upper bound for the face turn metric of the Rubik’s cube. His main work (finished in March 2008) is described in [TR], using a mathematical field known as group theory and prodigious programming skills. In Tom’s own words:

In December of 2003 I decided to solve the “edges-with-centers” space (the entire space of Rubik’s cube, ignoring all the corners). I wrote all of the code in C++ using a new set of classes for representing positions, sequences, and symmetry. The program itself required only 1.3GB of RAM, and I posted the results to the Yahoo newsgroup speedsolving in January 2004. This was the largest such complete implicit graph search performed to date at that time, I believe, with 980 billion states (before symmetry and antisymmetry reductions).

In November of 2005, I got an email from Silviu Radu that he had used the “edges-with-centers” results I had posted to lower the upper bound on God’s number in the quarter turn metric to 38. This email started a collaboration that, in the end, led to all the rest of the work. My debt to Silviu is profound.

Many others were also working on this problem, but Rokicki’s progress in early 2008 was so significant that Rubik’s cube aficiadados started to think Rokicki was about to make a first ascent on their own Mount Everest. In fact, it was soon afterwards that Sony’s John Welborn contacted Tom out of the blue and offered CPU time on the “farm” of computers which Sony Imageworks uses to render animated movies, such as “Spiderman 3.” As a result of this generous offer by Sony, Tom was able to extend the same method used in the $25$ -move upper bound to show, in the face turn metric, every position can be solved in $\leq 22$ moves.

Then Google called. They donated time on a supercomputer to rule out the cases $N=21,22$ . This meant God’s numbr was $\leq 20$ . On the other hand, the “superflip” position is known to take $20$ face moves exactly (Michael Reid established this in 1995), so $20$ is best possible. In other words, God’s number in the face turn algorithm is $20$ . What Tom did was great but, with a little help from some friends, an amazing milestone was achieved.

Cochlear implants

What a cochlear implant tries to do is generate tiny electrical impulses in the nerve cells of the basilar membrane by attaching small electrical wires to different locations where hair cells should be. Even though the cochlear implant is very small, it cannot match mother nature. In a normal human ear, there are about $20000$ hair cells. There is no way to surgically implant $20000$ electrical nodes in the small area of the human skull where the inner ear is located. However, even 25 electrodes, which is the current state of the art, can transform a deaf person’s life from noise (or silence) to meaningful sound. The implanted electrodes get “mapped” or “programmed” to nerve cells of the basilar membrane by an audiologist working closely with the patient. For some patients, the process of installing and mapping a functioning “bionic ear” goes fairly smoothly. For others, it can be a very frustrating experience.

How does the cochlear implant distinguish the frequencies which are then passed to the implanted electrodes? Sound waves can be “decomposed” into more basics sounds called fundamental harmonics. As a rough analogy, think of the sound from a piano chord, which can be decomposed into the sounds of its individual keys. Each of the individual piano keys makes a more fundamental, pure sound. Play them simultaneously, as you do when playing a piano chord, and you get a more complicated sound. Now, try to reverse this process. Listen to the sound of a complicated chord. How do you tell what the individual notes are? Assuming you are not a musician who knows the chords by heart, this question of decomposing a chord into individual key notes is a complicated one. Abstractly, the process of decomposing sound into fundamental harmonics uses the mathematics of Fourier analysis, a method physicists and mathematicians have known since the 1800s. However, mathematics and engineering are not the same. Implementing these procedures in a tiny hardware device which is small enough to allow it to be surgically implanted in your skull behind your ear is still a very difficult, but actively researched, problem. Many engineers and scientists are developing new techniques, with improvements in hearing devices being discovered every year.

At some point Tom’s hearing got so bad that hearing aids no longer helped. Here is how Tom described what happened next.

I went in, and they said I might be a candidate for cochlear implants; I got implanted, and now I am hearing so much better! (If not normally.) It is hard to put into words how much better I hear now; it is like someone turned on the lights after I had spent years stumbling in the dark. Absolutely and truly a miracle in my life.

Tom Rokicki had his first surgery for a cochlear left-side implant in March 2008, just before he published his $25$ move upper bound for God’s number, in the face-turn metric. His surgery in March 2011, about 8 months after establishing the $20$ move result, was for the right side. It was so successful, that he listens to audio books in the car on the way to work in the morning. As Tom says, miraculous.

Today

The question remains – how many moves do you need to make to solve the Rubik’s cube in the worst case scenario, in the quarter turn metric? In this case, there is a position which is known to require $26$ quarter turn moves, namely, the “superflip with 4 spot” position (the position of the Rubik’s cube where the corners are correct, and all edges are correctly placed but “flipped,” and 4 of the 6 corners are permuted) also established in 1995 by Michael Reid. In the quarter turn metric, the answer is unknown at this time.

Will the improvements in implants ever make Tom’s hearing as good as a normal person? Time will tell.

[B] Brian Boyd, On the Origin of Stories: Evolution, Cognition, an Fiction, Harvard Univ. Press, Cambridge MA, 2009.

[C20] Cube 20 website http://cube20.org/

[Ch] Michael Chorost, Rebuilt: My Journey Back to the Hearing World, Mariner Books, 2006

[F] Article on large databases:
http://www.focus.com/fyi/10-largest-databases-in-the-world/

[J] David Joyner, Adventures in Group Theory, 2nd ed., Johns Hopkins Univ. Press, 2008.

[TR] Tomas Rokicki’s website http://tomas.rokicki.com/

[T] Bernard Becker Medical Library, Washington University School of Medicine, Timeline of Hearing Devices and Early Deaf Education,
http://beckerexhibits.wustl.edu/did/timeline/

[W] Wikipedia article on Cochlear implants:
http://en.wikipedia.org/wiki/Cochlear_implant#History

[W2] Wikipedia articles on the Rubik’s cube:
http://en.wikipedia.org/wiki/Rubiks_Cube
http://en.wikipedia.org/wiki/Gods_algorithm
http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubiks_Cube

Many thanks to Tom Rokicki for his many very helpful correspondences!

Yet Another Mathblog

Monthly Archives: July 2012

Ahlfors and Beurling