My research and investigations

Fermat’s Little Theorem

I have a joint paper with my supervisor, on combinatoric and group-theoretic proofs of Fermat’s Little Theorem in HOL4.

It all started when I came across the Necklace proof of Fermat’s Little Theorem, which is different from the textbook number-theoretic proof. The number-theoretic proof is also standard in automatic theorem provers, e.g. it is a worked example in HOL Light Tutorial. I was wondering how to put a combinatoric proof in HOL4.

It turns out that it is just a matter of counting with sets. There are tricks to set up bijections to establish the sizes of sets. Digging deeper, I find that there is a kind of symmetry underlying the bijections, and I am surprised to find group action is involved. Eventually I use the Orbit-Stabilizer Theorem to prove the Necklace Theorem, thereby proving Fermat’s Little Theorem.

At the end, we did several proofs of the theorem in HOL4, made a comparison, and gave the paper this title: “A String of Pearls: Proofs of Fermat’s Little Theorem”. The paper was accepted by CPP 2012, and I gave a talk at the conference held in Kyoto this December.

During this process, I have build up a library of group theory in HOL4. This should help my further work in finite fields.

Math – Finding Patterns

Everyone learn math at school, but it’s a subject most would rather forget. Simple calculations are fine. Solving problems is a headache. Proving theorem is like climbing mountains.

However, mathematician study math with pleasure. What are they studying, and what pleasure do they get?

If you’re looking for a short answer to the question “What’s math?”, here is one: “Math is the study of patterns.”

Yes, to mathematicians, there are patterns — visible or hidden — in their imaginary math world. They seek pleasure in finding patterns, show them off, perhaps apply them to dig out deeper patterns.

You don’t believe this? I’ll let YOU find a pattern.

Math deals with many things: numbers, shapes, changes, structures, patterns, patterns of patterns, … Let’s start with the basic stuff: numbers.

What patterns are hidden in numbers? Nothing much for 1, 2, 3, 4, 5, ….

How about the squares? 1, 4, 9, 16, 25, 36, 49, ….

A pattern is something that repeats. To find a pattern, we may need to see a long list. In this case, compute as many squares as possible — the first 100 squares, 1000 squares, even more. Perhaps you are willing to compute the first 10 squares. Beyond that, you know you have the skills (just multiply a number with itself), but you’d rather not to waste your time doing so. Nowadays, there are computers (most likely you’re using one right now) which can compute at almost lightning speed. I’ll help you to use the computer for this task.

However, it’s rather tricky to teach you how to program (give instructions to) a computer to perform calculations.

Or is it? You’re using a browser to read this blog. You can instruct the browser to ask the computer to do calculations!

Modern browser knows something called Javascript, and you can do wonderful things with it. Also, it helps if your browser allows new tabs. If not, you’ll need to open a new browser instance, in order to keep reading this.

So click for a new tab in your current browser, copy the following line (highlight it, right-click, copy), and paste it in the new tab’s address box (right-click the long blank rectangle near the top, paste). Press ENTER (or click “->”).

javascript:m=100;for(n=1;n<=m;n++)document.write(n+' sq = '+n*n+'<br>')

On iPad/iPhone, just select the above line, copy, switch to Safari, tab address box, clear by (x), then paste, “Go”.

You should see the first 100 squares printed in your browser page, one square per line. I won’t teach you Javascript here. I’ll just say that m=100 above means “set maximum to 100”, and “for…” will repeat the computation (in this case printing the squaring line) for the maximum number of times.

If you close the tab, start an new one, and copy/paste again: this time change m=100 to m=500 before “->”. The browser will print the first 500 squares, faster than you can scroll!

Try this in your browser now, and see if you can spot any pattern in the squares.

Steve Jobs and Apple

We’ve all shared the news. Steve Jobs had left a legacy that perhaps no one can match. I still remember my Apple ][ — with high-resolution color graphics and 64KB memory, no hard disk, but boot from 5.25″ floppy — very “modern” in 1980!

To appreciate the achievements of Steve Jobs, you have to understand his philosophy. We can get a lot of inspiration from Wikipedia:

I am really inspired to read how Steve talks about himself, in his 2005 Stanford Commencement Address, with video (also this Chinese translation: 喬布斯三個故事啟發人心).

Last year, Steve Jobs was named “Person of the Year for 2010” by the Financial Times. The article ends with this story from the Apple CEO when Steve left the company in 1985:

“In his autobiography, John Sculley, the former PepsiCo executive who once ran Apple, said this of the ambitions of the man he had pushed out: “Apple was supposed to become a wonderful consumer products company. This was a lunatic plan. High-tech could not be designed and sold as a consumer product.” How wrong can you be.”

However, this was quoted from John Sculley’s autobiography in 1987. Since then, John understands Steve better, and this interview in 2010 is really informative.

Did you ever wonder why the Apple Logo has a bite? Here is the story.

Oh yes, Steve is a Beatles fan. Here is an interesting episode.

The Proof Path

When doing a math proof, it’s like walking along the math landscape: your proof is a path (a logical path) from the hypotheses (starting point) to the conclusion (finishing point).

The HOL theorem-prover provides an interactive proof manager. When it shows “all goals proved”, it is indeed a revelation: suddenly the logical path is complete.

Because the logical path is taken by the machine, you’re sure that there are no logical gaps — no missing steps. This is the advantage of using the theorem-prover: it won’t allow logical gaps.

However, you can be driven into logical blind alleys — the theorm-prover won’t tell you. This is because along the proof path, there are many decision points: which symbol to induct on? should cases of a symbol be taken?

Ideally all paths will lead to the same goal, but some paths are easier to walk, while other paths go through mountains or deserts. Some even lead to a door — you just can’t open it without a key. The key may be nearby, or far away; but you need to find the key to open the door if you want to continue on with that particular path. That’s the key idea to overcome the stumbling block.

All in all, a theorem prover is a good guide for the proof path, as you can see the effect of tactics, and where you’re going. Most goals will branch off into subgoals, and it’s tedious to keep track of subgoals by hand — better let the machine do the book-keeping.

To spell out all the logical details of a proof, as required by a theorem-prover, can be routine — not very illuminating, even boring. The HOL theorem-prover provides various rewrite tactics and simplification sets to ease the task, but picking out the appropriate tools to do the job still needs experience.

However, sometimes you’ll hit a stumbling block: something that looks simple and must be true, but you just can’t see any simple proof of it. That’s when the proof becomes interesting.

This is not related to a particular theorem prover. Ask any mathematician and he or she will tell you stories.

The solution of the “stumbling block” usually involves a key idea.

For example, given a number N, how to show that there is a prime greater than N? There is no known formula to generate primes. It was Euclid, around 300 BC, who recorded this key idea: use N to generate a number M such that M cannot be divided by any primes up to N. By case-analysis of this M, the infinitude of primes can be proved.

Of course, during case-analysis of M, you’ll need to show that any number must be a product of primes. If this is a stumbling block, you’ll need another key idea. And so on.

How to find the key idea? Using examples or pictures can help visualizing the stumbling block. After some deep thoughts, the key idea will dawn upon. Sometimes you need to look outside the box. And you’ll need pencil-and-paper to try out the key idea, as the theorem prover will not allow unproven stuff.

To find the key idea in a proof is almost an art — there is no algorithm for it.

The HOL theorem-prover includes tactics on induction, a standard technique for proofs involving a recursive data structure.

For example, the whole numbers can be constructed recursively as follows: starting from 0, successive numbers can be obtained by adding 1 to the predecessor: n to n+1. So if a property P can be shown such that:

  1. P is valid for 0, and
  2. If P is valid for n, it is also valid for n+1.

Then we can claim that the property P is valid for all whole number n.

Similarly, the list data structure can be constructed recursively as: starting from the empty list [], elements are inserted into the list (h::t), with head h and tail t. If tail t = [], the list has one element [h]. If tail = [k], the list has two elements [h; k], and so on.

Corresponding to the induction for proofs involving whole number properties, there is Structural Induction for proofs involving lists:

  1. Property P is valid for [], and
  2. If P is valid for list t, it is also valid for list (h::t).

The we can claim that the property P is valid for all lists.

Usually the base case (1) is trivial, easily proved by some fundamental results from definition.

The trick to prove the step case (2) is to match the pattern of the induction hypothesis: P is valid for t, to the pattern in the goal: P is valid for (h::t).

Sometimes the definition provides decomposition of the pattern (h::t) to t, then the step case is easy to match.
Otherwise, the best strategy is:

  • figure out what’s the stumbling block,
  • formulate a lemma that can solve the stumbling block,
  • prove the lemma.

It is the solving of stumbling blocks that make theorem-proving endeavours interesting.

Theorem Proving in HOL

Recently I’ve been doing actual theorem proving using HOL. This is a real eye-opener. Here is a summary of my first experience:

  • Simple theorems can be proved just by using definitions.
  • It’s not good to prove everything from definition — this makes the proof tedious.
  • Some fundamental results should first be established by definition — they become theorems for proving more complex results.

This corresponds to the working mode of mathematicians. To build a theory one starts from definitions, properties, lemma, then theorems. There are many proof techniques, called tactics in HOL, and choosing the most efficient one needs a lot of experience.

Meanwhile, HOL upon loading includes some basic theories, and there is mechanism to load in more specific theories if required. Users of HOL can write up the proofs in scripts, and the Holmake utility can compile the script and generate the theory file and binary files, ready for loading so that the theorems will be available in other HOL sessions.

HOL is a very useful too, and I’m learning the basics of the tool. The HOL documentations are a big help here. I alway learn a lot by following the theory scripts provided in the source and examples.