📄 Computing the optimal keyboard through a geometric analysis of the English language

Summary

The authors ask whether a letter arrangement faster than QWERTY can be derived from the statistics of English. They treat typing as hand travel at constant speed, so typing time is proportional to distance moved. From a list of frequent English words with counts, they build a 26×26 matrix of letter-to-letter transitions. Normalising its rows gives a Markov chain, and its stationary distribution recovers overall letter frequencies. The expected distance per keystroke is the sum of π_i·P_ij·d_ij over letter pairs. They minimise it over the pairwise distances, with symmetry, a minimum key gap, a scale constraint and ridge regularisation. Multidimensional Scaling then turns the optimised distances into 2D key positions. Integer programming places these positions on a real key grid. They build a one-handed design (H1) and a two-handed design (H2), where H2 splits the letters into one cluster per hand. They also study the geometry through curvature and π-weighted covariance ellipses. H2 needs about 2.8% less travel than a two-hand QWERTY baseline. The result shows that QWERTY is already fairly efficient by this measure.

Key points

• Data and model: bigram counts from an English word-frequency list form a 26×26 transition matrix P. Its stationary distribution π satisfies π = πP.
• Objective and settings: the objective is the long-run average distance per transition. The chosen hyperparameters are d_min = 0.01, c = 1 and α = 1. With these, frequent letters land near the centre of the embedding, and rare letters such as q and z sit on the edge.
• Pipeline: the method runs in three stages: (1) a relaxed distance optimisation, (2) a 2D embedding via MDS using double centering and the top two eigenvectors, and (3) an integer-programming step that assigns letters to physical keys.
• Two-hand cost model: a hand that finishes early waits for the other hand, so only the excess travel is counted. Under this model, H2 averages 2.36 a.u. per transition and QWERTY-2 averages 2.43 a.u., a 2.8% gain.
• Limitations and extensions: the model ignores the space bar and punctuation, and the two-cluster assumption for two hands is questionable. Proposed extensions are a multilingual keyboard built from a Wasserstein barycenter of per-language transition matrices, and a Gromov-Hausdorff-style distortion score for comparing layouts.

Interesting ideas

• I1. Optimise in a relaxed continuous space first, then snap the result onto a discrete structure with integer programming; this keeps the hard combinatorial step small and makes it explainable.
• I2. Weight every metric by the stationary (long-run) frequency of items, so that errors on common letters count more than errors on rare ones.
• I3. Model two parallel actors so that the slower one sets the cost, counting only the extra time beyond the faster one's work; this is a simple and explicit concurrency rule.
• I4. Average several conditional distributions with a Wasserstein barycenter instead of a plain mean, so the shared geometry of the sources is preserved.
• I5. Compare two spaces through a distortion score that uses an identity coupling and is weighted by item importance, which gives a single interpretable "how different" number.

For Mova

How these ideas could serve Mova, our small open language model — its files, stages and tests:

• I1 (back): when choosing word order or clause arrangement in generation, a continuous score over the meaning graph could be computed first, then an ILP could pick one grammatical linearisation.
• I2 (learn): weighting parser or tagger errors by how often a construction occurs in running text would give an evaluation closer to what readers actually meet.
• I3 (world): when ordering events in a story, concurrent actions by different agents could be timed by the longer action rather than summed.
• I4 (tree): transition or attachment statistics from several UD treebanks or dialects could be merged this way into one prior for the perceptron parser.
• I5 (learn): the same score could measure how far two witness parsers' tree distances diverge, weighted by token frequency, to flag sentences where silver agreement is weak.