Optimal Shift Encoding for Binary Tries

Preliminary draft / work in progress — September 2026. This version contains the complete mathematical and algorithmic development of the main optimal-shift algorithm. The full development of the Optimal-versus-Average result and the reference implementation are still in preparation and are intentionally not presented as complete here. Let A be a set of n distinct K-bit integers and let U=2^K. We seek a circular additive shift minimizing the number of nodes in the binary trie of A. For 0<=r<=K, let f_r(s) be the number of trie nodes at depth K-r after shift s. Their sum is the total number of nodes in the trie. We establish a recurrence for the functions x -> min_{y ≡ x (mod 2^r)} ∑_{r<=i<=K} f_i(y). Each of these functions is periodic and has O(n) transitions in one period. The recurrence solves the optimization problem and leads to an explicit O(nK)=O(n log U)-time algorithm using O(n) auxiliary space. This matches the O(N log u) running time stated by Alanko et al. for their more general setting, where the construction attaining that bound was omitted. We also show that the additive bound 2(n-1) between average and optimal shifted trie costs from Gupta et al. is asymptotically sharp even for families with K << n << U.