Category: Uncategorized

I’m sure you know about ordered fields. The rationals, the reals, etc. But those fields can only be ordered in one way. Now consider the field Q[sqrt(2)]. That field has two possible orderings: one where sqrt(2) is positive and one where it’s negative.

What about a field with 0 possible orderings? Easy – any finite field, any complex field, insert third example here. Many to choose from.

A field with 4 orderings is also pretty easy to construct: Q[sqrt(2)][sqrt(3)] is an example – the sqrt(2) and sqrt(3) can be positive or negative as they choose.

How about a field with continuum-many orderings? I can think of two very different examples: Q[sqrt(2)][sqrt(3)][sqrt(5)][sqrt(7)] etc, and the field of rational functions. The first has continuum-many via infinitely many countable choices, and the second has continuum-many via x taking on any real value.¹ Unlike all other examples on this list, these ordered fields are not all isomorphic.

What if we want exactly 3 orderings? I struggled for a while but I think I found one. Extend the field Q with an element we call k, whose cube is one less than its triple. There are three orderings of this field.

That setup for 3 orderings can of course be generalized for higher odd numbers, and the 4 orderings setup lets you double any number of orderings that can be achieved. Altogether, that lets you get any finite number of orderings.

Any amount of orderings that can be achieved by a field can also be achieved by a commutative ring and vice-versa: any field is a commutative ring, and any commutative ring with more than 0 orderings has the same number of orderings as its field of fractions.

And, of course, the obligatory unsolved question: Is there a field with countably many orderings?

1. If x is algebraic, there are two orderings depending on whether the corresponding polynomial is positive or negative. There are also two more orderings for x being positive or negative infinity. ↩︎

I’m sure you know about ordinary graph coloring, but just in case: a k-coloring of a graph assigns to each node one of k colors such that no two nodes that share an edge share a color. Most maps are shaded with a 4-coloring of their adjacency graphs, and a Sudoku puzzle is just a puzzle of finishing partial 9-coloring of the Sudoku graph.

Fractional graph coloring is a way to generalize graph coloring to fractional color amounts. For example, the pentagon graph is 5:2-colorable, and the 9-cycle is 9:4-colorable. An a:b-coloring of a graph assigns to each node b colors out of the available a such that no two nodes that share an edge share a color. Note that an n:1-coloring is just an n-coloring. Here is an example 6:2-coloring of an unnamed graph:

From any a:b-coloring, you can get a corresponding an:bn coloring by assigning each original color to n colors (as the Wikipedia article for fractional coloring shows in its image). Note that the reverse cannot be performed; the above graph that has been 6:2-colored cannot be 3-colored, and was in fact specifically chosen because of this.

I was trying to figure out the fractional chromatic number of the icosahedron graph for an earlier part of this article. First I assumed that it was 7/2, then I thought it was 18/5, then I tried 11/3. I still don’t know what it is. “Hang on,” you might be wondering, “Why are these actual fractions?” There is a way to generalize fractional graph coloring to actual fractional numbers of colors: an x-coloring (with x a real number) assigns each node of a graph to a set of real numbers with measure 1 that is a subset of the interval [0,x]¹, and no two adjacent nodes can share a color. Alternatively, you can consider the fractional chromatic number to be the minimum of the fractions you get if you interpret the coloring numbers as fractions.

An infinite graph can be constructed to have any irrational fractional chromatic number larger than 2: Find a series of fractions that converge to that number from below (If we were to do this for pi, the first three could be 3, 25/8, and 47/15), and take the disjoint union of the corresponding Kneser graph for each one.

An unproven conjecture: If some graph can be a:b-colored, and bc > ad, then it can also be c:d-colored. Equivalently: If bc > ad, then the Kneser graph KG_a,b can be c:d-colored.

1. It doesn’t actually matter if the interval is closed or open, because points have measure 0. I just think square brackets look better. ↩︎

The definition for ordinal-time cellular automata is simple:
Generation 0 is just the initial state, as it always is.
Generation n+1 is the cellular automaton applied to generation n, as it always is.
Generation A, with A being a limit ordinal, makes any cell that is alive infinitely often just before generation A be alive.

Here is a video of the blinker’s evolution in infinite-time Conway’s Game of Life up to generation ω+8:

The blinker’s evolution actually continues past the generations shown above, and it eventually stabilizes at generation ω5+25.

Other common oscillators stabilize way earlier: a toad stabilizes into a block at generation ω+3, a beacon is already stable (even though it’s oscillating), a clock stabilizes into a fleet at generation ω+8, and the n-barberpole stabilizes into a longⁿ ship at generation ω, and the pulsar stabilizes into eight blocks at generation ω+22.

No pattern has a known stabilization point past ω²2. To be clear, in this post, stabilization refers to the first generation that doesn’t stop appearing at some point.

The only known online appearances of this are https://googology.fandom.com/wiki/User_blog:LittlePeng9/Infinite_time_game_of_life, which defines it, a thread in the #misc-ca channel of the ConwayLife Lounge Discord server that has links to all of the other examples in this list, https://scratch.mit.edu/projects/1267474269/, which simulates it on random initial states for generations less than ω³ (and lets you move through the generations freely!), and this blog post.

It is a well-known “fact” that any valid Rock-Paper-Scissors variant with 5 elements must be isomorphic to Rock-Paper-Scissors-Lizard-Spock – that’s the only way for every element to have two things that beat it and two things that it beats. However, there is in fact a second option we invented recently.

It’s called Rock-Paper-Scissors-Bomb-Defuser – Bomb beats all the old things, Defuser beats Bomb, and all the old things beat Defuser. This is still a valid variant; although some elements are more useful than others, every element is useful.

So what really is the rule for a variant being valid? It’s simple: there must be a strategy that ties with any other strategy. For standard Rock-Paper-Scissors, it’s playing every element with a 1 in 3 probability, for Rock-Paper-Scissors-Lizard-Spock it’s playing every element with a 1 in 5 chance, and for Rock-Paper-Scissors-Bomb-Defuser it’s playing Rock, Paper, and Scissors with a 1 in 9 chance and playing Bomb and Defuser with a 1 in 3 chance.

A good rule of thumb for construction is that any pair of elements must be contained within a three-element cycle. This is a necessary condition, although this isn’t a sufficient condition – adding an element to Rock-Paper-Scissors-Bomb-Defuser that beats only Bomb and Scissors satisfies that condition, but if you calculate, it turns out that new element is useless.

Here is a proof that the only 5-element variants are the two already mentioned:
If every element beats two other elements, it must be Rock-Paper-Scissors-Lizard-Spock.
Otherwise, there must be an element that beats one element and/or an element that beats three. If an element beats one thing, then for any element other than it to form a 3-cycle with it, the thing it beats needs to beat three things. There can’t be two things that beat only one element each, because then neither of them could beat the other. So the only remaining combination is that one element beats one element, one element beats three elements, and three elements beat two elements. A quick check shows that to do that it must be Rock-Paper-Scissors-Bomb-Defuser.

I still have plenty of unknown questions:
– Are there any valid variants with an even number of elements?
– How many valid variants are there with 7 elements?
– Is there a valid variant where its tie-with-everything strategy doesn’t use one of the elements?