# ADR 0017: The Neighbor Joining tie rule is this project's, with a relative band Neighbor Joining joins the pair with the smallest Q score. When two pairs tie, something has to choose, and neither [saitou1987] nor the Q formulation in [studier1988] says what. This records what `damicore_tree_builder` does, because the choice changes the tree a run reports from the same matrix, so recording "Saitou and Nei 1987" alone does not identify that tree. Both works were read against this code on 2026-11-07, which settles two things this record had been asserting without them. The Q reformulation credited to [studier1988] here is its formula (1), `Sij = (N - 2)Dij - Ri - Rj` with `Ri` the row sum, which is what the module computes. And the gap is real in both: [saitou1987] selects on the smallest `Sij` and [studier1988] step B says "Pick a pair i, j for which Sij is the smallest" — singular, with nothing said about which pair when two are equally small. ## Ties are not an edge case here With four clusters left, `Q(i,j)` and `Q(k,l)` for complementary pairs are algebraically equal for *every* matrix. A tie is therefore reached on the way to the end of essentially every run, not occasionally. Exact float64 comparison does not see it. Measured, it detects that equality about 60% of the time, and no summation strategy fixes it: the cancellation happens in the final subtraction rather than in the sums. An exact comparison also asserts a precision the input never had — every distance here is a ratio of integer compressed sizes, so its meaningful digits run out long before the sixteenth. ## The rule Two scores within a relative band are one tie. The band is `1e-9 * max(1.0, abs(best_score))`, so it scales with the magnitude of the better score rather than being absolute. Among pairs in a tie, the one reached first wins: a later pair replaces the best only when it is better by more than the band, and a better score inside the band tightens the band's centre without changing the pair. What "first" means is the part worth recording, because it is not the input. The active set is sorted at the start of every round, so pairs are visited in **lexicographic label order**: the running pair is always the lexicographically earliest one seen so far. Relabelling can therefore change which pair wins a tie; reordering the rows of the same matrix cannot. Internal nodes are named `nj_%06d`, zero-padded so that their lexicographic order is also the order they were created in. The tree is a function of the matrix and its labels and of nothing else, which `damicore_tree_builder`'s `test_an_exact_q_tie_is_broken_by_the_smallest_id_pair` holds by running the same tie through three permutations of the input and requiring the same join. The band and this ordering are both this project's. The opening of this record says [saitou1987] states no tie rule, and nothing here walks that back: what is claimed is that resolving a tie by a fixed, label-derived order is a choice the method leaves open, not a departure from it. Reading both works confirmed the opening rather than changing it; what it did change is one sentence in `neighbor_joining`, where the reduction had been described as the published average. It is [studier1988]'s formula (3), which that paper flags as deliberately not [saitou1987]'s average. ## What the band buys, and what it costs It buys determinism across platforms. Without it the tree depends on whether a particular float64 subtraction happened to cancel exactly on the machine that ran it, which makes a result irreproducible for a reason that has nothing to do with the data. It costs a threshold with a magnitude, and a threshold is a decision: two genuinely distinct pairs closer than one part in a billion are treated as tied. Against distances that are ratios of integer compressed sizes, that is far below the resolution of the input. ## Status The band and the index-order preference are this project's and are versioned by this record. A change to either is a new record, because it changes which tree a run reports. `validate_matrix` rests on the same decision: it is the gate that makes the rule meaningful, by refusing a matrix whose shape, dtype or labels would let the pair loop run on input the rule was never defined over.