Formula reduction for Polyominoes

# Introduction

In the last blog, I discussed about some fundamental rules for the shape algebra. I closed with a remark on how we’re able to not construct shapes like these:

In this blog, I’ll explore a way of solving this first, then I’ll write some generalised notation so that we can talk about the length of the formula as a “feature” of the algebra and ponder over it.

# Introducing Subtraction

The rules are the exact same as adding a block, except that when we write $-1_C$ we’ll be removing the first block it hits. So, to give you a few examples:

Hopefully these examples make it clear.

All other rules stay the same. With this in place, I had to use all the existing rules to carve out the shape above, and here’s how it looks like:

$$ \left(\left(\left(\left(\left(\left(\left(\left(\left(\left(\left(\left(A_R^3+1_C\right)_C+1_C\right)^M_C+1_C\right)_C\right)_P+1_C\right)_C+1_C\right)+1_C\right)+1_C\right)+1_C\right)^M_C-1_R\right)_P-1_R\right)_C+1_R\right)_C+1_R $$

To make that clearer:

The only trick here was to leverage the pinned image. Because when we subtract, we can then subtract off exactly the middle element, which would be impossible to do so without a rule like this.

# Notation and reduction

You would have realised that there are a lot of unnecessary brackets and plus signs. I mean addition is understood, so we can get rid of those and assume addition by default. We can also get rid of the brackets because its one block at a time always going to the right.

So, a formula can be written in a simplified manner:

$$ \left(\left(A_C^4 + 1_R\right)+1_R\right) \implies A_C^{4}(1_R \cdot 2) $$

Basic translations:

1. $1_R$ + $1_R$ … $n$ times = $(1_R \cdot n)$

There are some caveats to this. For example in case of rule 1, we only do this when the latch never changes! So, if we had latched onto a column before adding multiple things, we’ll write:

$$ C1_R(1_R \cdot 3) $$

and not

$$ C(1_R \cdot 4) $$

This is because right after latching, the first $1_X$ will go to the largest X, but the subsequent ones will fall back to the defaults. Hence, we’re trying to make this relationship discrete.

# Reduction formulas

Now let’s talk about some reduction formulas. The goal of the reduction formula is that if we see the LHS anywhere in the equation, we should be able to substitute them for the RHS and leave the entire equation unchanged. This means, we need to care about the latches as well.

$$ M_{X}M_{X} = \text{empty} $$

$$ A_X^{j+k} = A_X^j(1_X \cdot k) \forall j,k \in N $$

$$ M_{X}M_{Y} = M_{Y}M_{X} \forall X \neq Y $$

So with these, we can reduce an obviously wrong formula into the simplest form:

$$ A_C^{2}1_C1_{R}M_{R}M_{C}M_{C}M_{R} \to A_C^{3}1_R $$

In the following relation, I had to latch onto X in the RHS because the LHS was latched to X. If we don’t do that, then we’ll mess up the next element’s placement.

$$ A_X^{j}(1_Y \cdot (j-1))M_Y = A_Y^{j}(1_X \cdot (j-1))M_XX $$

In fact it is this observation that led me to adding subtraction in the rules and discovering the new formula for the unspeakable shape.

Update: we wrote a script in Lean to verify this. Both sides draw the same shape, but the relation fails as a direct substitution because the final reference points are different. On the LHS the next $1_X$ goes to the default $X$ line. On the RHS the latch was just pressed, so it goes to the $X$ line with the most blocks, and in this shape those aren’t the same line.

It does work if both sides are followed by a latch. Latching resets the reference point the same way on both sides, and then the extra $X$ on the RHS isn’t needed anymore:

$$ A_X^{j}(1_Y \cdot (j-1))M_YZ = A_Y^{j}(1_X \cdot (j-1))M_XZ \quad \forall Z \in \lbrace R, C \rbrace $$

Lean checks this one as a perfect substitution for every $j$ from 1 to 15.

# Coverage

So, I was able to run some scripts to prove that we’re able to reach all the shapes up to N = 11 at least. After that the required computations go very high so I didn’t run those checks. I’ll keep updating this, but I assume there shouldn’t be a problem with coverage now with all the rules we have in place.

(For code explanations, see the next post)

# Observations

This is a simple observation:

If we’re starting from base $A_X^j$, for a figure with N blocks, if the number of “steps” needed is S then

$$ S \geq (N-j) $$

This is kinda trivial to see tbh. You will need $N-j$ new blocks to build the shape, so definitely the number of steps will exceed that since we’ll be counting $M$, $P$ and $X$ in the steps as well.

What you’re not prepared for is this empirical fact I discovered by running more scripts. I did the following:

1. For each value of N from 5 to 10, we’ll take every possible fixed polyominoes and try to find an algebra that fits it.
2. For each algebra that we find, we’ll count the number of steps. We’ll find ALL possible algebra until we have exhausted the possible branches (the approach is obviously not a naive search, I’ll talk about the code later) and move on.
3. We’ll count how many shapes fit in “i” number of “steps” and plot that.

If we count the percentage of shapes achieved for different $N$ values against the number of steps, we get this nice looking graph:

Note that fixes shapes means we’re not counting rotations and reflections as the same thing for any shape. Each operation results in a distinct shape.

Clearly the graph is shifting to the right, with the peak decreasing ever so slightly. The thing I want you to focus on right now is the correspondence between the $N$ value and the number of steps at which it peaks. They’re the same! That’s a pretty coincidence to have isn’t it. It also means that for a given $N$ value, at least empirically, more than 30% of the shapes can be generated in a minimum of $N$ steps.

Maybe there is a proof for that, I am yet to do that.

Here’s another image I want to direct your attention to. This one is plotting the average number of steps (minimum) across all shapes for a given N, against N.

This is a clear result because look at that beautiful linear growth! We roughly get

$$ \text{mean} \approx 1.2n − 1.75 $$

So, each new value of N, requires on average 1.2 times more steps.

Few things to note here:

1. N = 5 to 10 implies we haven’t encountered subtraction yet, so this is purely an additive artifact. Nothing else can be drawn from this.

2. Honestly, the search space is way too narrow to make any claims about the mean for the entire algebra. That’s an engineering mindset and that can’t work here!

Now I’ll try and prove some things, maybe we’ll have to update a few rules yet again who knows. The goal is to see if we can use this construction to first prove some well known theorems in polyominoes. After that sky’s the limit. But first we’ll talk about the code.

Let’s talk the code next.

Link for the 3rd part: part 3