Sign in

Nathaniel Johnston

@njohnston.ca
368 followers 125 following 110 posts

Associate Professor of Mathematics at Mount Allison University Interested in quantum information theory, Conway's Game of Life, recreational mathematics, and mathematics pedagogy. 🔗 njohnston.ca ▶️ www.youtube.com/@NathanielMath

PostsRepliesMedia
Nathaniel Johnston @njohnston.ca · 24/09/2026
New preprint today. I (with AI) proved the S_{n,n} conjecture from spectral graph theory: arxiv.org/abs/2609.26895
arxiv.org
The Laplacian $S_{n,n}$ conjecture is true
The "$S_{n,n}$ conjecture" asserts that there does not exist a simple graph on $n$ vertices with Laplacian spectrum $\{0,1,2,\ldots,n-1\}$ for any integer $n \geq 2$. This conjecture has already been ...
020
Nathaniel Johnston @njohnston.ca · 16/09/2026
Sure enough, the barrier in our proof was broken down by AI, which proved Lemmas 35 and 36 for us, which then allowed everything else to fall into place.
010
Nathaniel Johnston @njohnston.ca · 16/09/2026
New preprint today with Benjamin Lovitz, @vrusso.bsky.social, and Jamie Sikora: arxiv.org/abs/2609.17411 We have been trying to extend our older paper (arXiv:2311.17047) since late 2023, but we were stuck on the proof of what is now Theorem 2 in the new paper for *years*.
arxiv.org
Sharp bounds for perfect quantum state classification beyond antidistinguishability
A multiset of pure quantum states is said to be k-learnable if there is a measurement strategy that always narrows an unknown sample drawn from the list down to one of at most k candidates. The parame...
120
Nathaniel Johnston @njohnston.ca · 11/09/2026
Notably, this is my first paper that made significant usage of AI. We used ChatGPT-6 Astra to develop the first version of the proof of the paper's main result.
010
Nathaniel Johnston @njohnston.ca · 11/09/2026
New preprint up today with Benjamin Lovitz: arxiv.org/abs/2609.11849 We construct positive-partial-transpose states with Schmidt number near n - sqrt(2n), versus the previously best-known constructions with Schmidt number of roughly n/2.
arxiv.org
PPT states of almost maximal Schmidt number
We construct PPT states on $\mathbb{C}^m \otimes\mathbb{C}^n$ that have Schmidt number asymptotically approaching the smaller local dimension. More specifically, we construct a PPT state with Schmidt ...
141
Nathaniel Johnston @njohnston.ca · 03/08/2026
lol, here's a fourth: arxiv.org/abs/2607.21367
arxiv.org
A solution to 2-copy distillability of Werner states
Entanglement distillation is a fundamental task in quantum information theory. In this work, we prove that Werner states in arbitrary dimension are 2-copy distillable if and only if they are 1-copy di...
020
Nathaniel Johnston @njohnston.ca · 02/08/2026
This first step always had a “I’m surprised we can’t figure this out” feel to it, so it’s maybe not surprising that AI beat us to it. But I’m having a really hard time seeing how we evaluate authorship and credit going forward. Theory builders seem somewhat safe for now, but problem solvers?
140
Nathaniel Johnston @njohnston.ca · 02/08/2026
For a bit of context, I worked on this problem a fair bit during my PhD (roughly 15 years ago). It’s the first nontrivial step in a larger (still open), much harder, problem in the field called “NPT bound entanglement”.
130
Nathaniel Johnston @njohnston.ca · 02/08/2026
It seems the rush to use ChatGPT Sol to solve all our open problems has hit quantum information theory. A problem from the field that has been open for 25 years was just solved 3 times, by 3 separate groups, in 2 days: arxiv.org/abs/2607.23416 arxiv.org/abs/2607.24309 arxiv.org/abs/2607.24479
arxiv.org
A partial-trace matrix inequality and Werner-state distillability
Motivated by the equivalent partial-trace formulations of Werner-state distillability [P. Costa Rico, Lett. Math. Phys. 115, 47 (2025); S.-Y. Qi et al., Phys. Rev. A 110, 012406 (2024)], we prove a bi...
2110
Nathaniel Johnston @njohnston.ca · 08/07/2026
In the process of trying to prove this conjecture, we showed that K_n is indeed the only such graph for n prime when n <= 29. However, for n >= 31, there are others (Table 3).
000
Nathaniel Johnston @njohnston.ca · 08/07/2026
Luis's numerics also suggested some other conjectures. Some of these conjectures were true (such as what is now Theorem 5 in the paper) and some were not. One of the not-true conjectures was that if n is prime then the only connected regular {-1,0,1}-diagonalizable graph is the complete graph K_n.
100
Nathaniel Johnston @njohnston.ca · 08/07/2026
Luis's computational results generated all Laplacian integral graphs up to order 12. Theorem 1 then makes it straightforward to generate all Laplacian integral graphs on order 13 as well.
100
Nathaniel Johnston @njohnston.ca · 08/07/2026
Luis did some great computational work that led us to conjecture that every order-n Laplacian integral graph, when n is prime, has disconnected complement. We ended up proving this conjecture (Theorem 1 in the paper, which has a surprisingly simple proof).
100
Nathaniel Johnston @njohnston.ca · 08/07/2026
New preprint with Sarah Plosker and my student, Luis Varona: "Enumeration of Laplacian integral and {-1,0,1}-diagonalizable graphs" (description in replies) arxiv.org/abs/2607.06336
arxiv.org
Enumeration of Laplacian integral and {-1,0,1}-diagonalizable graphs
A graph with Laplacian matrix $L$ is called Laplacian integral if the eigenvalues of $L$ are all integers, and it is called $\{-1,0,1\}$-diagonalizable if $L$ has a full set of eigenvectors with entri...
130
Reposted by Nathaniel Johnston
Vincent Russo @vrusso.bsky.social · 15/04/2026
New preprint with @njohnston.ca: "Distinguishability of locally diagonal orthogonally invariant quantum states" Optimal measurements preserve LDOI structure, reducing optimization from n^4 to O(n^2) variables. For two-qubit cases: LOCC = SEP = PPT. arxiv.org/abs/2604.12808
051
Nathaniel Johnston @njohnston.ca · 25/08/2025
The paper is: arxiv.org/abs/2508.11043
arxiv.org
Dyadically resolving trinomials for fast modular arithmetic
Residue number systems based on pairwise relatively prime moduli are a powerful tool for accelerating integer computations via the Chinese Remainder Theorem. We study a structured family of moduli of ...
010
Nathaniel Johnston @njohnston.ca · 25/08/2025
Huge shout-out to authors who put humour, even very mild humour, in their papers. You keep me awake.
A screenshot of a math paper.
170
Nathaniel Johnston @njohnston.ca · 21/07/2025
Finding the maximum or a minimum value of a single-variable polynomial is standard calculus fare, but doing this for polynomials of multiple variables is very hard. Our paper presents a method that works better than any other know methods for many polynomials.
010
Nathaniel Johnston @njohnston.ca · 21/07/2025
New paper published today! "A hierarchy of eigencomputations for polynomial optimization on the sphere", with Benjamin Lovitz: link.springer.com/article/10.1...
link.springer.com
A hierarchy of eigencomputations for polynomial optimization on the sphere - Mathematical Programming
We introduce a convergent hierarchy of lower bounds on the minimum value of a real form over the unit sphere. The main practical advantage of our hierarchy over the real sum-of-squares (RSOS) hierarch...
131
Nathaniel Johnston @njohnston.ca · 03/04/2025
If k is the size of the matrix then this quantity is exactly the rank of the matrix. If k = 1 then the matrix must be diagonal and this quantity is again the rank of the matrix. For intermediate values of k, more interesting stuff happens.
020
Nathaniel Johnston @njohnston.ca · 03/04/2025
The goal of the paper is to answer the question "If a matrix can be written as a convex combination of rank-one PSD matrices that are each non-zero only on a single k-by-k principal submatrix, what is the fewer number of matrices needed in that convex combination?"
120
Nathaniel Johnston @njohnston.ca · 03/04/2025
New paper published today! "The factor width rank of a matrix", with Shirin Moein and Sarah Plosker: www.sciencedirect.com/science/arti...
sciencedirect.com
The factor width rank of a matrix
A matrix is said to have factor width at most k if it can be written as a sum of positive semidefinite matrices that are non-zero only in a single k×k…
160
Nathaniel Johnston @njohnston.ca · 15/03/2025
Happy belated pi day! Had a midterm in my Vector Calculus class yesterday, so I asked my students to compute some vector line integrals along pi: www.desmos.com/calculator/u... #ITeachMath #MathsToday
desmos.com
Desmos | Graphing Calculator
060
Nathaniel Johnston @njohnston.ca · 28/02/2025
Now, two months later, Musk says that "Grok 3 is becoming superhuman" because Grok 3 obtained just as good as solution (i.e., an absolutely terrible non-solution) to this Putnam problem. Unreal.
Luis Batalha: None of the top 500 contestants in the 2025 Putnam competition fully solved this problem. Grok 3 (Think) found the solution in ~8 minutes.

Elon Musk: Grok 3 is becoming superhuman.
030
Nathaniel Johnston @njohnston.ca · 28/02/2025
I always present this as a fun final-lecture activity in intro linear algebra to try to give students an idea of how far-reaching eigenvalues are (you can use a 91-by-91 matrix to model the sequence of lengths and then its maximal eigenvalue is that 1.3-ish limiting ratio.
140
Nathaniel Johnston @njohnston.ca · 28/02/2025
I would expect that you could prove this straightforwardly from the fact that the sequence of lengths satisfies an order 72 linear recurrence relation. But the existence of that huge recurrence relation might not count as elementary.
010
Nathaniel Johnston @njohnston.ca · 29/01/2025
Are those platonic solid dice soft/plushie? If so, I have the exact same set in my office! I use them to illustrate symmetries when teaching group theory :)
110
Nathaniel Johnston @njohnston.ca · 10/01/2025
Paths, vector fields, scalar and vector line integrals, differentiation of vector value functions, divergence, curl, Greens theorem, and stokes theorem.
010
Nathaniel Johnston @njohnston.ca · 09/01/2025
Not sure if PPT can do that. My setup is a bit convoluted: I have two instances of OBS running (one to record me and one to record my screen), and then I overlay myself and do editing in a program called Capcut.
110
Nathaniel Johnston @njohnston.ca · 09/01/2025
Yep! I actually have two instances of OBS running at once - one to record me and one to record the PDF notes on my screen. Then I put it all together (and overlay the Desmos clips etc on top) in Capcut.
010
Nathaniel Johnston @njohnston.ca · 08/01/2025
I'm teaching Vector Calculus this semester (for the first time, somehow!) and making lecture videos to accompany the course. The first video is now up, with about 3 per week planned (35 to 40 total): www.youtube.com/watch?v=VbDE... The videos make huge use of @desmos.com #ITeachMath #EduSky
youtube.com
Vector Calculus - Lecture 1: Paths and Curves
YouTube video by Nathaniel Johnston
4122
Nathaniel Johnston @njohnston.ca · 01/01/2025
Shameless self-promotion time: if you enjoyed this thread and/or are interested in these sorts of aspects of Conway's Game of Life, have a look at my (free) book "Conway's Game of Life: Mathematics and Construction", co-authored with Dave Greene: www.conwaylife.com/book/
The cover of the book "Conway's Game of Life: Mathematics and Construction"
050
Nathaniel Johnston @njohnston.ca · 01/01/2025
#3 (4/4) This bound has now been improved, culminating in 2024 with Keith Amling proving an upper bound of 1176/2087 ≈ 0.563. We still don't know the exact answer, but this is the first progress that was made in over 3 decades: conwaylife.com/forums/viewt...
conwaylife.com
Unproven conjectures - Page 13 - ConwayLife.com
120
Nathaniel Johnston @njohnston.ca · 01/01/2025
#3 (3/4) However, it's natural to ask whether or not the same is true of infinitely large oscillators. There are plenty of infinitely large oscillators with average density equal to 0.5, but until 2023 the best known *upper* bound on the average density of an oscillator was 8/13 ≈ 0.615.
110
Nathaniel Johnston @njohnston.ca · 01/01/2025
#3 (2/4) In 1999, Noam Elkies proved that this conjecture is true. That is, there is no infinitely large still life with more than half of the cells in the Life grid alive: arxiv.org/abs/math/990...
arxiv.org
The still-Life density problem and its generalizations
A "still Life" is a subset S of the square lattice Z^2 fixed under the transition rule of Conway's Game of Life, i.e. a subset satisfying the following three conditions: 1. No element of Z^2-S has e...
130
Nathaniel Johnston @njohnston.ca · 01/01/2025
#3 (1/4): Oscillator density. In the early days of Life, it was conjectured that the maximum density (i.e., maximum ratio of alive cells to dead cells) of an infinitely large still life is 0.5. This density is easily attained by alternating rows of dead and alive cells.
An infinite still life in Conway's Game of Life, made up of alternating rows of alive and dead cells.
130
Nathaniel Johnston @njohnston.ca · 01/01/2025
#2 (4/4) In 2024, a large collaborative effort extended this to all 22-cell still lifes. To get a sense of scale, there are 672172 still lifes with 22 cells. That's 672172 different patterns to construct by colliding gliders together: conwaylife.com/forums/viewt...
conwaylife.com
22-bit still life syntheses - ConwayLife.com
110
Nathaniel Johnston @njohnston.ca · 01/01/2025
#2 (3/4) For this reason, people have been cataloging glider syntheses of patterns in Life ever since the early 1970s. We've known how to synthesize all small (say 10 cell or smaller) still lifes and oscillators since those early days. Recently this was pushed to all <= 21-cell still lifes in 2022.
110
Nathaniel Johnston @njohnston.ca · 01/01/2025
#2 (2/4) Glider synthesis is the key ingredient of Life that makes it possible to build most of the complex mega-patterns that you hear about. If you zoom in on a pattern like Gemini, for example, you'll see that it's almost entirely made of gliders: conwaylife.com/wiki/Gemini
conwaylife.com
Gemini - LifeWiki
110
Nathaniel Johnston @njohnston.ca · 01/01/2025
#2 (1/4): Still life glider synthesis. A glider synthesis is a way of crashing together 2 or more gliders so as to create another object. For example, in the image below three gliders collide so as to create a lightweight spaceship.
Three gliders colliding so as to create a lightweight spaceship in Conway's Game of Life.
130
Nathaniel Johnston @njohnston.ca · 01/01/2025
#1 (4/4) In 2024, Adam P. Goucher completely resolved this problem by showing that there does not exist a phoenix oscillator of any period other than 2. The proof is computer-assisted, but the idea behind it is very readable: cp4space.hatsya.com/2024/01/20/e...
cp4space.hatsya.com
Every finite phoenix has period 2
A phoenix is an oscillator in Conway’s Life where every cell dies in every generation. The smallest example is Phoenix 1, which oscillates with period 2 and has a constant population of 12: A…
140
Nathaniel Johnston @njohnston.ca · 01/01/2025
#1 (3/4) In 2000, Stephen Silver showed that period 3 phoenices don't exist. In 2019, Alex Greason showed that period 5 phoenices don't exist. And in 2023, Keith Amling showed that period 7, 9, and 11 phoenices don't exist.
110
Nathaniel Johnston @njohnston.ca · 01/01/2025
#1 (2/4) That phoenix was found in the early days of Life (1970 or 1971), and since then people have been wondering whether or not there are phoenices of any other periods. And previously, only a few scattered periods had been ruled out.
110
Nathaniel Johnston @njohnston.ca · 01/01/2025
#1 (1/4): Phoenices. A phoenix is an oscillator in which every cell dies in every generation (and thus every alive cell was dead in the previous generation, hence the name). The first known phoenix has period 2: conwaylife.com/wiki/Phoenix_1
The "phoenix 1" oscillator in Conway's Game of Life.
130
Nathaniel Johnston @njohnston.ca · 01/01/2025
Happy New Year! Just like every year, there were tons of fantastic discoveries and theorems proved in Conway's Game of Life in 2024. This is a thread for my three favourites (and the context behind them to try to convince you that they're interesting). 🧵 #MathSky
184
Nathaniel Johnston @njohnston.ca · 20/12/2024
...a more fair comparison is how ChatGPT performs compared to a typical math undergrad who has access to Mathematica and Google while writing the Putnam. And I think that the answer to that question is "eh, about the same". Thread/rant over.
0296
Nathaniel Johnston @njohnston.ca · 20/12/2024
So sure, ChatGPT is currently at the level where it can get somewhere around 20/120 on the Putnam; way better than most math undergrads. But if we're talking about the contribution of ChatGPT or AI in general here...
160
Nathaniel Johnston @njohnston.ca · 20/12/2024
...into a brutal monstrosity that I'm guessing only 5 or so Putnam participants will get 10/10 on? Exactly the stuff that ChatGPT didn't do.
150
Nathaniel Johnston @njohnston.ca · 20/12/2024
They could ask Mathematica for the first few coefficients in the generating function, put those into 1x1, 2x2, and 3x3 matrices, compute their determinants, and spot the pattern. None of that is hard. What changes question A6 from a routine (but tedious) exercise that any math undergrad can do...
150
Nathaniel Johnston @njohnston.ca · 20/12/2024
If students had access to computers with Mathematica installed on them while writing the Putnam, they could get 1/10 or 2/20 on these questions too. And I don't mean the good/strong/gifted/brilliant students. I mean the very typical undergraduate math students.
1101