carry-free-mobius

• The design Mobius nu_F of the two-digit design F = {0,1} is base-free: it is the pushforward of one function nu* on the monoid M* of products of 0/1 polynomials in Z[x], and the base enters only as the order in which nu* is summed.
• M* is the multiplicative monoid generated by the nonzero 0/1 polynomials, S* is that generating set, and nu* is the Dirichlet inverse of 1_(S*) on Z[x], which is a unique factorisation domain; evaluation P -> P(base) is a bijection S* -> S_F and a monoid homomorphism with finite fibres at every base >= 2, since an element of M* has nonnegative coefficients so P(base) = n caps every coefficient by n and deg P by log_base n, and therefore nu_F(n) = sum_(P in M*, P(base) = n) nu*(P) at every integer n.
• M* is not divisor-closed, 1 + x^2 + x^4 = (1 + x + x^2)(1 - x + x^2) with the second factor outside it, so nu* and its convolution live on the ambient monoid A of nonzero polynomials of Z[x] up to units, where nu* vanishes off M* by induction. A splits as N x R with R the classes of nonzero constant term, which is divisor-closed in A; a 0/1 polynomial is x^j b with b a 0/1 polynomial of constant term 1, so x^k b lies in S* exactly when b lies in S*_odd, at every k >= 0, and 1_(S*) is the outer product of the all-ones function on N with 1_(S*_odd) on R. Dirichlet inversion factors with the splitting and the inverse of the all-ones function on N is 1 - t, so nu*(x^k b) = 0 at every k >= 2 and nu*(x b) = -nu*(b) for every b in R.
• Every element of M* of degree d has its coefficient of x^i at most binomial(d, i), because a product of 0/1 polynomials of degrees d_1 + ... + d_r = d is dominated coefficientwise by prod_k (1 + x + ... + x^(d_k)) and each factor by (1 + x)^(d_k), so the product is under (1 + x)^d; the maximum coefficient at degree d is therefore exactly binomial(d, floor(d/2)) and (1 + x)^d attains it, which retires the crude cap 2^(level-1) the carry bound is stated against.
• lemma: the carry bound. The maximum coefficient over M* at degree below level against the exact cap binomial(level-1, floor((level-1)/2)) and the crude cap 2^(level-1) the study was first stated against; the carry-free window base_set(level), least base with every P of degree below level under base^level, against its closed form (base+1)^(level-1) < base^level; the order window base_ord(level), least base with evaluation increasing on all of M* to degree level, and the overtaking pair that breaks each; the pushforward checked term for term against the design Mobius of mrly-pairing verb inverse, with the base 2 full digit set as the control where nu_F = mu; and the first departing level of the base ladder against the window.
• sequence: the base-free ladder of nu*, its running maxima and its M(base^level) by level, the census of M* by degree and its partial sums, the maximum coefficient at the deepest degree against the packing width, and an OEIS grep against a local dump named by the environment variable OEIS_STRIPPED.
• exponent: the growth RATE of the base-free running maximum against the design's mass rate 2, the ratio max/2^level, the per-level step, the exponent log_2(max)/level, the same ratio split by the residue class of level mod 2, and geometric mean steps over the last 4, 6 and 8 levels.
• pin: the Rust ladder to level 18, printed level by level and diffed term for term against the Python running maxima, M(base^level), monoid census and maximum coefficients.
• exponent in Rust is the verb ladder: the same table one line per level as it lands, to whatever level the memory budget reaches, then the residue split, the geometric mean step over windows 4 to 20 with the hull those windows span, each of the windows 4, 6 and 8 read at the last four depths, the first level of the final rising run of max/2^level, and the working set.
• Domain: the Python holds M* to degree 17, which is 2423801 elements cumulative, for the ladder and the exponent, M* to degree 14 for the bound table, and the design Mobius to 3^16, 4^12, 5^11, 6^9 and 7^8; the Rust reaches degree 22, where the count of M* at that degree alone is 78798610 and 43676862 of those have nonzero constant term. It stores the degrees 0 to 21, which is 35121748 elements, and streams the top degree without storing it.

RUN

• uv run python research/lab/rs/carry-free-mobius/carry_free.py lemma
• uv run python research/lab/rs/carry-free-mobius/carry_free.py sequence
• uv run python research/lab/rs/carry-free-mobius/carry_free.py exponent
• bash scripts/cargo.sh cargo run --release -p carry-free-mobius -- pin from mrlyprod/
• bash scripts/cargo.sh cargo run --release -p carry-free-mobius -- ladder 22 2.5 from mrlyprod/, where the first argument is the top degree and the second the working-set budget in GB
• bash scripts/cargo.sh cargo test -p carry-free-mobius pins the Rust ladder to the Python numbers at every level to 18
• the mobius page prints the same ladder command in its own house form, CARGO_BUILD_JOBS=4 cargo run --release -p carry-free-mobius -- ladder 22 2.5, which is one recipe under two wrappers, the build lock being the only difference
• The Python lemma runs in ten seconds, sequence and exponent in seventeen each; peak resident memory is 0.60 GB in lemma and 0.58 GB in the other two.
• The Rust pin runs in one second and ladder 22 2.5 in 99 seconds; the heldMB column of the table is the working set the generator accounts for itself, 26 MB at level 18 and 2069 MB at level 23, and the peak resident memory of the process, measured outside it, is 2.41 GB in ladder 22 2.5; the ladder asserts the Python numbers at every level to 18 before it prints a deeper one, and stops at the first level whose working set passes the budget, printing that cut.
• A 0/1 polynomial is a bitmask, so every element of M* is a packed integer and multiplication of polynomials is multiplication of integers; the Python packs one coefficient to thirty-two bits, which is safe because the coefficient at degree below 18 never passes 2^17, and the Rust packs the coefficient of x^i at degree d into as many bits as binomial(d, i) has, which is the proved cap for that coefficient and no lane can carry: 312 bits hold a degree-22 element against 736 for a thirty-two bit packing, and the generator prints the coefficient it actually reaches at every degree beside binomial(d, floor(d/2)).
• The packed integer is P(2^32) in the Python and a mixed-width positional value in the Rust; both order elements by degree and then lexicographically from the leading coefficient down, which is the base-free order, and in both the divisibility of packed integers is polynomial divisibility.
• The Rust builds one degree at a time and never stores the top degree: a level is filled bucket by bucket in the two leading coefficients of the target, which are read off the source and the generator before the product is formed, so the buckets arrive already in the base-free order and the running maximum crosses them without a sort of the whole level.

WITNESSES

• the pushforward is exact term for term with 0 mismatches at base 2 to n <= 2^15, base 3 to n <= 3^10, base 4 to n <= 4^8 and base 5 to n <= 5^7, where 108978 elements of M* collapse onto 32768 integers at base 2 and 76210 values collide, and 104 values collide at base 3; the base 2 line is the full digit set, where nu_F = mu, so the classical Mobius function is the pushforward of nu* at base 2
• the degree-graded sums of nu* are 1, -2, 0, 0, ..., so the graded partial sum over degree below level reads 1 at level 1 and -1 after; the column both generators print is M(base^level), that partial sum plus nu*(x^level), which is the design Mertens at n <= base^level inclusive and reads 0 at level 1 and -1 at every level 2 to 23, matching sum_(n <= base^level) nu_F(n) = -1 inside a base's carry-free window
• the running maxima of nu* read 1, 1, 2, 3, 4, 7, 15, 23, 45, 86, 162, 331, 741, 1665, 3173, 7508, 17753, 36147, 79645, 182432, 427806, 858703, 2026147 at levels 1..23, the first eighteen matching the Python term for term, and the first twelve are absent from the local dump when OEIS_STRIPPED names one
• the census of M* by degree reads 1, 2, 5, 11, 27, 61, 144, 331, 776, 1788, 4147, 9544, 22000, 50420, 115407, 263062, 598540, 1357535, 3072441, 6935695, 15624802, 35121748, 78798610 at degrees 0..22, its subsequence with nonzero constant term reads 1, 1, 3, 6, 16, 34, 83, 187, 445, 1012, 2359, 5397, 12456, 28420, 64987, 147655, 335478, 758995, 1714906, 3863254, 8689107, 19496946, 43676862, the first is the partial sum of the second term for term, and both are absent from the same dump on the same condition
• the maximum coefficient over M* at degree d reads 1, 1, 2, 3, 6, 10, 20, 35, 70, 126, 252, 462, 924, 1716, 3432, 6435, 12870, 24310, 48620, 92378, 184756, 352716, 705432 at d = 0..22, which is binomial(d, floor(d/2)), A001405, term for term, and no coefficient of x^i at any degree passes binomial(d, i), the two facts the packing rests on
• the maximum of P(base) over M* at degree below level is exactly (base+1)^(level-1), attained by (1+x)^(level-1), because a 0/1 polynomial of degree d has P(base) <= 1 + base + ... + base^d <= (1+base)^d and degrees add over a product; so the carry-free window base_set(level) is the least base with (base+1)^(level-1) < base^level for every level, and it reads 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 7, 7 at level 3..14 where the generator enumerates it directly
• the order window base_ord(level) reads 3, 3, 4, 4, 4, 5, 5, 6, 6, 7, 7, 8 at level 3..14 and is strictly larger than base_set at level 12 and level 14, where the first inversion is between two elements of the same degree, (1+x^2)^6 = 2565726409 before x^11 + x^12 = 2539579392 at base 6 and (1+x^2)^7 = 781250000000 before x^13 + x^14 = 775112083256 at base 7
• the carry-free windows are 4, 7, 9, 12 and 15 at bases 3, 4, 5, 6, 7 and M(base^level) departs from -1 at exactly 5, 8 and 10 at the three bases where the departure is reachable, one level past the window at each, while bases 6 and 7 hold -1 to the depth measured
• the first overtaking pair is (1+x)^4 = 256 over 3^5 = 243 at base 3, (1+x)^7 = 78125 over 4^8 = 65536 at base 4 and (1+x)^9 = 10077696 over 5^10 = 9765625 at base 5
• the running maximum is a blunter statistic than M(base^level) and survives past the window: it departs at level 9 at base 3, at level 11 at base 4 and nowhere to level 11 at base 5, so 1, 1, 2, 3, 4, 7, 15, 23, 45, 86 is shared by base 4 and base 5 although base 4 leaves the carry-free window at level 8
• nu* vanishes at every polynomial divisible by x^2 and nu*(x b) = -nu*(b) on the classes of nonzero constant term: the Rust holds only M*_odd, assembles every level from that layer and its single shift, and reproduces the Python full-monoid ladder term for term at every level to 18, which is the check
• on the classes of nonzero constant term, nu* is invariant under the reciprocal b -> x^(deg b) b(1/x), which is degree-preserving, multiplicative and involutive there, so it is a monoid automorphism of R carrying S*_odd onto itself by reversing the bitmask; it is not an invariance on all of Z[x], since the reciprocal drops the x power and nu*(x) = -1 against nu*(1) = 1: the Rust reverses every stored element and looks it up in its own layer, 0 mismatches over the 35121747 elements of M*_odd of degree 1 to 21
• the base-free running maximum stays under the design mass at every level measured: max/2^level bottoms at 0.079102 at level 11, falls for the last time at level 15, and rises at every step from there to 0.241536 at level 23; what runs ahead of the mass is the RATE, and the estimate of that rate is not stable in the window. At depth 23 the geometric mean step reads 2.245836, 2.202419, 2.242075 and 2.206405 over the last 4, 6, 8 and 10 levels but 2.194975, 2.149760, 2.092480, 2.074545 and 1.996559 over the last 12, 14, 16, 18 and 20, a hull of [1.996559, 2.245836] that straddles the mass rate 2. The long windows are the ones that fall, and they average in the levels below level 15 where the ratio was still falling: the 20 level window at depth 23 opens at level 3. At the short windows every reading from depth 20 to depth 23 sits above 2.18 and above its own depth-18 value, 2.220211, 2.215612, 2.207713, 2.245836 at window 4 against 2.158562, 2.187499, 2.264450, 2.203196, 2.202419 at window 6 against 2.186288, and 2.201198, 2.214005, 2.182999, 2.242075 at window 8 against 2.127878, with no monotone trend inside that span. The measured log_2(max)/level climbs 0.697557, 0.733333, 0.764379, 0.775442, 0.804638, 0.830340, 0.841199, 0.856910, 0.873850, 0.890790, 0.895991, 0.910883 at level 12..23 and has not settled
• the step sits under base^(Re rho) = 2.207512 at base 3 {0,1}, which is a bracket and not a comparison of one object with itself: base 3 leaves the base-free ladder at level 9, reading 38 against 45, so past level 8 the two orders differ
• the wall is memory, not time: level 24 needs the degree-22 layer resident as a source, 1.9 GB beyond the 2069 MB the level-23 run accounts for, and every source layer is read as at most four monotone streams over the level's buckets, so streaming the layers is the route past it

PAGES

• mobius THE EXPONENT, TAGGED HONESTLY - the base-free reading of the two-digit column, its M(base^level), its running maxima and the rate of that maximum against the mass rate 2.

SOURCES

• A001405 - binomial(n, floor(n/2)), matched term for term against the local dump through n = 17 as the exact maximum coefficient of a product of 0/1 polynomials of total degree n.
• mrly-pairing - the design Mobius nu_F this study transports, its boxed zero of zeta_F at base 3 {0,1}, and the transport theorem that turns a zero right of alpha into a lower bound on the growth of sum nu_F.