The coprimality spine

Several entries in the ledger count the same thing on different fractals: the points of a digital design whose coordinates share no common factor. The Sierpinski triangle gives 16/(3*Pi^2), the carpet 189/(32*Pi^2), the Vicsek plus 27/(4*Pi^2), the Menger sponge (513/520)/zeta(3). Four fractals, four constants, and no obvious reason they should be related. They are one theorem with four inputs, and this page is that theorem.

The short version: the base of the design contributes an exact factor, known in closed form at every finite level, and every prime away from the base contributes the classical factor 1 - p^(-D). The first half is proved. The second half is proved one prime at a time and open as a whole, and the gap between those two statements is a single named lemma that nobody here has closed.

Every claim below carries a tag. Proved means a proof is given or restated here. Verified means recomputed from scratch for this page. Conjecture means supported and open.

The object

A design is a triple (q, D, F): a base q >= 2, a dimension D >= 2, and a set F of filled digit-vectors, F a subset of {0,...,q-1}^D with k = |F| >= 2. The level-n set is

S_n = { x in [0, q^n)^D : every base-q digit-vector of x lies in F }

and it holds exactly k^n points, one per string of n choices from F. This is the same substitution rule as the core, read on coordinates rather than on cells. The count of interest is

A(n) = #{ x in S_n : gcd(x_1, ..., x_D) = 1 }

and the question is what A(n)/k^n converges to.

One structural condition matters throughout. Let L be the subgroup of Z^D generated by the differences F - F, and m(F) its index. The design is spanning when m(F) = 1. Non-spanning designs collapse onto a proper sublattice or a line and are genuinely outside the theory, not anomalies inside it — base 2, D = 2, code 9 is a diagonal pair whose whole fractal is the line i = j, and its coprime count is stuck at 1 forever. The census marks these DEGEN and excludes them from the density claim.

Theorem 1: the base is exact at every finite level

For every squarefree e dividing rad(q) and every n >= 1:

#{ x in S_n : e | x_i for all i }  =  k_e * k^(n-1),
k_e = #{ v in F : e divides every component of v }.

Proved. Every prime dividing e divides q, and e is squarefree, so e | q*y for every integer y. Write x = v_0 + q*y with v_0 the least-significant digit-vector and y the point of S_(n-1) above it. Then e divides every x_i exactly when it divides every component of v_0. So the last digit-vector is pinned to one of the k_e admissible corners and the other n - 1 are free. There is no error term and no asymptotics: this is an identity at every level.

When q = p is prime, more is true. The only vector of {0,...,p-1}^D divisible by p is the zero vector, so x = p*y maps {x in S_n : p | x} bijectively onto S_(n-1) with gcd(x) = p*gcd(y), and iterating,

#{ x in S_n : p^a | gcd(x) }  =  a_0^a * k^(n-a),    a_0 = 1 if 0 is in F, else 0.

Proved. Every design is therefore its own Euler factor at the base prime, and the factor is self-similar rather than approximate. The Vicsek plus is the extreme case: it demands digit 1 in some coordinate at every position, so the zero vector is absent, a_0 = 0, and no point of the plus fractal has gcd divisible by 3 at any level. That is why its density carries no Euler factor at 3 at all, and why 27/(4*Pi^2) is larger than 6/Pi^2.

Recomputed from scratch for this page on six designs — the gasket and the or-triangle to n = 8, the carpet and the Vicsek plus to n = 6, the base-6 sample below to n = 5, the sponge to n = 4 — by direct enumeration of S_n rather than by the census engine, matching the identity on the integer at every one of those levels and every squarefree e, and the prime-base corollary likewise for every exponent a. Verified. The census engine lab/census/coprime/general.py runs the same check at n = 4 on all 763 design lines, including the degenerate ones, with zero failures; the identity does not need spanning.

The bracket, and why it does not factor

Mobius inversion over the base primes turns Theorem 1 into a single exact number, the bracket:

B(F) = Sum_{e | rad(q)} mu(e) * k_e / k .

B(F)*k^n is exactly the number of points of S_n whose gcd is coprime to q, at every level, with no error term. Proved, immediately from Theorem 1.

At a prime base the bracket is just 1 - a_0/k and nothing interesting happens. At a composite base it is the whole story, because divisibility by the different base primes is correlated through the corner set. The design at base 6, D = 2 stored as code 34376528265 in lab/census/coprime/census_named.txt has k = 8 corners with k_2 = 3, k_3 = 2, k_6 = 1, so

B(F) = 1 - 3/8 - 2/8 + 1/8 = 1/2,   while   (1 - 3/8)*(1 - 2/8) = 0.46875 .

Treating "divisible by 2" and "divisible by 3" as independent is wrong, and it is wrong by an exact amount at every finite level:

Proved (Theorem 1 with inclusion-exclusion over {2, 3}) and Verified to the integer by enumeration for this page. The local truth at the base is the bracket, not a product of per-prime factors — the cleanest thing in the program that a prime base cannot show you.

Away from the base: uniform contraction

The primes not dividing q behave classically, and the reason is a contraction that holds for every spanning design at once. For gcd(d, q) = 1, a nonzero t in (Z/d)^D, and r = ord_d(q), put

f_l(t) = (1/k) * |Sum_{v in F} e(q^l * <t, v> / d)|,   e(x) = exp(2*Pi*i*x).

Lemma A. Prod_{l=0}^{r-1} f_l(t) <= c(q, k) := 1 - (2/k)*(1 - cos(Pi/(2*q))) < 1.

Proved. Spanning gives v, v' in F with delta := <t, v - v'> nonzero mod d; otherwise <t, w> = 0 for every w in F - F, forcing t = 0. Let y_l be the distance from q^l * delta / d to the nearest integer. Since gcd(q, d) = 1 the orbit is purely periodic and never hits 0, so every y_l > 0. Whenever y_l < 1/(2*q) one has exactly y_(l+1) = q*y_l; if every y_l in one period were below 1/(2*q), a full cycle would return y_0 = q^r' * y_0 > y_0, impossible. So some l0 in the period has y_l0 >= 1/(2*q). Split the character sum at l0 into the pair v, v' and the other k - 2 terms:

|Sum_{v in F} e(q^l0 * <t, v> / d)|  <=  (k - 2) + 2*cos(Pi*y_l0)  <=  k - 2 + 2*cos(Pi/(2*q)).

Divide by k; every other factor is at most 1.

The constant is universal — it depends only on q and k, not on which corners F holds — and it is not sharp. Two rows below need naming: the or-triangle is base 2, D = 2, code 14, the design that keeps every digit pair but (0,0) — equivalently the pairs with i OR j = 2^n - 1, of which there are 3^n — and the base 6 sample is code 34376528265 from the section above. Recomputed here over every nonzero character to every modulus coprime to q in the range searched:

Verified. No violation anywhere, and the slack is large — the gasket's true contraction is 1/3 against a bound of 0.80. Sharpness is not the point; being below 1 for every design at once is.

Two consequences follow with no further work.

Corollary (equidistribution rate). For gcd(d, q) = 1 and any a in (Z/d)^D,

| #{x in S_n : x = a mod d} / k^n  -  1/d^D |  <=  c(q, k)^floor(n / ord_d(q)).

Proved, by character orthogonality: the principal character gives 1/d^D, each of the other d^D - 1 contributes at most one factor of c per complete orbit cycle among the n digit positions. Verified for the gasket and the carpet at d = 5, where the measured deviation stays well inside the bound at every level tested (gasket at n = 10: deviation 0.0015 against a bound of 0.65).

Corollary (base peel). For squarefree d = e*m with e | rad(q) and gcd(m, q) = 1, writing T_d(n) = #{x in S_n : d | x_i for all i}, the last digit-vector is pinned mod e by Theorem 1 and the rest is a shifted residue class mod m, so

T_d(n) / k^n  =  (k_e / k) * (1 / m^D)  +  O(c(q,k)^floor((n-1)/ord_m(q))).

Proved. At a prime base with 0 in F it degenerates to an exact identity, T_(q*m)(n) = T_m(n-1). Verified for the gasket at m = 3, 5, 7, 11 and for the carpet at m = 2, 5, 7, exact on the integer at every level tested.

The master density: one half proved, one half open

Combining the exact bracket with the classical factor everywhere else gives the formula the whole census is measured against:

delta  =  B(F) * Prod_{p not dividing q} (1 - p^(-D))
       =  B(F) * (1/zeta(D)) * Prod_{p | q} (1 - p^(-D))^(-1).

What is proved. For every spanning design,

limsup_n  A(n)/k^n  <=  delta .

Fix z and sift only by the primes up to z. Coprimality implies z-sifted, so A(n) is at most the sifted count; that count is a Mobius sum over finitely many squarefree moduli, each handled exactly by the base peel, and it converges as n grows to B(F) times the partial Euler product over p <= z. Letting z grow gives the bound. Nothing conditional enters: z is fixed before n moves. Proved.

What is not. The matching lower bound needs the sifting level to grow with n, and that needs a uniform tail estimate. So the limit statement

A(n)/k^n  ->  delta

is a Conjecture with a proved mechanism — proved prime by prime, unproved in the interchange of limits. It is tagged Conjecture in the ledger for every sequence that depends on it, and nothing on this page upgrades it.

Lemma B, the open capstone.

lim_{z -> infinity}  limsup_n  (1/k^n) * Sum_{p > z, p not dividing q} T_p(n)  =  0.

Every other step in the program is proved; this one is not, and it is the only one missing. The honest description of its state: the naive bound that drops one of the D divisibility conditions loses a full factor of p, so it misses by a logarithm, while the truth has a whole factor of p in hand — recovering any p^(-eps) would close it. That is a gap, not a proof sketch. An earlier argument in the research notes claiming to close it was audited and found vacuous for the great majority of the primes involved. No literature is cited for it here because none was read for this page; treat it as an open tail estimate of large-sieve type and nothing more.

Shear identities

The shear theorem. If sigma is in GL_D(Z) and sigma(F) still lies inside {0,...,q-1}^D, then sigma acts digit-wise with no carries, maps S_n(F) bijectively onto S_n(sigma F), and preserves gcd because it is unimodular. The two designs therefore have identical counting sequences at every level, not merely the same limit. Proved, in one line.

This is why the census collapses so hard. At base 2, D = 2, the shear (i, j) -> (i, i+j) carries code 7 to code 11 and (i, j) -> (i+j, j) carries it to code 13; all three share the sequence 2, 4, 12, 34, 122, 362. Verified by recomputing the images and the codes.

The converse is open and was not checked: whether every collision in the census is explained by a shear is unknown, and the census identifies a sequence by its first six terms only — by five or four on the 14 lines where the point budget stops sooner — so its "distinct" counts are distinct term-vectors rather than proven-distinct sequences.

The census

lab/census/coprime/ holds a full enumeration: every design with k >= 2 at base 2 in dimensions 2 and 3, every design at base 3 in dimension 2, the Menger sponge, and two base-6 samples. Each line records the bracket, the predicted delta, the measured ratio at the deepest level the point budget allows, the first six terms — five at k = 8 and k = 9, four for the sponge, where the budget stops earlier — the exact-factor check, and the spanning index.

Verified, recounted from the stored census files for this page. Zero designs are flagged: the exact base-local identity passes on all 763 lines and every spanning design lands within the tolerance of its predicted density at the depth reached.

Two cautions travel with that table, both of them real. The OK verdict is numerical agreement at a shallow level inside a flat tolerance of 0.06, not a proof — the point budget caps each design at 200000 points, so a k = 3 design reaches n = 11 while the sponge only reaches n = 4, where it measures 0.7719 against a prediction of 0.8207 and passes only because the tolerance is loose that far up. And the deduplication counts are per-family and first-six-terms only. Each census file's own summary line counts term-vectors over every design of its family, degenerate ones included — 5, 35, 109 and 131 — while the column above keeps only the spanning ones. The research notes quote a figure of "about 240" distinct base-3 sequences; that is 109 + 131, the two base-3 half-files added, and across both halves together there are 219 distinct term-vectors among the 502 designs, 175 of them spanning. The smaller numbers are the right ones.

The four named instances

Each ledger entry in this family is one line of the census, and the terms match on the integer. Verified, recomputed independently for this page and cross-referenced against the stored census files. The census prints from n = 1; the ledger and the b-files start at n = 0, where all four entries read 0.

Feeding those four brackets into the master formula reproduces the four constants exactly — (2/3)*(4/3) = 8/9, (7/8)*(9/8) = 63/64, 1*(9/8) = 9/8 against 6/Pi^2, and (19/20)*(27/26) against 1/zeta(3). Verified, exact arithmetic. The three planar ones appear as rational multiples of 6/Pi^2 in pi out of the stack; the ledger holds the canonical statement of all four, and each is Conjecture there.

Against the stored b-files, the convergence:

Verified, read off the b-files in lab/sequences/ and recomputed. The Vicsek row is the honest one: its approach is non-monotone, n = 13 sits further from the limit than n = 12, and the support there is weak. Support, not proof, in every row.

A fifth design shows the mechanism at its cleanest. The or-triangle — base 2, D = 2, code 14 — forbids the digit pair (0,0), so a_0 = 0, B(F) = 1, and the predicted density is 8/Pi^2 = 0.810569 against a measured 0.811800 at n = 11 — the classical 6/Pi^2 with the factor at 2 removed entirely, exactly as for the Vicsek plus at 3. Its terms are 3, 6, 22, 58, 200, 576. It is a worked illustration only: no b-file, no second independent generator, no novelty check, so it is not a ledger sequence and is not claimed as one.

What this page does not cover

Two things sit deliberately outside it, and neither is an empty box.

Pairwise coprimality — the sponge condition gcd(i,j) = gcd(i,k) = gcd(j,k) = 1 behind menger_pairwise in the ledger — is a different object, but its base-local half survives intact. Exactly 13 of the sponge's 20 legal digit-vectors have no coordinate pair both 0, so the same last-digit argument as Theorem 1 pins the factor at 3 to 13/20, replacing the full-grid factor 20/27. Verified by enumeration here, and carried as proved in the ledger. What has no analogue is the sieve half: the pairwise condition inverts over three moduli at once and the master theorem above has not been carried out for it, so the ledger's constant stays Conjecture there.

Designs with 1 < m(F) < infinity are the other exclusion, and they are not hypothetical — the census holds 95 of them, 82 at index 2, 4 at index 3, 9 at index 4, all marked DEGEN. Base 3, D = 2, code 13 is the plainest: its corners are (0,0), (0,2), (1,0), so the second coordinate is built from digits 0 and 2 alone and is even at every level, leaving an uncorrected Euler factor at 2. Its measured ratio is still near 0.3051 at n = 13 against a predicted 0.455945 — the formula on this page is simply wrong there, which is why the census excludes it. Verified, recounted from the idx column and recomputed to n = 13. Repairing such a design needs a corrected factor at every prime dividing m(F), from an automaton on cosets of L; none is derived here.

The base is exact, the rest is classical, and the join is one lemma short.