Julia Robinson Centennial and the Mathematical Tale of Hilbert's 10th Problem

The month of December in the San Francisco Bay Area was foggy, cold and wet. A warm remarkable Mathematical tale however was awaiting as I arrived at the former house of Julia Robinson, perched at the top of a hill at Kensington, California.

The celebration of Julia Robinson Centennial kickstarted at Julia's former house with a reception organized by Nancy Blachman who founded the Julia Robinson Mathematics Festival (JRMF). It was a marvelous evening as I made new friends (math circle friends at the Bay Area, Howard Landman, Manuel Blum and his wife Lenore Blum who just retired from CMU) and catching up with old friends (Mark Saul and Nancy Blachman). I was especially delighted to get the autograph of Martin Davis and Yury Matiyasevich who were Julia's former collaborators. The celebration continued the next day with a Symposium in Honor of Julia Robinson's 100th Birthday organized by the Mathematical Sciences Research Institute, where prominent speakers e.g., Lenore Blum (who was Julia's former postdoc), Martin Davis, Yury Matiyasevich shared more on the highlights of Julia's mathematical quest. After her death, Julia's husband, Raphael M. Robinson, also an eminent mathematician at UC Berkeley, created the Julia Bowman Robinson Fund for scholarships for graduate students at Berkeley, which received the bulk of the Robinsons' estate (the sale of Julia's former house) upon his death. The charitable Robinson mathematicians were truly highly remarkable persons.

Julia Robinson was instrumental in resolving Hilbert's 10th problem, together with American mathematicians, Martin Davis, Hilary Putnam. Hilbert posed his 10th problem along with twenty two others in 1900, now famously known as Hilbert's problems. And this 10th problem was finally closed in 1970 by a young Russian mathematician Yuri Matiyasevich who built on the work of Robinson, Davis and Putnam. Out of Hilbert's 23 questions, this 10th problem was the only decision problem, asking for a computational procedure to determine the solvability of a Diophantine equation. Martin Davis' prediction that "Julia Robinson's conjecture is true and it will be proved by a clever young Russian" essentially came true. It was truly remarkable how leading mathematicians on both sides of the Iron Curtain could come together to complement each other's work in resolving Hilbert's problem seventy years after it was first posed. Lenore Blum's Public Lecture "Julia Robinson: Personal Reflections, Her Work and Time" gave a very comprehensive overview of the mathematical quest and Julia's personality. These mathematicians and logicians laid down very strong foundations for theoretical computer science as computer science becomes a mainstream academic discipline mushrooming in universities starting in the seventies.

To show that Hilbert's 10th problem has no solution (i.e., no such algorithm exists) was a tour de force of mathematics and logic, requiring the invention of new mathematical tricks, connecting revolutionary concepts (Turing's halting problem with Diophantine equations in number theory) and the discoveries of new properties of the Fibonacci numbers (properties overlooked for centuries and discovered by Yuri Matiyasevich). What struck me the most was that to those Diophantine equations that do have a solution (and therefore an algorithm to determine the solution), the quest for the algorithm by extraordinary mathematicians since ancient times is equally exciting!

Here, I'll point out some of these special cases. The linear Diophantine equation in two variables was solved completely many years ago by Diophantine (who else?) and relies on the Euclid's algorithm. This Diophantine equation is a mathematical statement that links the prime decomposition of natural numbers with the solvability of the equation (the notion of solvability means a computable program): Two natural numbers, say a and b, are relatively prime if and only if the linear Diophantine equations with integral variables x and y: ax+by =1 has a solution. The Euclid's algorithm is fundamental to its solution. Next, moving to the nonlinear world, another special case is the Pell's equation, which can be solved by the Chakravala method invented by the great Indian mathematician Bhāskara II, and this algorithm was considered "the finest thing achieved in the theory of numbers before Lagrange" by Hankel. Another special case is the exponential Diophantine equation associated with the enumeration of dyadic distributions that connects to binary search tree algorithms that are fundamental in information theory and coding theory (e.g., construct prefix-free code for compression). And, until only recently, the task of expressing the sum of three cubes for 33 and 42 was completed in 2019 by supercomputers and massively parallel computational search algorithms. It is undeniable that finding solutions to solvable Diophantine equations requires a skillful use of computers. Further reading on how Julia's legacy impacts the future of computer science can be found in Undecidability in Number Theory by Bjorn Poonen published in AMS 2008.

This is an inspirational mathematical tale worth telling to many more students of mathematics and computer science.

The Julia Robinson Centennial Reception held at Julia's former house

 Nancy Blachman and myself beside the Christmas Tree at MSRI

Martin Davis showing a picture of the collaborators who nailed down Hilbert's 10th Problem.

Promoting Equity in Mathematics Education

In February 2018, I visited the Mathematical Sciences Research Institute at UC Berkeley to attend a MSRI Workshop on Critical Issues in Mathematics Education 2018: Access to mathematics by opening doors for students currently excluded from mathematics. Tertiary and K-12 educators across the nation and some including myself from overseas converged at this workshop packed with group discussions and lightning talks co-organized by Francis Su who was the President of the Mathematical Association of America. The MSRI has been a prominent driving force behind math circle learning in the United States, and so for me it was rightly a pilgrimage trip to MSRI which is perched right up at the top of the Berkeley hill, offering an unbeatable panoramic view of the Golden Gate Bridge and the Bay Area.  

One striking takeaway from this workshop is equity in mathematics education. Roughly speaking, equity means giving students what they need to succeed in learning regardless of their personal or social circumstances. One of the plenary speakers, Prof. Dave Kung, gave a very powerful and fantastic talk that provoked the educators among the audience to ponder the question of "I teach math?" or "I teach students?"  and where the audience would see themselves in the spectrum between these two extremes. The former is speaking the content, while the latter is individualized instruction. Dave held polls in between his plenary and it was interesting to watch the number of hands raised in the audience when Dave asked whoever had experienced a teacher at those two extremes and where the audience thought their current department might be standing in that spectrum. 

What Dave Kung brought out is an important pedagogical question but also one that is well formulated to ask whether and how, somewhere in the spectrum, technologies can help the disaffected students and even teachers. Going by the extent in which technologies have democratized information sharing in the last ten years, it is thus necessary to consider what greater role will technology play in order to address the equity problem in mathematics education. Will it open up doors to many more students or will it shrink the equity gap between the haves and the have-nots? This one-week pilgrimage to MSRI has been extremely educational and has given me a sense on how to develop and deploy our educational software technologies going forward.

For more than a year, we have been working on the PolyMath App, which first saw action at the Julia Robinson Mathematics Festival in Hong Kong in April 2017. Subsequently, we have partnered with a number of educators to promote the JRMF App at a few international and regional math outreach activities. Last October, the JRMF App was featured as a means to play Exploding Dot that James Tanton created for the 2017 Global Math Project. We also held a few interactive workshops with mathematics teachers at several well-established math education centers in Shanghai and the Shanghai World Foreign Language Middle School (上海市世界外国语中学). In February 2018, we worked with a group of forty secondary school mathematics teachers from the English Schools Foundation (ESF) international schools in Hong Kong. There was so much to learn from the teachers at the front-line of the ever-evolving mathematics education landscape. After the workshop was over, some ESF teachers even came forward to volunteer as math mentors at the Julia Robinson Mathematics Festival in March 2018!

Using the PolyMath App, we shared with the teachers how they can quickly learn binary number system and arithmetic through game-play in our PolyMath App. Thereafter it was natural to introduce James Tanton's exploding dot as it revolves around place value number system once the teachers had become familiar with the binary number system. The binary system is the most basic and practical one, not just because we use it in computers, but also because binary number representation and its arithmetic manifest intriguingly in games and algorithms. In particular, we delved into the deep mathematical insights behind the NIM game (also called the Fish-flavored Lollipop problem set in JRMF) and the algorithm behind the Russian peasant's method of multiplication and a logical puzzle by Martin Gardner. Working with these amazing teachers was an uplifting experience!

    

The Julia Robinson Mathematics Festival in Hong Kong (Video, App and Abundant Math Opportunities)

Hong Kong’s inaugural Julia Robinson Mathematics Festival (JRMF) was held at the Singapore International School (Hong Kong) on April 1st 2017 from 10:00am to 1:00pm. In partnership with the American Institute of Mathematics, the JRMF makes mathematics accessible to every student of all abilities, and focuses on collaborative problem-solving, as opposed to the competitive nature of mathematics examinations and contests, so that students can enjoy the richness and beauty of mathematics without any anxiety.

Guided by mathematics teachers and other mathematics lovers in the community, 248 students aged 10 to 14 worked on a variety of mathematical problems, puzzles and activities. Of these students, 230
(92%) came from local schools (Singapore International School, Chinese International School, Tung Wah Group Schools, ESF Island School among others). The mathematical activity at each table was specially designed to be initially easy and then progressively become challenging. These mathematically deep problem sets came with interesting names: "The Tower of Hanoi - and Beyond", "Broken Calculators", "The Game of Criss-cross", "Exploding Dot Puzzle", "Algebra Game", "Algebra Maze", "Leo The Rabbit", "Mobius Strip", "Number Game of Randomness", "Rubik Cube Machine!" among others. 

See Video Clip below on how students had a blast at doing mathematics! Dr. Mark Saul, Executive Director of The Julia Robinson Mathematics Festival, commented "They're choosing to do the Mathematics. And that's what is important!". 

Students roamed freely around and chose to go to any table to work on the problem sets. The facilitator at each table rewarded students with a raffle for demonstrating persistence in working on the math problems on hand or showing collaborative learning spirit (e.g., helping fellow peers at the table). Thirty raffle prizes such as Festival T-shirts, math games and books were given out at the end of the festival. To let all the participants meet the man behind the mathematics (to see their human faces flashed across the screen), we have even named each of the Raffle prizes after brilliant mathematicians whose short biography are read out before drawing the lucky winner of the raffle prize (see image below). The facilitators and overseas guests (Dr. Mark Saul and VIP guests from Mainland China and Taiwan —see group dinner picture below) had the honor to give out the Raffle prizes to the lucky students!

For the first time, mobile app software was leveraged at the JRMF for students to develop a stronger intuition to the mathematical problems through observation and experimentation. Even after the festival, the mobile app continues to encourage collaborative and creative problem-solving between the students and their parents and teachers. See our JRMF App screenshots below and install the Apple iOS version or the Android version to get a taste of some of the fun mathematics at the JRMF in Hong Kong!

Amidst the fun in mathematics, participants took away fond memories of doing challenging mathematics. With the new friendships forged, we look forward to the infinitely many opportunities and creative ideas to make Mathematics accessible to many more students. A Press Release and many more pictures and videos of the Festival can be found at the JRMF Hong Kong website!

"They're choosing to do the Mathematics. And that's what is important!"
 — Dr. Mark Saul, Executive Director of The Julia Robinson Mathematics Festival

Thirty Raffle Prizes named after Brilliant Mathematicians at the JRMF in Hong Kong

Screenshots of JRMF App used at JRMF in Hong Kong. The JRMF App continues to encourage collaborative and creative problem-solving between the students and their parents and teachers even after the JRMF Festival ends. 

JRMF Organizing Team and Overseas VIP Guests enjoying a "Festive Dinner" together: Dr Mark Saul, Executive Director of the JRMF, Ms. Cherry Pu and Team from Mainland China and Mr. Ho and Team from Taiwan.

Starting the Julia Robinson Mathematics Festival in Hong Kong

We are very excited to announce that the inaugural Julia Robinson Mathematics Festival in Hong Kong is going to be held on April 1st (Saturday) at the Singapore International School (Hong Kong). This is open to students in Hong Kong, ages 10 to 14.

The Julia Robinson Mathematics Festival in Hong Kong 2017 inspires students to explore the richness and beauty of mathematics through activities that encourage collaborative and creative problem-solving. This event is in joint partnership with the Julia Robinson Mathematics Festivals and the Singapore International School (Hong Kong). Details at http://www.algebragamification.com/JRMF.

We started this as a grassroots activity with a few like-minded friends -- Jian Shen (former Princeton University Math Club President who then roped in other mathematicians working in finance), Ken Shum. We all wondered what differences we can make for Hong Kong students who are new to this type of mathematics initiative. And the Julia Robinson Math Festival in Hong Kong seems perfectly in sync with the United States' 2017 National Math Festival, the grandest carnival in mathematics. We are delighted to receive full support from Mark Saul (Executive Director of Julia Robinson Mathematics Festival) and also local academics like Professor Tony Chan (HKUST President), sponsorship from the IEEE Information Theory Society and the Singapore International School (Hong Kong) whose vice-Principal Mr. Bernard Ng and I had a great time working together before.

The Julia Robinson Mathematics Festivals is a project founded by Nancy Blachman in partnership with the American Institute of Mathematics that started in 2007 at Google in the Bay Area (yes it's as old as the cool iPhone). Since then, the festivals have spread to many places worldwide. The idea of the Festivals is to allow young people to develop their talent for mathematics by providing problems, puzzles, and activities that are intriguing and accessible in a non-competitive atmosphere. A diverse audience of young people, school teachers, math lovers in the community come together to explore the joys and power of mathematics with the goal of broadening society's appreciation and support of mathematics. 

We will have a number of math-lovers from the academia and industry who will facilitate at each table of math and to give out raffle tickets! The Algebra Game Project will of course have a table of its own for students to explore the mathematics behind the game. There are also mathematical origami, puzzles and many more that we are creating and preparing right now! 

Stay tuned for April 1st! Here is the Festival poster:

Camera Vibration in Canvas Based Unity Game

Contributions by Alex Ling

Currently I am maintaining a 2D Unity game (check it out here if you are interested). I was trying to implement a feature that when the user gives illegal input, the whole screen would shake (or vibrate if you would) for a while.

Here’s a GIF as a demo. When the user try to multiply of divide a variable with x, the whole screen will vibrate for 0.3 seconds.

I know what you would say, what’s the big deal here? We can simply randomly move the main camera for 0.3 seconds to achieve the effect. I don’t blame you, because that’s what I thought at first glance.

I attached a CameraShaker.cs script to the main camera. The script looks like this

using UnityEngine; public class CameraShaker : MonoBehaviour { public float shakeAmount = 0.7f; float shakeTime = 0.0f; Vector3 initialPosition; public void VibrateForTime(float time){ shakeTime = time; } void Start() { initialPosition = this.transform.position; } void Update () { if (shakeTime > 0){ this.transform.position = Random.insideUnitSphere * shakeAmount + initialPosition; shakeTime -= Time.deltaTime; } else{ shakeTime = 0.0f; this.transform.position = initialPosition; } } }

And in another script I call the VibrateForTime method:

// ... if (!OperationIsLegal(operation)) { Camera.main.GetComponent<CameraShaker>().VibrateForTime(.3f); return; } // ...

Then I ran the game and tried it… Oh wait! Why isn’t the screen shaking? I quickly found that it’s because the canvas’ renderMode property is at its default value Screen Space - Overlay



When this property is set as Screen Space - Overlay or Screen Space - Camera, the canvas is always attached to the screen (and of course the camera), and so it’s vibrating with the camera. That’s why we can’t see any vibration happen.

So the solution is simply set the renderMode property to World Space in the inspector. In this way the canvas and the camera are decoupled and so the vibration can be seen. This should work in most cases, but for me, I found that when set to World Space, the light blue operator when dragged (see the above GIF) will not be displayed. That’s because to position the blue operator at mouse position the coupling between canvas and camera(screen) is needed.

So my final solution is, set the renderMode of the canvas to World Space when the vibration start, and set it back to Screen Space - Overlay once the vibration finish. Since the vibration time is short, this should not affect the display of the light blue operator. The final version of CameraShaker.cs is shown below:

using UnityEngine; using UnityEngine.UI; public class CameraShaker : MonoBehaviour { public float shakeAmount = 0.7f; public Canvas canvas; float shakeTime = 0.0f; Vector3 initialPosition; public void VibrateForTime(float time){ shakeTime = time; canvas.renderMode = RenderMode.ScreenSpaceCamera; canvas.renderMode = RenderMode.WorldSpace; } void Start() { initialPosition = this.transform.position; } void Update () { if (shakeTime > 0){ this.transform.position = Random.insideUnitSphere * shakeAmount + initialPosition; shakeTime -= Time.deltaTime; } else{ shakeTime = 0.0f; this.transform.position = initialPosition; canvas.renderMode = RenderMode.ScreenSpaceOverlay; } } }

Let’s take a closer look at what I did in VibrateForTime:

// ... canvas.renderMode = RenderMode.ScreenSpaceCamera; canvas.renderMode = RenderMode.WorldSpace; // ...

Before setting the renderMode to WorldSpace, I set it to ScreenSpaceCamera first. That’s because by setting it to ScreenSpaceCamera, the canvas will be automatically positioned and scaled to fit in the camera. If I jump from ScreenSpaceOverlay directly to WorldSpace, the canvas will be out of the sight of the camera, and we will need to manually reposition the canvas in that case.

Algebra Game and Algebra Maze on Google Play Store!

We recently launched our first mobile apps Algebra Game and Algebra Maze on the Google Play Store.  From day one, the Algebra Game team members basically hit the ground running to put ideas into code.  Designing mathematical games in mobile apps is a challenging experiment - binding mathematical elements with the human-computer interface is an art,  making the same piece of software work on different hardware is trial and error,  walking through the entire online app submission process is new to us!  And this whole process doesn't stop there. It continues in a loop whenever new bugs/ideas surface.  Developing software is truly a humble learning experience.  We are working hard on the iOS mobile apps - so expect to see them in App Store soon.

We are also excited to have made inroads into understanding the mathematics behind Tao's Algebra Game.  Figuring out the math to compute the fewest moves for puzzle generation thereby answering some of Terence Tao's questions is actually the ultimate endgame for us :)   This can help in cleverer puzzle generation and we will flesh out that once the math is neatly ironed out.  The Algebra Maze on the Google Play Store currently has forty-five levels altogether,  but we have embarked on newer game design for the Algebra Maze and even contemplating new functionality in these mobile app games to bring out the social element: Math is social!

Ultimately, user experience matters the most. And we expect to get as much feedback as possible to further improve our mobile app games. Check them out and let us know!  We will be glad to hear from you.  Algebra Game Team members meanwhile take a break from crunching maths and writing software to savor yummy mooncakes.

Claude Shannon Centenary and the 1-bit Maze (A-Maze-ing Dash Challenge)

The Claude Shannon Centenary 2016 in Hong Kong is a series of events held in Hong Kong to mark the life and legacy of Claude Shannon, an American mathematician and engineer, who was a visionary pioneer in the fields of computing, communications and artificial intelligence.  I chaired a seminar on quantum information theory given by the 2016 Shannon Award Lecturer Alexander Holevo on May 6th.  A Claude Shannon Centenary workshop was also organised on May 19th by Professor Raymond Yeung at the CUHK Institute of Network Coding, where I gave a talk titled "To prove or to disprove: information inequalities and sparse optimization". 

I also delivered this as an invited talk at Tsinghua University in Beijing on May 14th ("纪念Shannon诞辰一百周年学术论坛"). My talk was on the automated generation of mathematical proof to Shannon-type inequalities in information theory using linear programming and cloud computing.  Fancy that! A topic that would be impossible without Shannon's Master thesis that engendered the birth of digital logic in 1938 and his seminal work on information theory in 1948, and these two seemingly-disparate subjects converge!

A local outreach activity Computer Science Challenge was held on 21 May at the City University of Hong Kong for 180 middle school children (62 upper primary and 118 secondary school students) who formed teams to compete in three digital game challenges. The CS Challenge is part of the Claude Shannon Centenary, 2016 Hong Kong. During the CS Challenge, educational exhibits of Claude Shannon and replicates of his fun and thought-provoking robotic machines —Rubik-cube manipulators using Lego — were also on display. 

One of the CS Challenge's tasks was to program a robot to solve a maze. This was inspired by Shannon's Maze-solving Theseus Mouse, which was the world's first digitally-programmed maze-solver in 1951. Shannon's Theseus Mouse ushered in the age of machine intelligence when a computer (using telephone relays) is capable of searching for a solution by trial and error and then remembering the solution. It was also Shannon's Theseus Mouse that inspired Paul Baran, the Internet pioneer to come up with the packet switching principle and dynamic routing underlying our Internet technologies.

The maze in the CS Challenge for secondary school students was designed with Shannon's entropy — a coin flip decides one of two possible maze entrances, i.e., the robot starts from the left entrance with a Head or otherwise from the right entrance with a Tail. The left and right entrances entail a left and right corner respectively, and the two passages meet at the intersection of a corridor to the exit. Now, a fair coin flip generates one bit of information. In this way, as the coin is flipped only after the robot has been programmed, this 1-bit uncertainty prevents the participants from hard-coding the robot's movement (i.e., no dead reckoning); The robot has to hit an obstacle (i.e., the corner wall) and navigate its way by trial and error. We hope that students know about Claude Shannon and his marvellous creations as they bravely enter the Maze as Theseus did. Check out more pictures and the video below on the 1-bit maze. What a memorable and a-maze-ingly fun 2016 CS Challenge we had!