Imagine a high school level maths exam in which students are requested to solve the following simple equation: x² - 3x + 2 = 0. How would you grade the two following answers:

1. We proved in class that such an equation has at most two solutions. [A few lines of maths in which the student computed them.] Therefore, the solutions to this equation are x = 1 and x = 2.
2. We proved in class that such an equation has at most two solutions. We check that 1² - 3×1 + 2 = 0 and 2² - 3×2 + 2 = 0. Therefore, the solutions to this equation are x = 1 and x = 2.

Many teachers dislike the second solution, because they think that the student must have cheated. Indeed, the solution seems highly suspicious, because we cannot guess where the solutions come from. (Alright, those were easy to find, but you get the idea.) Notice however that, from a logical standpoint, the second solution is perfectly valid: it justifies the fact that they exists at most two solutions, and explicits them in a perfectly rigorous fashion.

[Interestingly, I had at least one maths teacher who preferred solutions of the second type, because he only wanted us to prove that our answers were correct, and believed that the process leading to the solution was none of his business.]

The point I would like to draw attention to is the following: whereas both solutions prove what they state, only the first one explains where it comes from. Of course, there are more complex examples of this distinction: while some math papers, books and teachers make a great job of explaining things, others just prove theorems mechanically without any effort to show what's going on behind the scenes.

This distinction isn't limited to numerical solutions to equations either. Even with no equations involved, there are proofs in which you can see that things work out as planned but can't understand why they do; proofs in which you build ridiculously complicated concepts with which you unexpectedly manage to prove simpler claims; proofs in which, to put it simply, the author writes things but does not explain what gave him the idea to do things this way. Proofs which, in a way, look like a program with no comments.

The important fundamental difference between explaining and proving is, in my opinion, the following. As far as proving is concerned, you can, theoretically, write proofs which are undoubtedly correct, using only the axioms and core deduction rules. Of course, you never do that in practice, but it means that you could reach perfection if you wanted to. However, when you explain things, you have no reason to believe that it is possible to write something which is undoubtedly understandable. To do this, you would need to make each step seem natural, that is, not only do things, but also explain, at each step, what gave you the idea to do so, and why it gave you such an idea, and so on, and so forth. [Philosophically, the idea is that you cannot understand well enough what's going on in your head when you think to explain why you are thinking in this way...]

Keep in mind that this issue of writing proofs which explain things in addition to proving them should not be confused with the well-known problem of writing proofs with the right level of detail, ie. the tantalizing fact that when you prove something, justifying every step is infeasible in practice but just writing "Trivial from the axioms." isn't acceptable either so you have to find a compromise between these two extremes. The issue I am dealing with has nothing to do with this: the second answer in the example above could formally justify every logical deduction (even going back to the axioms) and still manage to cook up arbitrary values for x and y without explaining how they were found.

It is quite sad that many math books and courses seem to be written for machines rather than humans in that they prove things but don't really try to explain what they do. In my opinion, things would be better if the two were present and clearly distinguished, with a machine-readable formal proof, and an informal discussion explaining how the proof is built and why it is built that way.

People seem to be entering lots of text using crippled telephone keypads these days. I personally hate these things, because they're so much slower than a regular keyboard, but I have to admit that carrying such a keyboard in your pocket is slightly unpractical.

The layout used on keypads is great for new users. I mean, since the letters are alphabetically ordered, you don't have to hunt that much for the key you want. However, a lot of phone users use their keypads so much that they know the layout by heart. I'm not one of them, but when I see them, I wonder: "wouldn't it be possible to create a layout which is less intuitive but more efficient ?"

Optimizing for frequency (without T9)

Of course, the answer is yes. If we arranged the letters on the keys in a way which ensures that the most frequent letters only require one keypress to reach, things would probably be a lot better.

Let's do the math. I assume that we will only be remapping the '2', '3', '4', '5', '6', '7', '8' and '9' keys. The layout used by mobile phones today is:

2

ABC

3

DEF

4

GHI

5

JKL

6

MNO

7

PQRS

8

TUV

9

WXYZ

Using letter frequency data for the English language, here is a possible layout optimized for letter frequency:

2

ERG

3

TDY

4

ALP

5

OCB

6

IUV

7

NMKQ

8

SWJ

9

HFXZ

Still using the letter frequency data, it's easy to compute the average number of keypresses by letter:

• 2.149 keypresses per letter for the default layout
• 1.462 keypresses per letter for the alternative layout

The bottom line is that this simple alternative layout requires 32% less keypresses than the default one.

Optimizing for key repetition (still without T9)

The previous analysis fails to take into account the fact that, whenever you want to use in succession two characters which are on the same key, you have to wait because the phone can't guess where the two characters could be separated. Some phone users prefer to type a dummy character and then delete, which removes the time penalty at the cost of two keypresses, or, more efficiently, press the "right" key (only one keypress).

Still, it might be possible to optimize the layout by ensuring that the letters of the most frequent digraphs are on different keys. We can try to do this without losing the frequency-optimization we did earlier, just by exchanging letters which require the same number of keypresses. (It don't say that it's the most efficient way to do it, I just say that it's a simple way to improve things so which preserves the optimization we did above.)

I could compute the optimal permutation using English digraph frequency data, but this would take some work. I might do it in a future blog entry. In any case, the default layout clearly hasn't been optimized for this.

Distinguishing ambiguities (with T9)

The T9 system requires other kinds of optimizations in order to distinguish similar-looking words.

A first idea would be to ensure that the keys are as equiprobable as possible (where the probability of a key is the sum of the probabilities of its letters). This is an idea from information theory: if a key has a very low total probability and the user almost never presses it, the information given by the user for each keypress is reduced, and more keypresses will be required.

The frequency-optimized layout I presented earlier is a "good" solution to the problem of making all keys equiprobable, though it's not the optimal one. Of course, the default layout isn't optimal at all. Once again, the efficiency difference could be computed using the English letter frequency tables.

However, since the user doesn't enter random strings of letters following the frequency distribution of the English language, but real English words, it would be possible (though perhaps computationally intensive), using a list of the English words with their frequency, to find the layout which minimizes ambiguities. Once again, doing this is left as an exercise to the reader.

Using grammar (still with T9)

When you use T9, you see that it often suggests words which match what you typed but make no grammatical sense in the current context (suggesting "the" after "a", for instance). Wouldn't it be great if T9 only suggested words which "make sense" (or, rather, used the grammatical plausibility of its suggestions as a way to order them)?

This might sound unrealistic, because it seems that it would require your phone to understand (ie. correctly parse) the sentences you're writing. In fact, it doesn't. We could simply use an n-gram model to tag the words entered by the user with their probable grammatical role in the sentence as they are being typed. This would require a bit more memory on the phone (to store the likely tags for each word, and the likely n-grams of tags), but is computationally feasible: it is no harder than standard predictive text, just done on tags instead of letters.

Conclusion

My point was not to develop the optimal keypad, just to show that there are a lot of extremely simple ideas that could make keypads more efficient but which, to my knowledge, haven't been explored. Sadly, this is the kind of things which should have been done right the first time, because, once widespread, they are well nigh impossible to change. If we didn't manage to get rid of QWERTY as a default keyboard layout and to replace it with DVORAK or any of its more efficient variants, then what are the odds of displacing the inefficient alphabetical keypad layout?

I've ranted about this for quite a bit, so I think I'd better blog about it once and be done with it. Here we go...

A lot of mobile phones today could be used as a general-purpose computer as far as the hardware is concerned, but come with a bunch of software restrictions. There are a lot of reasons for that: most users want their phone to be dead simple to use, and the telcos' nonsensical pricing (like, for instance, selling something labelled as full-featured unlimited Internet access and still trying to make customers pay their phone calls) makes it necessary for them to lock users.

Fortunately, it is usually possible to get rid of these crippled systems: iPhones can be jailbroken, Android phones can be rooted, and so on. The problem is that such actions void the warranty on the phone.

Don't get me wrong: I understand that I can't both use my phone in creative ways and ask my phone manufacturer to help me with that. The important point is that I don't need a warranty on the software, but I still need a warranty on the hardware.

The rationale is the following: except in the case of a hardware bug (or in some very specific cases, like BIOS flashing, software control of the fans, and so on), the hardware should work no matter which software I run on it. If it fails within the warranty period, I would like the manufacturers to replace it for free, because it means that the hardware was defective.

It surprises me a bit that, to my knowledge, no consumer defense association took the necessary steps to prevent manufacturers from refusing to replace the faulty hardware they sell, and to put an end to this ridiculous excuse of "the hardware was damaged by the broken software you used"...

Here's another attempt to resume blogging after quite a long break. In all probability, this attempt will fail just like the others, but who knows...

As a way to make things easier for me, I will probably write shorter posts, and will try to proof-read and edit a bit less.

On a technical note, this blog is powered by fugitive, a blogging engine which uses git and bash to generate static HTML, developed by a friend of mine. This is no longer true; see the footer.