Nathaniel Johnston

Nathaniel Johnston

@njohnston.ca

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

382 followers 127 following113 posts

Nathaniel Johnston

OpenAI just dropped some 400 math papers all at once, one of which disproves the PPT-squared conjecture: github.com/openai/math/...

github.commath/preprints/Entanglement-with-zero-distillable-secret-key-in-local-dimension-ten-September-27-2026/paper.pdf at main · openai/mathContribute to openai/math development by creating an account on GitHub.

Nathaniel Johnston

I am exactly 0% surprised that this conjecture is false (I vaguely recall telling Vern Paulsen, when he told me about this conjecture, that I would eat my hat if it's true). But people have worked *hard* to prove and to disprove it.

Nathaniel Johnston

New preprint today. I (with AI) proved the S_{n,n} conjecture from spectral graph theory: arxiv.org/abs/2609.26895

arxiv.orgThe Laplacian $S_{n,n}$ conjecture is trueThe "$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 ...

Nathaniel Johnston

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.orgSharp bounds for perfect quantum state classification beyond antidistinguishabilityA 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...

Nathaniel Johnston

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.

Nathaniel Johnston

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.orgPPT states of almost maximal Schmidt numberWe 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 ...

Nathaniel Johnston

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.

Nathaniel Johnston

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.orgA partial-trace matrix inequality and Werner-state distillabilityMotivated 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...

Nathaniel Johnston

lol, here's a fourth: arxiv.org/abs/2607.21367

arxiv.orgA solution to 2-copy distillability of Werner statesEntanglement 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...

Nathaniel Johnston

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.orgA partial-trace matrix inequality and Werner-state distillabilityMotivated 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...

Nathaniel Johnston

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”.

Nathaniel Johnston

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?

Nathaniel Johnston

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.orgEnumeration of Laplacian integral and {-1,0,1}-diagonalizable graphsA 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...

View full thread

Nathaniel Johnston

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.

Nathaniel Johnston

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).

Nathaniel Johnston

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.orgEnumeration of Laplacian integral and {-1,0,1}-diagonalizable graphsA 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...

Nathaniel Johnston

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).

Nathaniel Johnston

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.

Nathaniel Johnston reposted

@vrusso.bsky.social

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

Nathaniel Johnston

Huge shout-out to authors who put humour, even very mild humour, in their papers. You keep me awake.

Nathaniel Johnston

The paper is: arxiv.org/abs/2508.11043

arxiv.orgDyadically resolving trinomials for fast modular arithmeticResidue 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 ...

Nathaniel Johnston

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.comA hierarchy of eigencomputations for polynomial optimization on the sphere - Mathematical ProgrammingWe 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...

Nathaniel Johnston

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.

Nathaniel Johnston

New paper published today! "The factor width rank of a matrix", with Shirin Moein and Sarah Plosker: www.sciencedirect.com/science/arti...

sciencedirect.comThe factor width rank of a matrixA 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…

Nathaniel Johnston

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?"

Nathaniel Johnston

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.

Nathaniel Johnston

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.comDesmos | Graphing Calculator

Nathaniel Johnston

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.

Nathaniel Johnston@njohnston.ca

To see why this line of reasoning falls flat to me, let's look at its answer to this year's question A6. If you don't want to read the technical details of the question, all that really matters here is that the question asks you to compute a formula for something.

Nathaniel Johnston

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.comVector Calculus - Lecture 1: Paths and CurvesYouTube video by Nathaniel Johnston

Nathaniel Johnston

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

View full thread

Nathaniel Johnston

#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.comUnproven conjectures - Page 13 - ConwayLife.com

Nathaniel Johnston

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/

Nathaniel Johnston

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

View full thread

Nathaniel Johnston

#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.orgThe still-Life density problem and its generalizationsA "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...

Nathaniel Johnston

#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.

Nathaniel Johnston

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

View full thread

Nathaniel Johnston

#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.com22-bit still life syntheses - ConwayLife.com

Nathaniel Johnston

#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.

Nathaniel Johnston

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

View full thread

Nathaniel Johnston

#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.comGemini - LifeWiki

Nathaniel Johnston

#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.

Nathaniel Johnston

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

View full thread

Nathaniel Johnston

#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.comEvery finite phoenix has period 2A 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…

Nathaniel Johnston

#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.

Nathaniel Johnston

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

View full thread

Nathaniel Johnston

#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.

Nathaniel Johnston

#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.

Nathaniel Johnston

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

Nathaniel Johnston

#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