THE FOLD / SPAWN / HELLO WORLD / THE TWO HEURISTICS
THE TWO HEURISTICS
rank prevents, compression repairs
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Union-Find carries two famous heuristics, and the celebrated inverse-Ackermann bound belongs to the pair. Measured separately they turn out to do entirely different jobs at entirely different times: union-by-rank prevents a deep tree from ever forming; path compression lets it form and then flattens it — but only where you looked.
LIT verified live on 2,000 elements unioned in chain-forming order. With neither heuristic the depth is 1,999. Rank alone builds it at depth 1. Compression alone builds the same 1,999-deep chain and a full query pass collapses it to 1. Both together cost 2.00 probes per operation against 999.50 for neither.
LIT verified live on 2,000 elements unioned in chain-forming order. With neither heuristic the depth is 1,999. Rank alone builds it at depth 1. Compression alone builds the same 1,999-deep chain and a full query pass collapses it to 1. Both together cost 2.00 probes per operation against 999.50 for neither.
2 HOW IT WAS WEAVED · AI + HUMAN
The structure is Galler and Fischer’s, with union-by-rank and path compression added later; the near-constant bound is Tarjan’s 1975 analysis. This corpus already carries the structure itself — this sphere is the split, which the general treatment does not measure.
AVAN (AI) got this wrong first and the correction is the finding. The initial harness measured tree depth immediately after construction and reported that compression alone did nothing — a failing gate. Depth was being read before any query had run, and path compression is lazy: it repairs only the paths someone actually walks. Measuring both moments turns a flat “both are needed” into the sharper statement that one acts at write time and the other at read time.
AVAN (AI) got this wrong first and the correction is the finding. The initial harness measured tree depth immediately after construction and reported that compression alone did nothing — a failing gate. Depth was being read before any query had run, and path compression is lazy: it repairs only the paths someone actually walks. Measuring both moments turns a flat “both are needed” into the sharper statement that one acts at write time and the other at read time.
3 ONE DIMENSION
Four variants, two moments each.
4 TWO DIMENSIONS · INTERACTIVE
Build a chain, then query it, one heuristic at a time.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a chain, and the same chain flattened.
AVAN’s addition (the inverse-companion): the forward reading is “compression repairs the tree.” The inverse is that it repairs only what is asked for, and leaves the rest exactly as bad. A structure under compression alone carries its full worst-case depth on every path nobody has queried yet, so the good amortised number is a statement about a workload rather than about the structure. Read backwards, rank buys you a guarantee you can reason about without knowing the queries, and compression buys you a number that is only true in hindsight.
LIT over 2,000 elements unioned in chain-forming order, neither heuristic gives depth 1,999; rank alone builds it at depth 1; compression alone builds the SAME 1,999-deep chain and a full query pass collapses it to 1; and both together cost 2.00 probes per operation against 999.50 for neither
FIG The structure is Galler and Fischer's, with union-by-rank and path compression added later; the near-constant bound is Tarjan's 1975 analysis. This corpus already carries the structure itself - this sphere is the SPLIT, which the general treatment does not measure. AVAN got this wrong first and the correction is the finding: the initial harness measured depth immediately after construction and reported that compression alone did nothing, a failing gate. Depth was being read BEFORE ANY QUERY HAD RUN, and path compression is lazy - it repairs only the paths someone actually walks. Measuring both moments turns a flat 'both are needed' into the sharper statement that one acts at write time and the other at read time.
FIG The structure is Galler and Fischer's, with union-by-rank and path compression added later; the near-constant bound is Tarjan's 1975 analysis. This corpus already carries the structure itself - this sphere is the SPLIT, which the general treatment does not measure. AVAN got this wrong first and the correction is the finding: the initial harness measured depth immediately after construction and reported that compression alone did nothing, a failing gate. Depth was being read BEFORE ANY QUERY HAD RUN, and path compression is lazy - it repairs only the paths someone actually walks. Measuring both moments turns a flat 'both are needed' into the sharper statement that one acts at write time and the other at read time.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of HELLO WORLD · David Lee Wise (ROOT0), with AVAN