AI-authored extension to king lattice polyplets, A006770

[Jason Parker-Burlingham]

Hello,

I have contributions I'd like to make regarding the king lattice polyplets
(A006770), created with heavy AI assistance over the last several months.
I'm bringing the question here instead of suggesting an edit to the sequence
because

(a) the code that computed new terms was wholly LLM generated and I'd like
a chance to have it scrutinized and verified by someone else, should
some brave soul decide to step forward;

(b) in the course of finding a way to push the sequence further I have found
a triangular sequence based on this one that gave up some real insight.
Again I would welcome any assistance verifying it.

I have extended A006770 to a(40) = 56749893611764175164545926946127 and have
a prospective value for a(41). I did this by having the LLM write
Redelmeier enumeration code, which I used to confirm all existing terms and
generate up to a(22).

Then, realizing that individually counting polyplets was going to be
prohibitive, searching the literature found the transfer matrix method. I'm
reasonably confident that I understand the basics of the approach; the code
counts polyplets by counting them per state, where the state is the k-th
column of a polyplet of (bounding box) height H along with some book-keeping
for number of cells remaining, whether this column is the top and/or bottom
of the polyplet, etc. This was able to push the result to a few more terms.

At this point I asked if it was useful to count polyplets _by height_.
Since we can't have H > n, this suggests a triangular sequence, T(n,H) such
that the sums of rows count polyplets of a given size:

1
1, 3
1, 10, 9
1, 27, 55, 27
1, 68, 248, 240, 81
1, 167, 996, 1480, 945, 243
1, 406, 3775, 7898, 7273, 3510, 729
1, 983, 13837, 39119, 47066, 32193, 12555, 2187
1, 2376, 49676, 185198, 278240, 241864, 133326, 43740, 6561
1, 5739, 175964, 850650, 1558399, 1631340, 1134865, 527094, 149445, 19683

Immediately we see that the diagonal is 3^(n-1) and this is because at each
row of the max height polyplet after the first we have 3 choices about how
to place it, left, right, center. Furthermore the "next" diagonal has a
closed form because the height n-1 polyplet is two 3^(n-1) polyplets "glued"
together by one row with two cells in it. After accounting for the
different options there a relatively simple closed form pops out:

T(n, n-1) = (25n - 45) . 3^(n-4)

From there the combinations get harder to account for but there is a general
form:

T(n, H) = P_k(n) . 3^(3H-2n-1) where k = n-H, when H > n/2

The LLM eventually produced a Lean proof of this, and it was useful in
computing the remaining terms up through a(40), because P_k(n) can be
determined by computing earlier rows of T(n, H); this reduces the number of
terms that needs to be explicitly computed to just T(n, H <= n/2). (It also
turns out that the left-hand side of the triangle has simple closed forms,
too, but these aren't as useful in terms of the speedup since there are
comparatively fewer animals of small height.)

I have counted free, bilateral, asymmetric and non-polyomino polyplets up to
n=32 and one-sided polyplets to n=34. Where relationships exist between the
counts, that's asserted as a check. Burnside congruences were also tracked
and used to verify counts.

To give more confidence in the transfer-matrix terms beyond the reach of
Redelmeier, a *second* transfer-matrix based approach to counting was found
that uses a coloring argument to avoid having to track connectivity
explicitly and computes "the number of connected n-cell subset of a strip of
height H where the leftmost column is fixed". (I will say frankly that this
is where the LLM badly outstripped my understanding, which is not a
comfortable place to be!)

The 41st term of A006770 has a value and there is an argument as to
correctness: T(41, 1--19) were enumerated twice (by height and by coloring);
T(41, 20) was enumerated and evaluated by closed form *but has no second
enumeration* using the coloring argument; T(41, 21--41) were given by closed
forms. Confirming the value is probably a mere operational concern but the
project had to come to a close somewhere.

Lean proofs of the following results were generated:

- T(n,n−k) = P_k(n)·3^(n−1−3k) for n ≥ 2k+1;
- A relationship between the different P_k(n) polynomials that implies
that two entries of T(n,H) determine a P_k(n);
- Existence of equivalents of these P_k(n) for diagonals of area-height
triangles for square and hexagonal lattices;
- Burnside identities relating free, one-sided and bilateral polyplet
counts to a(n) and polyplets invariant under different rotations and
reflections;
- a lower bound on the largest hole a polyplet of a given size can
contain.

The project's full output, with some attempt made to organize it and make it
easier to ingest and explore is at https://github.com/jhparkerb/polyplets .
I apologize in advance for it being LLM-authored, I have done what I can to
make it more readable, particularly `paper/technical-report.tex` which was
intended to be wholly human-authored.

I'm personally confident in: the new terms for sequences counting polyplets
of different symmetry classes, the value and contents of the T(n,H)
triangle, the existence of the polynomial-exponential closed forms.

This project began to get away from me around the a(25) mark; what started
as a simple "I wonder if Claude could write code to compute more polyomino
counts" project to explore LLM-assisted research (yes, the original target
was polyominoes) turned into something with real sprawl but perhaps also
real promise.

jasonp