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. 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.

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

(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.)

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.

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.

(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 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.