hash_adjacent_step_counterexample
On a fixed occupied set, a unit-first order can create more adjacent pairs on average in the next step than linear probing.
Statement
theorem hash_adjacent_step_counterexample :
(∑ h : ZMod 6, hash_adjacent_count 6 1
(hash_insert_step 6 ![(0 : ZMod 6),1,4,5,2,3] ({0,2,3} : Finset (ZMod 6)) h)) = 15 ∧
(∑ h : ZMod 6, hash_adjacent_count 6 1
(hash_insert_step 6 (linear_probe_offset 6) ({0,2,3} : Finset (ZMod 6)) h)) = 14- Source
- Unit-first fixed-offset mean-probe extremality; experiments 11670–11680 and arXiv:2610.31363.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- hash_adjacent_countThe number of occupied slots whose d-successor is also occupied.
- hash_insert_stepGiven table size n, an offset sequence r : Fin n → ZMod n, a set of occupied slots T : Finset (ZMod n), and an element a : ZMod n,…
- linear_probe_offsetGiven a natural number n, linear_probe_offset n is the function from Fin n to ZMod n that maps each index j : Fin n to its canonical…
The proof, explained
The theorem is proved by exhaustive finite computation. In a hash table of size 6 with occupied slots {0, 2, 3}, inserting a key with initial hash value h yields identical adjacent-pair counts under both probe orders for all h except h = 2. When h = 2, the unit-first probe order fills slot 1 to produce a run of four consecutive elements {0, 1, 2, 3} with three adjacent pairs, whereas linear probing fills slot 4 to produce {0, 2, 3, 4} with only two adjacent pairs, resulting in total sums of 15 versus 14.
The sum of adjacent pair counts across all six possible initial hash values is 15 for the unit-first probe sequence and 14 for linear probing. automation
Because the domain $\mathbb{Z}/6\mathbb{Z}$ and the initial set $\{0, 2, 3\}$ are finite, the statement is a decidable proposition. Evaluating each case $h \in \{0, 1, 2, 3, 4, 5\}$: for $h \neq 2$, both probe orders insert into the same positions. For $h = 2$, linear probing finds slot $2 + 2 = 4$ empty (yielding $\{0, 2, 3, 4\}$, which has 2 adjacent pairs: $\{2,3\}$ and $\{3,4\}$), whereas the unit-first order tests offsets 0, 1, 4 (slots 2, 3, 0, all occupied) and fills slot $2 + 5 = 1$ (yielding $\{0, 1, 2, 3\}$, which has 3 adjacent pairs: $\{0,1\}$, $\{1,2\}$, and $\{2,3\}$). Summing over all $h$ gives 15 for the unit-first sequence and 14 for linear probing, which Lean's kernel computes directly.
(hash_insert_step 6 (linear_probe_offset 6) ({0,2,3} : Finset (ZMod 6)) h)) = 14 := by decide +kernel
- The proof is closed entirely by computation (`decide +kernel`), which evaluates the finite sums, set insertions, and adjacent-pair counts directly in the Lean kernel.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem hash_adjacent_step_counterexample : (∑ h : ZMod 6, hash_adjacent_count 6 1 (hash_insert_step 6 ![(0 : ZMod 6),1,4,5,2,3] ({0,2,3} : Finset (ZMod 6)) h)) = 15 ∧ (∑ h : ZMod 6, hash_adjacent_count 6 1 (hash_insert_step 6 (linear_probe_offset 6) ({0,2,3} : Finset (ZMod 6)) h)) = 14 := by decide +kernel