## Monday, December 02, 2019

### Julia Robinson's 100th birthday

On Dec 8, 1919 Julia Robinson was born, so today is close to her 100th birthday (she passed away at
the age of 65 on July 30, 1985).

So time for some facts about her

1) She got her PhD from Tarski where she proved the undecidability of the theory of the rationals.

2) She is probably best known for her work on Hilbert's tenth problem (which we call H10)

In todays' terminology H10 would be stated as:

Find an algorithm that will, given p in Z[x_1,...,x_n] determine if it has an integer solution.

Hilbert posed it to inspire deep research in Number Theory. There are some cases that are
solvable (the topic of a later blog post) but the general problem is undecidable. This is not what Hilbert was aiming for. I wonder if he would be happy with the resolution.

The Davis-Putnam-Robinson paper showed that the decision problem for exponential diophantine equations was undecidable. It was published in 1961. The paper is here.  Martin Davis predicted that the proof that H10 was undecidable would be by a young Russian mathematician. He was proven correct when Yuri Matiyasevich supplied the missing piece needed to complete the proof.

I often read `H10 was resolved by Davis-Putnam-Robinson and Matiyasevich' or sometimes they put all four names in alphabetical order. I like that--- it really was a joint effort.

3) She was inducted (a proof by induction?) into the National Academy of Sciences in 1975.

4) She was elected to be president of the American Math Society in 1982.

5) She got a MacAuthor Fellowship prize in 1985 (Often called the MacAuthor Genius award.)
At the time it was worth \$60,000.  Its now \$625,000.

6) She also did work in Game Theory. Her paper An Iterative Method of Solving a Game, which is
here, is a proof from the book according to Paul Goldberg's comment on this post.

7) The Julia Robinson Math Festival is named in her honor (hmmm- is that a tautology?) Its purpose is to inspire K-12 students to get involved in math. For more on it see here.

8) (ADDED LATER) Commenter David Williamson pointed out that Julia Robinson did work on the transportation problem. See his comment and his pointer to the paper.

(ADDED LATER) When I hear Julia Robinson I think Hilbert's 10th problem.  I suspect many of you do the same. However, looking at items 6 and 8 above, one realizes that she did research in non-logic branches of math as well.

1. Fine so far, just correct the spelling:
Yuri Vladimirovich Matiyasevich (Ю́рий Влади́мирович Матиясе́вич).
Born March 2, 1947. As you are interested in undergraduate research it may be worth noting that he won a gold medal (absolute rank 7) in the 1964 IMO and in 1966 he presented a talk at International Congress of Mathematicians held in Moscow. He was a second-year undergraduate student at that time. This was prior to his final blow on H10 which was published in 1970.

1. Thanks for correction and additional information!

2. Regarding (6), her proof that Fictitious Play converges for zero-sum games, is a "proof from the Book".

1. I have added both a pointer to the article and your comment to the post. Thanks!

3. She also figured out that for the transportation problem, the flow is optimal if and only there are no negative-cost cycles in the residual graph. It's in a RAND technical report from 1950.

1. Great!
Do you have a pointer to the paper, or to a paper that describes that paper?

2. I've posted it at https://people.orie.cornell.edu/dpw/Robinson50.pdf.

3. Great! I have added to the post to include this information.

4. I live next door to where Julia (and Rafael) used to live. I never knew her, but I used to talk to Rafael a fair amount. Their house was constructed and furnished to be perfect for 2 mathematicians. In fact, I have a table that Rafael gave me that has two shelves on opposing sides that was constructed for some reason that I no longer remember that made it easier for 2 scholars to use.