A certified upper bound for the beat the average game

A mix of human-written and AI-generated textHuman understanding: all partsmath.PR — Probabilitymath.OC — Optimization and Controlmath.CO — Combinatorics

Contributed by Tejasvi Singh Tomar ↗

Version 1 / Nov 15, 2026 / CC BY 4.0

Abstract

Let CC be the supremum of P[X1+X2+X3<2X4]\mathbb{P}[X_1+X_2+X_3<2X_4] over all probability measures on [0,∞)[0,\infty), where X1,…,X4X_1,\dots,X_4 are independent with the given law. Determining CC is Problem 6.39, the beat the average game, in the list of Georgiev, Gómez-Serrano, Tao and Wagner. Bellec and Fritz proved 0.4006953≤C≤673/16150.4006953\le C\le 673/1615 and conjectured that the lower bound, 0.4006953723…0.4006953723\ldots, is the exact value. We prove C≤0.40069634C\le0.40069634, less than 10−610^{-6} 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.

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

References

  1. 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.
  2. 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
  3. B. Borchers, CSDP, a C library for semidefinite programming , Optim. Methods Softw. 11 (1999), 613--623.
  4. T. Fritz, How large can P[X1+X2+X3<2X4]\mathbf{P}[X_1+X_2+X_3<2X_4] get? , MathOverflow question 474916, 2024, https://mathoverflow.net/q/474916.link
  5. B. Georgiev, J. Gómez-Serrano, T. Tao and A. Z. Wagner, Mathematical exploration and discovery at scale , arXiv:2511.02864, 2025.arXiv
  6. P. Gordan, Ueber die Auflösung linearer Gleichungen mit reellen Coefficienten , Math. Ann. 6 (1873), 23--28.
  7. Q. Huangfu and J. A. J. Hall, Parallelizing the dual revised simplex method , Math. Program. Comput. 10 (2018), 119--142.
  8. The mathlib Community, The Lean mathematical library , in: Proc. 9th ACM SIGPLAN Int. Conf. Certified Programs and Proofs (CPP 2020), 2020, 367--381.
  9. 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.
  10. A. Novikov et al., AlphaEvolve: A coding agent for scientific and algorithmic discovery , arXiv:2506.13131, 2025.arXiv
Show all 13 referencesShow fewer references
  1. A. A. Razborov, Flag algebras , J. Symbolic Logic 72 (2007), 1239--1282.
  2. 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.
  3. V. Yu, answer to Fri24 , MathOverflow, 2024, https://mathoverflow.net/a/484853.link

Version history

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