THE FOLD / CHEAT / GOD MODE / THE BLOOM
THE BLOOM
a filter that only lies one way
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A Bloom filter is a bit array and a handful of hash functions. To add an item, set the bits it hashes to; to test one, check whether they are all set. It cannot store what it holds and cannot remove anything, and it will sometimes say yes to something it never saw. What it will never do is say no to something it did — and that one-sided guarantee is structural, surviving any choice of size or hash count. Burton Bloom published it in 1970 to fit a hyphenation dictionary into memory that could not hold it.
LIT verified live across five configurations: 0 false negatives in every one. The false-positive rate matches (1 − e−kn/m)k closely — measured 0.02805 against a predicted 0.02883, 0.01890 against 0.01960, 0.13628 against 0.14001, 0.000375 against 0.000382. Sweeping the number of hash functions at m = 8192, n = 1000 finds the minimum at k = 6, exactly the predicted (m/n) ln 2 = 6, and going to k = 12 makes it worse — 0.042625 against 0.018900.
LIT verified live across five configurations: 0 false negatives in every one. The false-positive rate matches (1 − e−kn/m)k closely — measured 0.02805 against a predicted 0.02883, 0.01890 against 0.01960, 0.13628 against 0.14001, 0.000375 against 0.000382. Sweeping the number of hash functions at m = 8192, n = 1000 finds the minimum at k = 6, exactly the predicted (m/n) ln 2 = 6, and going to k = 12 makes it worse — 0.042625 against 0.018900.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at GOD MODE: it can claim membership it does not have, and never denies membership it does.
AVAN (AI) included the k-sweep because “more hash functions is safer” is the natural assumption and it is false. Each additional hash sets more bits, so past the optimum the array saturates and the false-positive rate climbs again — at k = 12 it is worse than at k = 3. The optimum sits at (m/n) ln 2, where the array is exactly half full, and the measurement lands on it. The one-sided property deserves precision: it holds because bits are only ever set, never cleared, so any bit an inserted item needs is still set no matter what arrived afterwards. That is why the guarantee survives every parameter choice while the accuracy does not — the same shape as a count-min sketch, arrived at from a different direction.
AVAN (AI) included the k-sweep because “more hash functions is safer” is the natural assumption and it is false. Each additional hash sets more bits, so past the optimum the array saturates and the false-positive rate climbs again — at k = 12 it is worse than at k = 3. The optimum sits at (m/n) ln 2, where the array is exactly half full, and the measurement lands on it. The one-sided property deserves precision: it holds because bits are only ever set, never cleared, so any bit an inserted item needs is still set no matter what arrived afterwards. That is why the guarantee survives every parameter choice while the accuracy does not — the same shape as a count-min sketch, arrived at from a different direction.
3 ONE DIMENSION
False positives against hash count. There is a bottom, and past it more is worse.
4 TWO DIMENSIONS · INTERACTIVE
Fill the array and watch the bits. The misses never happen; the phantom hits do.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: items casting their bits into a shared array.
AVAN’s addition (the inverse-companion): the forward reading is “a Bloom filter trades accuracy for space.” The inverse is that it does not store a set at all — it stores a proof obligation. The array cannot answer “what is in here” and was never asked to; it can only ever fail to rule something out. Read backwards, the structure is a formalised version of not having looked: a “yes” means nothing here contradicts membership, which is a much weaker sentence than it sounds, and the whole engineering value comes from a “no” being the only answer that carries information.
LIT across five configurations there are 0 false negatives in every one; the false-positive rate matches (1 - e^(-kn/m))^k closely, measured 0.02805 against a predicted 0.02883, 0.01890 against 0.01960, 0.13628 against 0.14001, 0.000375 against 0.000382; and sweeping the hash count at m = 8192, n = 1000 finds the minimum at k = 6, exactly the predicted (m/n) ln 2 = 6, with k = 12 making it WORSE - 0.042625 against 0.018900
FIG The k-sweep is included because 'more hash functions is safer' is the natural assumption and it is FALSE. Each additional hash sets more bits, so past the optimum the array saturates and the false-positive rate climbs again - at k = 12 it is worse than at k = 3. The optimum sits at (m/n) ln 2, where the array is exactly half full, and the measurement lands on it. The one-sided property deserves precision: it holds because bits are only ever SET, never cleared, so any bit an inserted item needs is still set whatever arrived afterwards. That is why the guarantee survives every parameter choice while the accuracy does not. Burton Bloom, 1970.
FIG The k-sweep is included because 'more hash functions is safer' is the natural assumption and it is FALSE. Each additional hash sets more bits, so past the optimum the array saturates and the false-positive rate climbs again - at k = 12 it is worse than at k = 3. The optimum sits at (m/n) ln 2, where the array is exactly half full, and the measurement lands on it. The one-sided property deserves precision: it holds because bits are only ever SET, never cleared, so any bit an inserted item needs is still set whatever arrived afterwards. That is why the guarantee survives every parameter choice while the accuracy does not. Burton Bloom, 1970.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of GOD MODE · David Lee Wise (ROOT0), with AVAN