Blog

First, the standard definition of multiplication on these structures makes a ring and not a field. Second, the resultant ring isn’t a very interesting one: it doesn’t have any elements that aren’t either a unit or a zero divisor. Third, the ordering is completely lost when you do this. Fourth, there is no reason I can think of that you would ever multiply ordered fields. Fifth, why is there a link? Wait, don’t leave yet! There’s still eleven to fourteen words left depending on how you count! Sixth, Happy April Fools!

The smallest asymmetric graph is the empty graph, and the second smallest is the one-vertex graph. What about the third-smallest?

Any two-vertex graph has a nontrivial automorphism (swapping the two vertices), so it can’t be a two-vertex graph.
Any vertex connected to all others or disconnected from all others could be removed without increasing the amount of automorphisms, so it can’t be any graph that has such a vertex. This means it can’t be any three-vertex graph.
Any disconnected graph would contain a smaller graph with at most as many automorphisms, so it can’t be a disconnected graph.
The complement of any graph has the same number of isomorphisms, so it can’t be the complmement of any already-excluded graph.
Any graph larger than 1 vertex that is isomorphic to its own complement has a non-trivial automorphism: applying said isomorphism twice. (Corollary: the third-smallest asymmetric graph is not unique)
The previous three sentences excluded the three remaining four-vertex graphs: complement of 4-cycle, 4-cycle, and path graph respectively.
Any remaining five-vertex graph with four edges must be a tree, and either include no vertices with degree larger than two (in which case it is the path graph, which has reversal as a non-trivial automorphism), or include one vertex with degree larger than two (in which case it can only include one such vertex and the distances from said vertex to the degree-one vertices cannot be all distinct, creating a non-trivial automorphism). This also excludes the five-vertex graphs with six edges (they are complements of five-vertex graphs with four edges).
The only remaining five-vertex graphs have five edges. Either they have five vertices of degree 2 (in which case it is the pentagon graph, which is isomorphic to its complement), three vertices of degree 2 and one vertex each of degree 1 and 3 (in which case it is a cycle graph with a stick attached, which has a non-trivial isomorphism of reversing the cycle), or one vertex of degree 2 and two vertices each of degree 1 and 3 (there is only one graph that has those degrees, so it’s isomorphic to its complement).

Therefore, the third-smallest asymmetric graph must have at least 6 vertices. There are asymmetric graphs with 6 vertices:

and their complements. I am uncertain of if those four are the only asymmetric graphs with 6 vertices.

It’s possible for two D6s to be correlated in such a way that their sum is 1 + a D11. You’ll see how later. For convenience, the rest of this article will make a Dn be randomly from 0 to n-1 rather than 1 to n.

The first thing you might try after seeing an example might be trying D2 + D2 = D3. This one is simple, and also unique: (0,0) with probability 1/3, (0,1) and (1,0) with probability 1/6 each, and (1,1) with probability 1/3. The next may be D2 + D3 = D4, which is also unique, and in fact any D2 + Dn = D(n+1) is unique: (0,x) has probability (n-x)/(n^2+n), and (1,x) has probability (x+1)/(n^2+n).

It’s also possible for three D2s to be correlated so that any two of them make a D3 and their entire sum is a D4. A similar thing can be done for four D2s where any two make a D3, any three make a D4, and all four make a D5, and this can also be done for any number of D2s: the chance for any specific combination with m of n D2s landing on 1 is 1/(n*(n choose m)). This means it can also be represented by rolling a D(n+1) and picking a random combination with that many 1s, which provides a neat way to physically build this distribution.

This new probability distribution gives us an answer to the question at the start: How can we make D6 + D6 equal D11? The most elegant answer: use the construction above with ten D2s, and consider the first five as one D6 and the other five as the other D6.

I’ve been thinking: Sudoku is nice, but the middle phase where you get interesting deductions is just not long enough. So, to solve that problem, here’s a few infinitely large sudoku variants I came up with. Feel free to implement any of these.

The Staircase: Each row is offset from the next by one cell, allowing for infinitely many rows and columns while each of them contains only nine digits. Regions can be whatever nine adjacent cells you want, like Jigsaw sudoku.

The Fractal: Every cell in an n by n grid contains an n-1 by n-1 grid, and that grid’s digits are the digits in the n by n grid other than the one in the cell. Regions are jigsaw again. Technically that one only has O(n!²) cells, But given that humans can only live for about three hundred million seconds, that’s probably close enough to infinity. You could also make it one-dimensional: instead of an n by n grid, you use a single row of size n.

The Cone: Row N contains digits from 1 to N and column N also has digits from 1 to N. Regions are jigsaw (one region of each possible size). In case you don’t understand what shape the grid is, here’s an image of the grid shape recreated in Desmos:

The Hypercube: Each cell has infinitely many coordinates, each of which only has nine possibilities. The 2D slices fixing all but two of the coordinates have to all be normal Sudoku grids.

All of these have downsides: The Staircase only really has two places to make deductions from, The Fractal still sorta has starts and ends, The Fractal (1D) is one-dimensional, The Cone has only 55 cells available before you’re forced to worry about digits other than 1 to 9, and The Hypercube is hard to visualize, and actually has no valid solutions past four dimensions.

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?