A Long Train of Thought (and a Puzzle)

This afternoon, while working on a probability assignment for my Open University course, I remembered an issue that came up in an A level class last week. When evaluating a definite integral, some students were using their calculators at the end and getting frustrated that an exact answer wasn’t appearing. Calculators these days will happily spit out surds or rational multiples of π but not this time. In fact, the result was something along the lines of \pi + 3\sqrt{3} and that was beyond the Casio’s capabilities.

Puzzle to Self

My mind then drifted and I wondered if it is possible to somehow reverse engineer exact expressions from decimals. Of course, such a system could not be perfect due to the rounding of the decimal value, but perhaps there’s scope on the assumption that the integers involved are relatively small.

Where to begin? I set myself a challenge. Typing 5+3\sqrt{2} into the calculator gives 9.24264 to 5 decimal places. Let’s assume we know we’re aiming for an expression of the form a+b\sqrt{2} with the a and b integers. Where to begin? Well, to be honest, I was almost immediately stumped. But little bits of mathematics started bubbling up in my mind:

  • Euclid’s algorithm: used for example to express 1 as a linear combination of two coprime integers.
  • The idea of a field: the set of numbers \{a+b\sqrt{2}, a,b\in\mathbb{Z}\} form a field. Coincidentally, Danny Brown posted last week about using these numbers for introducing the binomial expansion:

     

  • Vector spaces: there is, in some sense, linear independence between 1 and \sqrt{2} and we are trying to find a particular linear combination of these two.
  • Gram-Schmidt algorithm: it’s been a long time since I last studied this, but I remember it relating to vector spaces and finding bases etc

I was pretty much stuck. Short of writing a bit of code to iterate over all pairs of integers ab I didn’t really know what else to try. So I Googled.

What the Interwebs Said

Of course, I’m not the first person to have ever considered this issue and I soon uncovered a host of interesting posts and discussions.

  • Firstly, the power of Twitter! Aidan Sproat sent me this approach to the problem. Working with figures rounded to 1dp, he succeeded:

     

  • This discussion on StackExchange was particularly interesting, especially as it opened up a much wider class of problems than I had considered. Moreover, it linked to a Windows executable that implemented the so-called PSLQ and LLL algorithms which hunt down these integer combinations.
  • Every page I’ve opened about the LLL algorithm has been all but impenetrable due to the abstract notation of vectors, norms and matrices. (One did make an analogy to Gram-Schmidt which gave me a slight moment of satisfaction that my ideas weren’t completely off-track.)
  • I then discovered the Inverse Symbolic Calculator. This is effectively a web implementation of the same algorithm, but which will try quite a variety of ‘famous’ irrationals. However, I did have to give it one extra decimal place on my test number (9.242641) for it to recommend 5+3\sqrt{2}.
  • With a bit more investigating, it turns out that the PSLQ algorithm has a much simpler precursor attributed to Gauss (or Lagrange, some people argue) that works in just 2 dimensions. Satisfied that my original problem is (a) essentially solved, and (b) possible in simple situations, as demonstrated by Aidan, I then followed some leads on Gauss’ algorithm for the ‘shortest vector problem’.

And so to the puzzle…

What I like most about this puzzle is that it could be phrased so that any level of maths student can understand it. I’ll go with the vector notation just to be concise.

Edited: Beginning at the origin and following any (integer) combination of the vectors \begin{pmatrix} 5 \\ 4\end{pmatrix} and \begin{pmatrix}12\\9\end{pmatrix}, what is the closest point to the origin that can be reached?

(Rather satisfyingly, this is somewhat akin to Euclid’s algorithm which was another of the ideas that occurred to me early on.)

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s