##
Archive for **March 15th, 2022**

### Any limits to Math knowledge? Sort of “is there a solution” or are we wasting our dear patience on a non-existent solution? What is this Hilbert’s 10th problem?

Posted March 15, 2022

on:# Julia Robinson defined the limits of mathematical knowledge

## Born 100 years ago, she was key in solving Hilbert’s 10th problem

By** Evelyn Lamb**

NOVEMBER 22, 2019

Every December 8 for years, Julia Robinson blew out the candles on her birthday cake and made the same wish: that someday she would know the answer to** Hilbert’s 10th problem**.

Though she worked on the problem, she did not care about crossing the finish line herself. “I felt that I couldn’t bear to die without knowing the answer,” she told her sister.

In early 1970, just a couple of months after her 50th birthday, Robinson’s wish came true.

Soviet mathematician **Yuri Matiyasevich** announced that he had solved the problem, **one of 23 challenges** posed in 1900 by the influential German mathematician **David Hilbert.**

Matiyasevich was 22 years old, born around the time Robinson had started thinking about the 10th problem. Though the two had not yet met, she wrote to Matiyasevich shortly after learning of his solution, “I am especially pleased to think that when I first made the conjecture you were a baby and I just had to wait for you to grow up!”

The conjecture Robinson was referring to was one of her contributions to the solution to Hilbert’s 10th problem.

Matiyasevich put the last piece into the puzzle, but Robinson and two other American mathematicians did crucial work that led him there.

Despite the three weeks it took for their letters to reach each other, Robinson and Matiyasevich started working together through the mail in the fall of 1970. “The name of Julia Robinson cannot be separated from Hilbert’s 10th problem,” Matiyasevich wrote in an article about their collaboration.

Robinson was the first woman to be elected to the mathematics section of the National Academy of Sciences, the first woman to serve as president of the American Mathematical Society and a recipient of a MacArthur Fellowship.

She achieved all of this despite not being granted an official faculty position until about a decade before her death in 1985.

Robinson never thought of herself as a brilliant person. In reflecting on her life, she focused instead on the patience that served her so well as a mathematician, which she attributed in part to a period of intense isolation as a child.

At age 9, while living with her family in San Diego, she **contracted scarlet feve**r, followed by rheumatic fever.

Penicillin had just been discovered and was not yet available as a treatment. Instead, she lived at the home of a nurse for a year, missing two years of school.

Even after she rejoined her family, attended college and married, **complications from rheumatic fever** led to lifelong health problems, including the inability to have children.

After a much-wanted pregnancy ended in miscarriage, doctors told her another pregnancy could kill her. She had a** heart operation when she was around 40 years old** that improved her health, but she was never able to have the family she deeply desired.

Despite her accomplishments, Robinson was reluctant to be in the spotlight, only **consenting to tell her story for publication **near the end of her life.

The quotes attributed to Robinson in this article come from that record, an “autobiography” written by her older sister, Constance Reid, in close consultation with Robinson.

#### The 10th problem

Hilbert issued the first of his 23 challenges to the mathematics community during a lecture in Paris at the 1900 International Congress of Mathematicians.

The questions, which helped guide the course of mathematics research for the next century and through the present day, spanned several disciplines in mathematics, probing everything from the logical foundations of various branches of mathematics to very specific problems relating to number theory or geometry.

The 10th problem is a deep question about the limitations of our mathematical knowledge, though initially it looks like a more straightforward problem in number theory.

It concerns expressions known as Diophantine equations.

Named for **Diophantus of Alexandria**, a third century Hellenistic mathematician who studied equations of this form in his treatise *Arithmetica*, a Diophantine equation is a polynomial equation with any number of variables and with coefficients that are all integers. (An integer is a whole number, whether positive, negative or zero.)

### All about integers

The three circles to the right represent the Diophantine equations x^{2}+y^{2}=1 (black), x^{2}+y^{2}=2 (blue) and x^{2}+y^{2}=25 (orange). All three have integer solutions (marked as black dots where the circles cross intersections of grid lines). Yet there are some Diophantine equations with no integer solutions. And for others, mathematicians don’t yet know if integer solutions exist.

Examples of Diophantine equations include everything from simple linear equations such as 5x+y=7 (the variables are x and y, and their coefficients are 5 and 1) to the Pythagorean distance formula a^{2}+b^{2}=c^{2} (the variables are a, b and c, and their coefficients are all 1) to towering monstrosities in googols of variables.

Mathematicians are interested in whether Diophantine equations have solutions that are also integers.

For example, Pythagorean triples — sets of numbers such as 3, 4 and 5 or 5, 12 and 13 — are solutions to the equation a^{2}+b^{2}=c^{2}.

Some Diophantine equations have integer solutions, and some do not. While a^{2}+b^{2}=c^{2} has infinitely many integer solutions, the similar equation **a ^{3}+b^{3}=c^{3} has none **(except for solutions including zeros, which mathematicians consider uninteresting).

If an equation does have integer solutions, you do not need to be particularly clever to find them — you just need to be patient. A brute-force search will eventually give you numbers that work. (Of course, being cleverer may mean you can be less patient.)

**But if you do not know whether the equation can be solved in integers, you will never know whether your failure to find a solution is because none exists or because you have not been patient enough.**

Earlier this fall, mathematicians **Andrew Booker **of the University of Bristol in England and **Andrew Sutherland** of MIT announced that they had used a mix of clever algorithms and a powerful supercomputer to find that 42 = −80,538,738,812,075,974^{3} + 80,435,758,145,817,515^{3} + 12,602,123,297,335,631^{3}.

In other words, the Diophantine equation x^{3}+y^{3}+z^{3}=42 has an integer solution.

### Summing the cubes

For more than a century, mathematicians have been looking for integer solutions for the equation x^{3}+y^{3}+z^{3}=k, where k is a positive integer (such as 1, 2, 3 …).

As of 1955, **solutions had been found for 69 numbers **(blue) equal to or under 100, with another 22 (red) known to have no solutions. **Finding solutions for the remaining 9 numbers under 100 (highlighted in blue below in the year they were found) took until this year.**

This is one case of the more general question of which integers n can be written as the sum of three integer cubes: x^{3}+y^{3}+z^{3}=n. Forty-two was the last two-digit number for which mathematicians didn’t know whether there was a solution, but infinitely more numbers await integer solutions, if they exist.

**What Hilbert wondered in his 10th problem was how to tell whether an equation has integer solutions or not. Is there an algorithm — a terminating process yielding a yes-or-no answer — that can determine whether any given Diophantine equation has such a solution?**

A large part of the appeal of the 10th problem and related questions is sheer curiosity.

Do these often very simple polynomials have integer solutions? Why or why not? The answers generally do not have concrete practical applications, but the area of research is related in deep ways to theoretical computer science and the limits of what computer programs can do.

#### Unknowability

Robinson’s interest in Hilbert’s 10th problem started fairly early in what was an atypical mathematical career. She married **Raphael Robinson,** a mathematician at the University of California, Berkeley, not long after graduating from the university with a bachelor’s degree in mathematics.

UC Berkeley’s **anti-nepotism rules **prohibited her from working in his department. (Her situation was not uncommon for women in academia in the 1940s and 1950s.)

After earning her Ph.D. in math in 1948, also at UC Berkeley, she worked in industry and outside her field for a few years and volunteered for Democratic candidate Adlai Stevenson’s presidential campaigns. She also worked as an unofficial member of the UC Berkeley math department, using Raphael’s office and occasionally teaching classes.

Although she did not have the stability or salary of an official faculty position, she published in mathematics journals, both individually and with collaborators, and presented her work at conferences, often bringing a bicycle along.

She’d become an avid cyclist after her heart surgery, delighted by her ability to exercise after years of being perpetually short of breath.

When she was elected to the National Academy of Sciences in 1976, the university press office had to call the mathematics department to ask who Julia Robinson was.

UC Berkeley quickly made her a full professor. Robinson writes, “In fairness to the university, I should explain that because of my health, even after the heart operation, I would not have been able to carry a full-time teaching load.”

Shortly after she graduated with her Ph.D., her adviser, **Alfred Tarski,** mentioned a problem to Raphael, who in turn told Julia. This particular problem involved **Diophantine sets,** groups of integers that when substituted for one variable in some Diophantine equation would allow integer solutions in the other variables.

Consider the equation c−x^{2}=0, which has integer solutions for x only when c is a perfect square. Thus the perfect squares form a Diophantine set. The problem Raphael told Julia about was to determine whether the powers of 2 (2, 4, 8, 16 and so on — form a Diophantine set]. Through her work on that question, she found her way to the 10th problem.

Robinson first met **Martin Davis, **then an instructor at the University of Illinois at Urbana-Champaign, in 1950. “It started with our working on the same problem but from absolutely opposite directions,” says Davis, now age 91.

Both researchers had been looking at Diophantine sets. Davis was starting generally, trying to show that all sets with a** particular property called listability **were Diophantine.

Robinson was starting from the particular, trying to show that a few special sets — including prime numbers and the powers of 2 she had been working on — were Diophantine.

In 1959, Robinson and Davis started working together.

With **Hilary Putnam **of Princeton University, they kept pushing on the problem. Eventually they showed that all they needed was what Davis describes as a **“Goldilocks” equation**.

“The solutions aren’t supposed to grow too fast, and they aren’t supposed to grow too slowly,” he says. But that equation eluded them for almost a decade.

In the U.S.S.R., Matiyasevich had tried to tackle Hilbert’s 10th problem as a college student but abandoned it around the time he graduated in 1969.

Then a new paper from Robinson sucked him back in. “Somewhere in the Mathematical Heavens there must have been a god or goddess of mathematics who would Not let me fail to read Julia Robinson’s new paper,” he wrote.

He was asked to review it — a mere five pages about the relative growth of solutions to certain Diophantine equations in two variables. Her ideas immediately sparked new ideas for him, and he was able to produce the needed “Goldilocks.”

“It’s such a romantic thing — in the wider sense of the word romantic — that the four of us, such different people with different backgrounds, all together produced this piece of work,” Davis says.

Together, **they had shown that no all-purpose algorithm exists **to determine whether an arbitrary Diophantine equation has integer solutions.

But that isn’t the end of the story. Building on the work of Robinson and her colleagues, mathematicians continue to probe the boundary between knowability and unknowability. “Her work is still very relevant today,” says** Kirsten Eisenträger** of Penn State, a number theorist whose research is related to the 10th problem.

If Robinson were still alive on her 100th birthday this December, what problem would she be thinking about as she blew out her candles? The fact that there is no general algorithm for all Diophantine equations leaves many tantalizing questions open.

For example, does an algorithm exist for Diophantine equations of a certain form, say, multivariable cubic equations?

Mathematicians are also looking at what happens if you change the types of solutions sought for Diophantine equations.

One change is to ask the question for rational numbers: Is there a way to determine whether a polynomial equation with integer coefficients has any solutions that are **rational numbers**? (A rational number is the ratio of two whole numbers; 1/2 and −14/3 are two examples.)

Most experts believe that the answer is no, but mathematicians are far from a proof. One potential path to a solution involves building on work Robinson did in her Ph.D. thesis over 70 years ago.

In 1984, during her term as president of the American Mathematical Society, Robinson was diagnosed with leukemia. During a remission the next spring, while cycling with her sister, Robinson decided that Reid would write her life story, “**The autobiography of Julia Robinson.**”

Weeks later, the cancer had returned. Reid finished writing the record of Robinson’s life as her sister’s health deteriorated. Robinson died on July 30, 1985, at age 65.

“What I really am is a mathematician,” Reid writes on behalf of Robinson on the closing page. “Rather than being remembered as the first woman this or that,** I would prefer to be remembered, as a mathematician should, simply for the theorems I have proved and the problems I have solved**.”