# Euler characteristics

Two of the 3D designs make solids clean enough to count exactly. Fill the cubes of
a `2^n` box by a parity rule, take the union as a cubical complex, and ask for its
Euler characteristic `V - E + F - C`. Both answers are closed forms in `n`, and
they point opposite ways: one solid fills with sealed cavities, the other with
tunnels. This page is also where the project caught itself in an error — an
earlier claimed form for one of the two is wrong, and the correction is the more
interesting half of the story.

Every claim carries a tag. **Proved** means a proof is given or restated here;
**Verified** means recomputed from scratch for this page; **Conjecture** means
neither.

## The two solids

A 3D design is a subset of the eight corners of the parity cube, written as the
code `mrly_i` with `i` the sum of `2^k` over the filled corners — the naming from
[the core page](core.md). This page puts the corner `(x, y, z)` at bit
`4x + 2y + z`. At level `n` a cube position `(x, y, z)` in `[0, 2^n)^3`
survives when every one of its `n` binary digit triples is a filled corner, which
for these two codes collapses to a single bitwise test.

| code | rule | cubes at level `n` | dimension |
|---|---|---|---|
| `mrly_127` | `x AND y AND z = 0` | `7^n` (A000420) | `log(7)/log(2) = 2.8073549220576...` |
| `mrly_031` | `x AND (y OR z) = 0` | `5^n` (A000351) | `log(5)/log(2) = 2.3219280948873...` |

Both codes are the smallest in their symmetry class under the signed permutations
of the cube, so each names a class and not just one representative — and, since
reordering the coordinates is itself such a permutation, nothing here depends on
which coordinate was handed the high bit. (Proved on the core page: a code
`2^k - 1` is canonical in every dimension, and `31 = 2^5 - 1`, `127 = 2^7 - 1`.
Verified again by orbit walk in `lab/euler/chi.py`; the cube counts and both OEIS
entries were checked live.) The dimensions are arithmetic consequences of the cube
counts at scale `2^n`, not separate measurements. (Proved.)

Code 127 is the natural three-dimensional Sierpinski analogue: every corner but
`(1,1,1)`. Code 31 keeps a whole face of the parity cube plus one corner of the
opposite face, which is what makes it lopsided enough to be interesting.

## The closed forms

| code | `chi(n)` | terms from `n = 1` |
|---|---|---|
| `mrly_127` | `(13*7^(n-1) - 27*3^(n-1) + 38)/24` | `1, 2, 18, 157, 1211, 8832, 62908, 443627, 3115221, 21836062` |
| `mrly_031` | `(7 - 3*5^(n-1))/4` | `1, -2, -17, -92, -467, -2342, -11717, -58592, -292967, -1464842` |

(Proved; see the next section. Verified twice over for this page: by brute force on
the actual complex to `n = 6` and `n = 7`, and by an independent digit automaton
against all 60 and all 100 stored b-file terms, zero mismatches.)

Each also satisfies short recurrences and a rational generating function. (Proved,
being consequences of the closed forms; Verified against every b-file term.)

| code | recurrences | g.f. |
|---|---|---|
| `mrly_127` | `a(n) = 7*a(n-1) + (3^n - 19)/2` for `n > 1`; `a(n) = 11*a(n-1) - 31*a(n-2) + 21*a(n-3)` for `n > 3` | `x*(1 - 9*x + 27*x^2)/((1 - x)*(1 - 3*x)*(1 - 7*x))` |
| `mrly_031` | `a(n) = 5*a(n-1) - 7` for `n > 1`; `a(n) = 6*a(n-1) - 5*a(n-2)` for `n > 2` | `x*(1 - 8*x)/((1 - x)*(1 - 5*x))` |

The first code-127 recurrence has a sibling worth naming. Writing
`g(n) = (3 - 3^(n-1))/2`, it reads, for `n > 1`,

```
a(n) = 7*a(n-1) - 9*g(n-1) + 4
```

and `g` is not an auxiliary invented to make the line work: `g(n)` is exactly the
Euler characteristic of the two-dimensional gasket `x AND y = 0` at level `n`,
running `1, 0, -3, -12, -39, -120, -363, -1092`. (Verified for `n = 1..8` by direct
count of the 2D complex in `lab/euler/betti.py`; the recurrence Verified on all 60
b-file terms.) The 3D solid glues to its own 2D shadow, one level down.

## Why these are proofs and not fits

A closed form matching sixty terms is still a fit unless the shape of the answer is
known in advance. Here it is, and the argument is short enough to give.

Write `S` for the set of surviving cube positions. Every cell of the complex is a
translate count: the cubes are `S`, the faces normal to axis `d` are
`S` united with `S + e_d`, the edges along `d` are the union of the four translates by the
other two axes, and the vertices are the union of all eight translates by
`{0,1}^3`. Inclusion-exclusion turns each union into intersections
`N_T(n) = #{p : p - u is in S for every u in T}` over subsets `T` of `{0,1}^3`, so
`chi = V - E + F - C` is a fixed integer combination of the `N_T`.

Each `N_T` is then a digit walk. A position lies in `S` when every digit triple is
a filled corner, and subtracting a vector from `{0,1}^3` touches only the lowest
digit, so the borrow in a coordinate survives exactly until that coordinate's first
`1` digit. The entire state is therefore the three-bit record of which coordinates
have shown a `1` so far — eight states, whatever `T` is. That transfer matrix can
only gain bits, never lose them, so it is triangular and its eigenvalues are its
diagonal entries, which are digit counts computed exactly. Hence `N_T(n)`, and with
it `chi(n)`, is a sum of `q(n)*lambda^n` over a known finite eigenvalue set with
`deg q` below each multiplicity.

| code | eigenvalues with multiplicities | forced recurrence order |
|---|---|---|
| `mrly_127` | `0^1, 1^4, 2^3, 3^3, 4^3, 7^1` | at most 15 |
| `mrly_031` | `0^3, 1^5, 2^4, 3^2, 4^1, 5^1` | at most 16 |

The claimed closed forms obey recurrences of order 3 and 2, so in each case the
difference obeys one of order at most 18. A sequence obeying a linear recurrence of
order `r` and vanishing on `r` consecutive terms from the start vanishes
everywhere. Sixty and one hundred terms of agreement are far past 18, so the closed
forms are exact for every `n`. (Proved; the eigenvalue table and the b-file
comparisons are Verified by `lab/euler/chi.py`.)

## Cavities against tunnels

The two signs are not cosmetic. `b3` vanishes for any finite union of closed unit
cubes: in a nonzero 3-chain take a cube maximal in lexicographic order, and its
outermost face survives in the boundary, so the group of 3-cycles is zero. (Proved.)
Both solids also turn out to be connected at every level computed, so there
`chi = 1 - b1 + b2` and the whole characteristic is carried by one Betti number
each — a different one.

| level `n` | `mrly_127` `(b0, b1, b2)` | `mrly_031` `(b0, b1, b2)` |
|---|---|---|
| 1 | `1, 0, 0` | `1, 0, 0` |
| 2 | `1, 0, 1` | `1, 3, 0` |
| 3 | `1, 0, 17` | `1, 18, 0` |
| 4 | `1, 0, 156` | `1, 93, 0` |
| 5 | `1, 0, 1210` | `1, 468, 0` |
| 6 | `1, 0, 8831` | `1, 2343, 0` |

(Verified for `n = 1..6` by two computations that share nothing beyond the cell
census. One is Gaussian elimination over `GF(2)` on the three boundary matrices, in
`lab/euler/betti.py`. The other, in `lab/euler/dual.py`, forms no matrix at all:
`b0` is the number of 26-connected components of the filled cells, `b2` is the
number of bounded components of the complement — which Alexander duality identifies
with the rank of `H^2` — and `b1` falls out of the alternating sum. The second route
returns ranks of integral homology and the first returns `GF(2)` dimensions, so
their agreement also says there is no 2-torsion at these levels. In the first
route the alternating sum of the Betti numbers is a real check against the
directly counted `V - E + F - C`, ranks and cell counts coming from different
parts of the calculation; in the second that sum is what defines `b1`, so there
the check is the agreement between the two routes. Nothing is claimed for larger
`n`.)

Code 127 has no tunnels at all in this range — `b1` vanishes and its
characteristic is `1 + b2`, one plus a cavity count. Code 31 is the mirror image:
no cavities, and its characteristic is `1 - b1`, one minus a tunnel count. That
explains the signs, and it explains a crossref that otherwise looks like numerology.
The code-31 tunnel counts `0, 3, 18, 93, 468, 2343` are A125833, three times the
base-5 repunits: `A125833(k) = (3*5^k - 3)/4`, offset `0`. (Verified live against
OEIS, which gives that formula and `A125833 = 3*A003463`, with A003463 confirmed
there as `(5^k - 1)/4`; the identity `chi(n) = 1 - A125833(n-1)` holds on all 100
b-file terms.) The ledger records that crossref as its one novelty-search hit; it is
the tunnel count, not a collision.

## The correction

An earlier claimed form for code 31 was `chi(n) = 2 - 5^(n-1)`. It is wrong. It
gives `1, -3, -23, -123, -623`; the complex gives `1, -2, -17, -92, -467`. The
failure is already at `n = 2`, where it predicts `-3` against a true value of `-2`,
and it never recovers. (Verified: the level-2 complex was built cube by cube for
this page, giving `V = 79`, `E = 172`, `F = 116`, `C = 25` and `chi = -2`.)

The replacement `(7 - 3*5^(n-1))/4` is the proved form above. The two agree only at
`n = 1`, which is how a wrong formula survives a first glance: at the level where
checking is easiest, it is right. The habit that caught it is the same one the
ledger enforces everywhere — two independent generators before anything is
believed, and a brute force that does not know what answer it is supposed to
produce.

## Status

Neither sequence has an OEIS A-number. Both are drafts held in the lab; no
submission has been made for either — searching the live OEIS for either term
list returned nothing again for this page. [The sequence ledger](sequences.md)
carries both entries, the AND-zero and the AND-OR solid, with the terms, the
formulas and the novelty searches; the b-files and the independent generators sit
in `lab/sequences/euler_xyz/` and `lab/sequences/euler_xyorz/`. The scripts behind
this page are `lab/euler/chi.py`, `lab/euler/betti.py` and `lab/euler/dual.py`,
with their run log in `lab/euler/RUN.txt`.

> The two codes differ by two corners of the parity cube and produce opposite
> topologies: one solid that fills with sealed rooms, one that fills with
> corridors. Nothing in the rule announces which you will get. You have to count.