# Math(s)! Currently: The Quantum 36 Officers Problem

Discussion in 'General Chatter' started by Exohedron, Mar 14, 2015.

1. ### ExohedronDoesn't like words

TIL that Karl Marx started writing a manuscript on calculus that, while apparently unaware of the work of people like Cauchy, nevertheless managed to anticipate some of the developments in the interpretation of calculus that for the mainstream only came in the 20th century, in particular nonstandard analysis.

• Winner x 1
2. ### ExohedronDoesn't like words

Today I learned that, while most mathematicians take for granted that for any infinite set A, AxA has the same size as A, that is in fact equivalent to the axiom of choice. Of course, most mathematicians also take the axiom of choice for granted.

• Informative x 1
3. ### ExohedronDoesn't like words

Another use for categories: talking about things that don't exist.

For instance, quantum groups don't exist. That is to say, there is no set with a binary operation and a specified point such that the group laws hold, and also where the function ring of the object is noncommutative; sets don't work that way.

There is also no field with one element; fields specifically have the axiom that 1 is not 0, but you need to have both in the field, so your field needs to have at least two elements. There is a ring with one element, but it isn't a field, and don't act like a field.

But! Categories allow us to treat said non-objects as if they were actual objects.

For instance, we can talk about the category of linear representations of a group. These are the maps from the group to matrices where the group operation becomes matrix multiplication. And these categories have particular properties that allow us to study the groups. For instance, the Feit-Thompson theorem that says that every group of odd order is solvable uses representation theory.
And we can similarly talk about the category of linear representations of a quantum group! Even though the quantum group doesn't exist as a set, we can use the data describing the quantum group to define a category of representations, and we can use this category to study the quantum group in the way that we use the category of representations to study a group.

We can also use category theory to talk about virtual representations, where the representations themselves don't actually exist, for instance by requiring the matrices to have negative dimension, but we can still talk about their behavior because we have the category structure.

Given a field, we can talk about geometric spaces defined using the field. For instance, we can say "take the vector space Fn and take the space of solutions to the polynomial P(x)" and that gets us a geometric object, and we can study the category of these spaces. For instance, we can define a notion of a "curve", a one-dimensional thing, even when the field isn't the reals, and the category tells us how these one-dimensional things behave.
And we can build such a category for the field with one element! It's a strange category, because it's built from a strange field, but we can still do it! And the relations between the spaces in this category look like the relations for spaces built from fields that actually exist, so we can say things about this field with one element based on things we learned from fields that actually exist by moving through this category language.
This is one way to "prove" the Riemann Hypothesis: there's an analogue for the Riemann Hypothesis that is true for function fields of curves defined over a field, and the integers would be the function field for a curve defined over the field with one element, if the field with one element existed. So if the field with one element actually existed, then the Riemann Hypothesis would necessarily be true!

The point is, categories allow us to make analogies between things that do exist and things that technically don't exist, or at least that don't exist in the same sense as the things that do exist.

4. ### ExohedronDoesn't like words

For those of us who like innocuous-looking axioms that provide surprising results, here's a set of six axioms that look purely algebraic that end up forcing a category to be (equivalent to) either the category of real Hilbert spaces or the category of complex Hilbert spaces.
The tricky bit, in my opinion, is showing that Solèr's theorem applies, which then forces the scalar field to be either the reals or the complex numbers (having first shown that there are scalars and that they do form a field).
https://arxiv.org/abs/2109.07418

So another step closer to putting quantum mechanics on really algebraic foundations. Which I would appreciate because I don't understand analysis at all.

• Useful x 1
5. ### ExohedronDoesn't like words

So nostalgebraist-autoresponder is a GPT-3 bot that generates human-like text via a large neural network trained on a corpus of a lot of stuff from the internet, plus trawling through nostalgebraist's own tumblr.

Anyway, here's some fake category theory

• Informative x 1
• Useful x 1
6. ### ExohedronDoesn't like words

The Quantum 36 Officers Problem

Apocryphally, Euler was once challenged by Catherine the Great to solve the following problem: there are six regiments and six ranks that an officer can have, and each regiment sends you 6 officers, one of each rank. So you have 36 officers total. And for some reason, you want to arrange them in a square so no row contains two officers of the same rank or from the same regiment, and no column contains two officers of the same rank or from the same regiment. Can you find such an arrangement?

Let's look at a simpler problem. Suppose we only care about regiments, and there are only three regiments, call them A, B and C. Then we have a solution that looks like

A,B,C
B,C,A
C,A,B

We call such an arrangement a Latin Square, where there are n labels and no label appears twice in the same row or column. So the condition on regiments is exactly the condition on Latin Squares.
The condition on ranks is also the Latin Square condition. Suppose there are three ranks, 1, 2 and 3. We have a solution that looks like

1, 2, 3
3, 1, 2
2, 3, 1

Furthermore, we can combine the two solutions to get a solution to the 9 officer problem:

A1, B2, C3
B3, C1, A2
C2, A3, B1

We call such a thing a Graeco-Latin Square, wherein each no officers from the same regiment have the same rank, and we have to arrange them into a square where no rank or regiment shows up twice in the same row or column. You can probably, with a bit of work, show that there isn't any Greco-Latin Square for two regiments and two ranks. Just not enough room to maneuver. So let's scale up. What about, say, 4, or 5?

A1, B2, C3, D4
B4, A3, D2, C1
C2, D1, A4, B3
D3, C4, B1, A2

A1, B2, C3, D4, E5
B5, C1, D2, E3, A4
C4, D5, E1, A2, B3
D3, E4, A5, B1, C2
E2, A3, B4, C5, D1

Do you see a pattern? What about 6?

Because I want to get to the real fun part, I'm just going to tell you that there isn't a solution for 6. Euler found solutions for all odd n and all multiples of four and figured out that there were no solutions for n = 2 or 6, and conjectured there were no solutions for n = 2 mod 4. It turns out that there are in fact solutions for n = 2 mod 4 except when n = 2 or 6; the solution for n = 10 was one of the first examples of computer-aided combinatorics.

But! Note the title of this post. Let's get quantum.

We start by rethinking the problem a little bit. Instead of saying "lets arrange officers", we'd rather just say "here's a square grid, put some labels on the squares." So what we want is a map from the (i,j) square on the grid to a pair (k, l) where k indicates regiment and l indicates rank. Call this map φ.
We can write φ as a matrix Uij,kl. In this case, we would write the state of the grid as
Σi,j,k,l Uij,kl |i>|j>|k>|l>
where |i>|j>|k>|l> indicates that the officer in row i and column j is from regiment k and has rank l.
A solution to the officers problem says that φ is a permutation of pairs (i,j) to pairs (k,l), since no pair of (regiment, rank) shows up twice. But we can also read φ as a map ρ from pairs of (row, regiment) to (column, rank) since no regiment shows up twice in the same row and hence specifying (row, regiment) also specifies a column that the officer from that regiment shows up in, and also the specifies the rank of that officer, and this map ρ is also a permutation. Similarly, we get a map σ from pairs of (row, rank) to (column, regiment) for the same reason, and σ is also a permutation.
In terms of matrices, we get ρ giving the matrix Uik,jl and σ giving the matrix Uil,jk, which are all basically the same matrix as Uij,kl but with the indices moved around. The point is that for a solution of the officers problem, all of these matrices are permutation matrices, i.e. that each row in the matrix has exactly one entry that's 1 and the rest are 0, and each column in the matrix has one entry that's 1 and the rest are 0.

If we want to change this to a quantum problem, we replace "permutation matrix" with "unitary matrix", i.e. a matrix with complex entries such that UU = I, where † indicates complex-conjugate-transpose. And so a solution to the quantum officers problem would be a unitary matrix Uij,kl such that the corresponding matrices Uik,jl and Uil,jk are also unitary.

What does this mean for the contents of the grid? Since we're no longer using permutation matrices, rather than each officer having a well-defined regiment and a well-defined rank, we instead get superpositions of (regiment, rank) pairs. Moreover, the officers are entangled with each other: the (regiment, rank) superpositions for each officer are not completely independent of those for the other officers.

Anyway, it turns out that although the classical 36 officers problem is impossible, the quantum 36 officers problem has a solution! Also the solution is related to certain quantum error-correcting codes. See this paper for details:
Thirty-Six Entangled Officers of Euler: Quantum solution to a classically impossible problem

7. ### ExohedronDoesn't like words

TIL that algebraic geometers got super lucky terminology wise, in that the reason that abelian varieties are called such is not due to them being commutative as groups! Rather, Abel was looking at generalizations of elliptic integrals and those all lead to varieties that admit group structures which all happen to be commutative!

From now on, I'm going to pretend that this is only fact about algebraic geometry that I know.

[EDIT] Okay, apparently it's the other way around: commutative groups are called abelian because they're the Galois groups of the polynomials that give us abelian varieties. Source: David A Cox
This makes the fact a lot less fun, that it's not a coincidence.

Last edited: Mar 17, 2022