TejasviTomar
October 2026 · Preprint

Exact sizes of networks that select the three or four largest of n elements

Tejasvi Singh Tomar

In plain words

A selection network uses comparisons fixed in advance to move a chosen number of the largest values in a list into designated positions, though not necessarily in order of size. Logic solvers use selection networks to impose limits like “at most three of these are true”. In 1975 Yao asked how few comparisons such a network needs to pick out the three largest. The paper answers this for lists of 4 to 18 numbers. For picking out the four largest from lists of 7 to 12 numbers, it confirms the comparison counts that Knuth expected. It also raises Alekseev’s 1969 lower bound on how many comparisons are needed when the number of values picked out is 4, 8, 16 or any larger power of two.

Abstract

Let Ût(n) be the least number of comparators in a (t, n)-selection network, which moves the t largest of n inputs to t given lines in any order. Alekseev proved Ût(n) ≥ (n − t)⌈lg(t + 1)⌉. For t = 2k ≥ 4 we raise this bound by k − 1 for every n > t, and by 2k − 5 when t ≥ 32; as far as we know, these are the first improvements at powers of two. For t = 4 this gives Û4(n) ≥ 3n − 11 for all n ≥ 5. The proofs follow the weights of the lines, and a finer count over all levels gives a larger gain for t = 2k with 9 ≤ k ≤ 20, by computation. With a pruning step of Yao the bounds give Ût(n) ≥ (n − t)⌈lg(t + 1)⌉ + t − 2k + k − 1 + δk for every t ≥ 2, where k = ⌊lg t⌋ and δk = max(0, k − 4), and a sharper explicit bound that is Yao's lower bound for t = 3. For t = 4, 8, 16, 32 and 64 and large n, explicit sequences show that no argument on the weights alone gives a larger gain. In 1975 Yao proved 2n − 6 + ⌈lg⌈n/3⌉⌉ ≤ Û3(n) ≤ 2n − 5 + ⌊lg(n − 3)⌋ and asked for the exact value. We prove that his upper bound is exact for 4 ≤ n ≤ 18, so that Û3(n) = 2n − 2 for 11 ≤ n ≤ 18, and that Û3(n) ≥ 2n − 2 for all n ≥ 11, which improves his lower bound for 11 ≤ n ≤ 24. We also prove Û4(n) = 3n − 10 for 6 ≤ n ≤ 12. Knuth posed Û4(n) ≤ 3n − 10 as an exercise, credited its solution to a construction of M. W. Green, and expected equality; for n = 8 the result also settles a conjecture of Qu, Tasbihi and Kschischang. These exact values come from exhaustive searches by two separately written programs at a few sizes, and from the inequality Ût(n) ≥ Ût(n − 1) + 2 for t ≥ 2 and n ≥ t + 1. With it, Yao's question reduces to the sizes n = 2j + 3, where his upper bound grows by three, and the paper gives an exact criterion for each of them in terms of the optimal networks on 2j + 2 inputs. Lead-pattern potentials on the inputs of weights 2 and 3 give Û3(n) exactly for n ≤ 6, but for n = 7 only a bound of at most 10, which is less than Û3(7). The gains k − 1 and 2k − 5 at powers of two, the bound with δk for every t, the inequality, the two results on Û3 and the values of Û4(n) for 6 ≤ n ≤ 10 are also proved in Lean 4, those on Û3 and Û4 partly through compiled checks.

Twelve horizontal wires crossed by 26 vertical comparator bars with round ends. Thick magenta, blue, yellow and green paths start on the first, fifth, ninth and tenth wires from the top, labelled 12, 11, 10 and 9 among the input numbers on the left, and end on the bottom four wires, labelled 11, 9, 10 and 12 among the output numbers on the right. The comparators on the paths are black and the others grey.
Illustration of a network from the paper’s supplement: its 26 comparators move the four largest of 12 values onto the bottom four wires, though not necessarily in sorted order. Each vertical bar compares the values on two wires and puts the larger on the lower wire. The numbers listed on the left are one example input, and the coloured paths trace its four largest values, 9 to 12, to the outputs on the right. The comparators these paths pass through are drawn in black. The paper uses an exhaustive computer search to prove that no such network has fewer than 26 comparators.