The Caltech Mathathon included exciting new results on the HP protein folding model and $\Pi_6$ definability of the Turing jump. I was a judge and also participated in a panel discussion.
Tag Archives: featured
Formalizable Mathematics grant
My proposal Formalizable Mathematics has been recommended for funding by the Simons Foundation for a 2026-2031 Travel Support for Mathematicians grant.
My selected contributions to Mathlib, the library of formalized mathematics for the proof assistant Lean:
- First and Second Derivative Tests (2024-2025, with Patrick Massot, Floris van Doorn, Jireh Loreaux, and Eric Wieser)
- Equivalence between one-point compactification of $\mathbb R$ and the projective line (2024, with Oliver Nash)
- One-point compactification of Euclidean space is homeomorphic to the sphere (2025, with Oliver Nash)
Cleaning up at annual awards!
The “lab” really cleaned up at the Department of Mathematics Annual Awards, with Prof. Kjos-Hanssen and Dr. Lakshmanan both receiving teaching awards.
Deontic independence challenge
Which of these 128 combinations are satisfiable in Carmo and Jones style deontic logic? (1=true, 0=false) (Here 5(c) is the strong version.)
Some possibilities are ruled out by Observation 5.1.2 that says 5(bcde) imply 5(g); and Lemma II.2.2 that says 5(abcd) imply 5(f), formalized by RJ Reiff.
| 5(abcdefg) | Model |
|---|---|
| 0000000 | ? |
| 0000001 | ? |
| 0000010 | ? |
| 0000011 | ? |
| 0000100 | ? |
| 0000101 | ? |
| 0000110 | ? |
| 0000111 | ? |
| 0001000 | ? |
| 0001001 | ? |
| 0001010 | ? |
| 0001011 | ? |
| 0001100 | ? |
| 0001101 | ? |
| 0001110 | ? |
| 0001111 | ? |
| 0010000 | ? |
| 0010001 | ? |
| 0010010 | ? |
| 0010011 | ? |
| 0010100 | ? |
| 0010101 | ? |
| 0010110 | ? |
| 0010111 | ? |
| 0011000 | ? |
| 0011001 | ? |
| 0011010 | ? |
| 0011011 | ? |
| 0011100 | ? |
| 0011101 | ? |
| 0011110 | ? |
| 0011111 | ? |
| 0100000 | ? |
| 0100001 | ? |
| 0100010 | ? |
| 0100011 | ? |
| 0100100 | ? |
| 0100101 | ? |
| 0100110 | ? |
| 0100111 | ? |
| 0101000 | ? |
| 0101001 | ? |
| 0101010 | ? |
| 0101011 | ? |
| 0101100 | ? |
| 0101101 | ? |
| 0101110 | ? |
| 0101111 | ? |
| 0110000 | ? |
| 0110001 | ? |
| 0110010 | ? |
| 0110011 | ? |
| 0110100 | ? |
| 0110101 | ? |
| 0110110 | ? |
| 0110111 | ? |
| 0111000 | ? |
| 0111001 | ? |
| 0111010 | ? |
| 0111011 | ? |
| 0111100 | none; Obs. 5.1.2 |
| 0111101 | ? |
| 0111110 | none; Obs. 5.1.2 |
| 0111111 | see: A5_not_implied |
| 1000000 | ? |
| 1000001 | ? |
| 1000010 | ? |
| 1000011 | ? |
| 1000100 | ? |
| 1000101 | ? |
| 1000110 | ? |
| 1000111 | ? |
| 1001000 | ? |
| 1001001 | ? |
| 1001010 | ? |
| 1001011 | ? |
| 1001100 | ? |
| 1001101 | ? |
| 1001110 | ? |
| 1001111 | ? |
| 1010000 | ? |
| 1010001 | ? |
| 1010010 | ? |
| 1010011 | ? |
| 1010100 | ? |
| 1010101 | ? |
| 1010110 | ? |
| 1010111 | ? |
| 1011000 | ? |
| 1011001 | ? |
| 1011010 | ? |
| 1011011 | ? |
| 1011100 | ? |
| 1011101 | ? |
| 1011110 | ? |
| 1011111 | see: B5_not_implied’ |
| 1100000 | ? |
| 1100001 | ? |
| 1100010 | ? |
| 1100011 | ? |
| 1100100 | ? |
| 1100101 | ? |
| 1100110 | ? |
| 1100111 | ? |
| 1101000 | ? |
| 1101001 | ? |
| 1101010 | ? |
| 1101011 | ? |
| 1101100 | see: C5_not_implied’ |
| 1101101 | ? |
| 1101110 | ? |
| 1101111 | ? |
| 1110000 | ? |
| 1110001 | ? |
| 1110010 | ? |
| 1110011 | ? |
| 1110100 | ? |
| 1110101 | see theorem: strong_do_not_imply_5d_or_5f |
| 1110110 | ? |
| 1110111 | ? |
| 1111000 | none; see II.2.2 |
| 1111001 | none; see II.2.2 |
| 1111010 | ? |
| 1111011 | see theorem: do_not_imply_5e |
| 1111100 | impossible as 5(fg) follow from 5(abcde) |
| 1111101 | impossible as 5(fg) follow from 5(abcde) |
| 1111110 | impossible as 5(fg) follow from 5(abcde) |
| 1111111 | stayAlive, alive, noObligations |
Knot and link theory in protein folding models
New paper! published in Journal of Experimental Mathematics, 2026
A computable measure of irregularity
My book “Automatic complexity: a computable measure of irregularity” was published by de Gruyter on February 19, 2024. It concerns a version of Sipser’s complexity of distinguishing that was introduced by Shallit and Wang in 2001 and has been developed by me and others since 2013. The book’s exercises have formalized solutions in the proof assistant Lean.
Errata
- Exercise 1.12: the word “no” should be removed.
- Theorem 1.41 (3) refers the reader to Chapter 2 for the function $A_N$. In fact, $A_N$ is introduced in Definition 1.21.
- Claim 4.43: $b’\in\Sigma\setminus\{w_1,\dots,w_s\}$ should (obviously) be replaced by $b’\in\Sigma\setminus\{b_1,\dots,b_s\}$.
- Theorem 4.49: The text claims Our witnesses for $A^{\mathrm{perm}}(x)\le |x|+1$ are doubly transitive since the generated group is $S_n$. However, the generated group is not $S_n$ in general. A minimal counterexample is the witness for the word $00$, which generates the group $\mathbb Z/3\mathbb Z \ne S_3$. Therefore, whether $A^{\mathrm{tra2}} \le A^{\mathrm{perm}}$ should be considered open. Python calculations suggest it is true for binary words $w$ with $|w|\le 4$, and for 00000, at least.
- Theorem 6.6: Two constructions $M_1\times_1 M_2$ and $M_1\times_2 M_2$ are described. The text suggests that $\times_1$ is used for the theorem, but actually $\times_2$ should be used. The operation $\times_1$ can be used to prove the inequality $A_N(x)\le A_N(x\mid y)\cdot A_N(y)$ instead.
Philosophy for Children P4C
The number of languages with maximum state complexity
Lei Liu completed her Master’s degree with the project title Complexity of Options in 2017.
An extension to monotone options (pictured) was presented at
ALH-2018. The new paper is called The number of languages with maximum state complexity and has been accepted for TAMC 2019.
As of 2022, the paper has been through 7 revisions and has been accepted for publication in the journal Algebra Universalis.
- Slides for ALH 2018
- Slides for TAMC 2019