sumset-density

• Computes the sumset S = A + B of the base-3 design A = {0, 1} and the base-4 design B = {0, 1}, the object of Erdos problem 125, exactly as a bit array up to 3^K, and reads its density D(x) = card(S meet [1, x])/x.
• The bit array holds one bit per integer in [0, 3^K]; the members of A are set directly, and each power 4^j <= 3^K is folded in by one shift-or pass, S |= S << 4^j, so floor(K log_4 3) + 1 passes over the array build the whole sumset, 14 at K = 17 and 18 at K = 22. The other order, B direct and the powers of 3 shifted, is the control.
• The scan reads card(S meet [1, x]) at x = 3^k, 4^m, floor(3^k/2), floor(4^m/3) and at the centres d = (3^k - 1)/2 + (4^m - 1)/3, and the maximum and minimum of D(x) over each window [3^k, 3^(k+1)), each window [2^j, 2^(j+1)) and over all of [1, 3^K], each with its location. Maxima and minima are compared exactly by cross multiplication; a density prints truncated to six places; an exponent log(card)/log(x) prints truncated.
• The energy verb computes the additive energy E(k, m) = card{(a, b, a', b') in A_k^2 x B_m^2 : a + b = a' + b'} exactly, as sum over t of 2^(z_3(t) + z_4(t)) with t ranging over the 3^m integers with base-4 digits in {-1, 0, 1}, z_4(t) the number of zero digits there and z_3(t) the number of zero digits in the balanced ternary expansion of t on k digits, or nothing when abs(t) > (3^k - 1)/2; a test checks it against the histogram of the representation function at three pairs. It prints, per pair (k, m) with 4^m within a factor 3 of 3^k, the fill card(S meet [0, d])/(d + 1), the energy, the flat energy 4^(k+m)/(d + 1), their ratio Q rounded up, and the Cauchy-Schwarz bound 1/Q truncated down.

VERBS

• density K builds S to 3^K and prints the readings above. Runtime 0.09 s at K = 17, 1.3 s at K = 20, 13 s at K = 22 on a 4 GB bit array; K = 23 wants 12 GB.
• energy K builds S to 3^K and prints the energy table for every pair with d <= 3^K. Runtime 0.3 s at K = 17, 39 s at K = 22.
• control compares the shift-or array against a double loop over A x B at 3^13, the two shift orders against each other at 3^17, the first 58 non-members against the terms of A367090, and tests the reflection x -> d - x on S meet [0, d] at every centre below 3^17. Runtime 0.08 s.

RUN

CARGO_BUILD_JOBS=4 cargo run --release -p sumset-density -- density 17
CARGO_BUILD_JOBS=4 cargo run --release -p sumset-density -- density 22
CARGO_BUILD_JOBS=4 cargo run --release -p sumset-density -- energy 22
CARGO_BUILD_JOBS=4 cargo run --release -p sumset-density -- control

• CARGO_BUILD_JOBS=4 cargo test --release -p sumset-density, 8 tests, under 0.1 s after the build.

READS

• card(S meet [1, 3^22]) = 26666749554, D(3^22) = 0.849772.
• D(3^k) at k = 4..22: 0.975308, 0.835390, 0.858710, 0.887517, 0.908855, 0.864959, 0.778472, 0.837186, 0.858264, 0.874244, 0.814704, 0.763392, 0.831183, 0.858962, 0.881342, 0.792352, 0.767893, 0.831191, 0.849772.
• D(4^m) at m = 3..17: 0.968750, 0.843750, 0.860351, 0.897460, 0.859313, 0.791305, 0.837238, 0.868845, 0.806823, 0.783585, 0.838184, 0.875988, 0.785523, 0.793552, 0.845272.
• Maximum of D over [3^k, 3^(k+1)) at k = 5..21: 0.913419, 0.903768, 0.912038, 0.931596, 0.913781, 0.875566, 0.875469, 0.881621, 0.908274, 0.885045, 0.865671, 0.882855, 0.886340, 0.910650, 0.874408, 0.865858, 0.872186; minimum: 0.835390, 0.852729, 0.887517, 0.858945, 0.778468, 0.778472, 0.822506, 0.858264, 0.806430, 0.763391, 0.763392, 0.815887, 0.858962, 0.785230, 0.767893, 0.767875, 0.818358.
• Minimum of D over [1, 3^22]: 0.763391 at x = 3^15 - 1; the maximum is 1 at x <= 61.
• The reflection x -> d - x fixes S meet [0, d] at every clean centre and at no mixed centre with d >= 449.
• Q(k, m) over the 27 pairs with 6 <= k <= 22 lies in [1.467705, 2.060586], the maximum at (16, 12); the Cauchy-Schwarz bound 1/Q is at least 0.485298 on every one of them, against fills between 0.834213 and 0.928391. Fitted as 3^(eta k) on two endpoints, Q grows at eta = 0.015852 from k = 6 to k = 22 and at eta = 0.001987 from k = 11 to k = 22, both rounded up.

WITNESSES

• cobham.md section "Object S: the base-3 design plus the base-4 design", every number there.