HEXAGONbeta

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

A mix of human-written and AI-generated textHuman understanding: all partscs.DS — Data Structures and Algorithmsmath.CO — Combinatoricscs.CC — Computational Complexity

Contributed by Tejasvi Singh Tomar ↗

Version 1 / Nov 12, 2026 / CC BY 4.0

Abstract

We study (t,n)(t,n)-selection networks, which move the tt largest of nn inputs to tt given lines in any order, and the least number U^t(n)\hat U_t(n) of comparators in such a network. Alekseev showed that U^t(n)≥(n−t)⌈lg⁡(t+1)⌉\hat U_t(n)\ge(n-t)\lceil\lg(t+1)\rceil. For t=2k≥4t=2^k\ge 4 we raise this bound by k−1k-1 for every n>tn>t, and by 2k−52k-5 when t≥32t\ge 32; as far as we know, these are the first improvements at powers of two. The proofs follow the weights of the lines, and a pruning step of Yao extends the gain to every t≥3t\ge 3. For t=3t=3, Yao's upper bound 2n−5+⌊lg⁡(n−3)⌋2n-5+\lfloor\lg(n-3)\rfloor is exact for 4≤n≤184\le n\le 18. For t=4t=4 the new bound is 3n−113n-11 for all n≥5n\ge 5, and the value 3n−103n-10 that Knuth expected is exact for 6≤n≤126\le n\le 12. Their lower bounds rest on exhaustive searches at a few sizes and on the fact that one more input costs at least two more comparators. Most of the results are also proved in Lean 4, some through compiled checks.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23801189

References

  1. Alekseev, V. E. Sorting algorithms with minimum memory. Kibernetika, vol. 5, no. 5, pp. 99–103. 1969. English translation: Cybernetics 5 (1969), 642–648DOI
  2. Asín, Roberto; Nieuwenhuis, Robert; Oliveras, Albert; Rodríguez-Carbonell, Enric. Cardinality networks: a theoretical and empirical study. Constraints, vol. 16, no. 2. 2011DOI
  3. Codish, Michael; Zazon-Ivry, Moshe. Pairwise cardinality networks. Logic for Programming, Artificial Intelligence, and Reasoning (LPAR-16), vol. 6355, pp. 154–172. 2010DOI
  4. de Moura, Leonardo; Ullrich, Sebastian. The Lean 4 theorem prover and programming language. Automated Deduction – CADE 28, vol. 12699, pp. 625–635. 2021DOI
  5. Jimbo, Shuji; Maruoka, Akira. A method of constructing selection networks with O(log⁡n)O(\log n) depth. SIAM J. Comput., vol. 25, no. 4. 1996DOI
  6. Karpiński, Michał; Piotrów, Marek. Smaller selection networks for cardinality constraints encoding. Principles and Practice of Constraint Programming (CP 2015). 2015. arXiv:1502.04551arXivDOI
  7. Knuth, Donald E. Errata for The Art of Computer Programming, Vol. 3, second edition. Entries of 12 September 2003: replacement of exercise 5.3.4–20 and its answer. https://www-cs-faculty.stanford.edu/~knuth/taocp.htmllink
  8. Knuth, Donald E. The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley. 1998
  9. Pippenger, Nicholas. Selection networks. SIAM J. Comput., vol. 20, no. 5, pp. 878–887. 1991DOI
  10. Qu, Yicheng; Tasbihi, Amir; Kschischang, Frank R. Constituent automorphism decoding of Reed–Muller codes. IEEE Trans. Commun. 2025. arXiv:2409.03700arXivDOI
Show all 16 referencesShow fewer references
  1. Tomar, Tejasvi Singh. Lead-pattern potentials and exact values of merging networks. 2026. Zenodo, version 5, doi:10.5281/zenodo.23756850 (https://doi.org/10.5281/zenodo.23756850)link
  2. Tomar, Tejasvi Singh. Lean development for ``Exact sizes of networks that select the three or four largest of nn elements''. 2026. Zenodo, doi:\leandoi (https://doi.org/\leandoi)link
  3. Tomar, Tejasvi Singh. Supplement to ``Exact sizes of networks that select the three or four largest of nn elements''. 2026. Checksum file \textttSHA256SUMS with SHA-256 hash \texttt\suppsums\dots. Zenodo, doi:\suppdoi (https://doi.org/\suppdoi)link
  4. Yao, Andrew C. Bounds on selection networks. 15th Annual Symposium on Switching and Automata Theory, pp. 110–116. 1974DOI
  5. Yao, Andrew C. Bounds on selection networks. SIAM J. Comput., vol. 9, no. 3, pp. 566–582. 1980DOI
  6. Yao, Andrew Chi-Chih. A Study of Concrete Computational Complexity. 1975. Report UIUCDCS-R-75-716

Version history

  1. v1 · 17 pagesSubmitted by Tejasvi Singh TomarPublished on Zenodo: https://doi.org/10.5281/zenodo.23801189CurrentNov 12, 2026