A certified upper bound for the beat the average game
Version 1 / Nov 15, 2026 / CC BY 4.0
Abstract
Let be the supremum of over all probability measures on , where are independent with the given law. Determining is Problem 6.39, the beat the average game, in the list of Georgiev, Gómez-Serrano, Tao and Wagner. Bellec and Fritz proved and conjectured that the lower bound, , is the exact value. We prove , less than above the conjectured value. The proof applies Razborov's flag algebra method to samples of nine points. Since the points are independent, the positivity constraints of flag algebras hold for every single measure, so that no limit objects are needed. An exact certificate is checked in rational arithmetic, and the bound is also proved in the Lean 4 proof assistant, with Lean's kernel checking the certificate.
References
- J. Balogh, P. Hu, B. Lidický, O. Pikhurko, B. Udvari and J. Volec, Minimum number of monotone subsequences of length 4 in permutations , Combin. Probab. Comput. 24 (2015), 658--679.
- P. C. Bellec and T. Fritz, On maximizing the probability of a linear inequality between iid random variables , Amer. Math. Monthly (2026), doi:10.1080/00029890.2026.2702871; arXiv:2412.15179v5 (listed on arXiv as Optimizing over iid distributions and the Beat the Average game ), whose numbering we cite.arXivDOI
- B. Borchers, CSDP, a C library for semidefinite programming , Optim. Methods Softw. 11 (1999), 613--623.
- T. Fritz, How large can get? , MathOverflow question 474916, 2024, https://mathoverflow.net/q/474916.link
- B. Georgiev, J. Gómez-Serrano, T. Tao and A. Z. Wagner, Mathematical exploration and discovery at scale , arXiv:2511.02864, 2025.arXiv
- P. Gordan, Ueber die Auflösung linearer Gleichungen mit reellen Coefficienten , Math. Ann. 6 (1873), 23--28.
- Q. Huangfu and J. A. J. Hall, Parallelizing the dual revised simplex method , Math. Program. Comput. 10 (2018), 119--142.
- The mathlib Community, The Lean mathematical library , in: Proc. 9th ACM SIGPLAN Int. Conf. Certified Programs and Proofs (CPP 2020), 2020, 367--381.
- L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language , in: Automated Deduction -- CADE 28, Lecture Notes in Comput. Sci. 12699 , Springer, 2021, 625--635.
- A. Novikov et al., AlphaEvolve: A coding agent for scientific and algorithmic discovery , arXiv:2506.13131, 2025.arXiv
Show all 13 referencesShow fewer references
- A. A. Razborov, Flag algebras , J. Symbolic Logic 72 (2007), 1239--1282.
- J. Sliačan and W. Stromquist, Improving bounds on packing densities of 4-point permutations , Discrete Math. Theor. Comput. Sci. 19 (2018), no. 2, paper 3.
- V. Yu, answer to Fri24 , MathOverflow, 2024, https://mathoverflow.net/a/484853.link
Version history
- v1 · 12 pagesSubmitted by Tejasvi Singh TomarPublished on Zenodo: https://doi.org/10.5281/zenodo.23715999CurrentNov 15, 2026