# 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](../mrly-pairing/README.md) 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](../../../notes/mobius.md) 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](../../../notes/mobius.md) 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](https://oeis.org/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](../mrly-pairing/README.md) - 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`.