# Equal Density, Different Block Budgets

Two synthetic 30-bit strings both contain 15 ones. Split them into two
15-bit blocks and count only a fixed-width class and a pattern index:

| Input layout | Ones per block | Class bits | Pattern bits | Total field bits |
| --- | --- | --- | --- | --- |
| 15 zeroes, then 15 ones | 0, 15 | 8 | 0 | 8 |
| Alternating 0 and 1 | 7, 8 | 8 | 26 | 34 |

These are exact constructed field counts, not measurements of an RRR library.
Global density alone does not determine local class sizes. Neither figure
includes query samples, pointers, lookup tables, headers or padding.

## Method

For a block of b bits containing k ones, count choose(b,k) patterns.
Use ceil(log2(b+1)) bits for its class and ceil(log2(choose(b,k))) for its
pattern. Sum the rounded widths over complete blocks. The reference uses
BigInt for the binomial coefficients. Input is limited to 4096 binary digits
and block lengths 1 through 256; incomplete final blocks are rejected.

The construction follows the class/offset layout described in
[Donges and Puglisi, SEA 2025, section 2.1](https://drops.dagstuhl.de/storage/00lipics/lipics-vol338-sea2025/html/LIPIcs.SEA.2025.15/LIPIcs.SEA.2025.15.html).
The examples and calculations are Hesela's, not a reproduction of that
paper's performance experiments.

A short variable-length code for one clustered input does not contradict
the worst-case distinguishing bound over all strings with the same weight.
The alternating case can expand even before query-support overhead is added.

## Reproduce

From sites/hesela-dev in the source repository:

```sh
node public/research/rrr-layout/generate.mjs --check
node --test public/research/rrr-block-budget.test.mjs
```

The generator, input strings and generated results are public. Files:
[generator](generate.mjs), [observations](observations.json),
[field calculator](../rrr-block-budget.mjs), [tests](../rrr-block-budget.test.mjs).
Keep those relative paths together to run an offline copy. No dependencies
are needed beyond a Node.js version supporting ES modules and node:test.

Generated numbers are checked against independent exhaustive enumeration,
including all 65,534 bitvectors of lengths 1 through 15 for single-block counts
and all 1,364 two-block strings with block lengths 1 through 5.

License: CC0-1.0 for Hesela's code, text and constructed inputs.
Published: 2026-11-17. No external paper text, figures or code redistributed.
