techno-optimist/erdos-minimum-overlap-bound — explained in plain English
Analysis updated 2026-05-18
Verify a new proven upper bound for the Erdos minimum overlap constant using exact rational arithmetic.
Study how a computer-assisted proof turns a numerical construction into a machine-checkable certificate.
Reference the current best proven bounds and their attribution when researching this specific open problem.
| techno-optimist/erdos-minimum-overlap-bound | 0xallam/my-recipe | 0xhassaan/nn-from-scratch | |
|---|---|---|---|
| Stars | 0 | — | 0 |
| Language | Python | Python | Python |
| Last pushed | — | 2022-11-22 | — |
| Maintenance | — | Dormant | — |
| Setup difficulty | easy | moderate | moderate |
| Complexity | 3/5 | 2/5 | 4/5 |
| Audience | researcher | general | developer |
Figures from each repo's GitHub metadata at analysis time.
Only Python 3.10 or newer and the standard library are needed to run the verification commands.
This repository is a math research note, not a piece of software you install and run day to day. It works on an old, unsolved question in number theory called the Erdos minimum overlap problem, which asks how small a certain kind of overlap between two sets of numbers can be made. Researchers narrow this down over time by proving upper and lower limits on the true answer, and this project claims a new, slightly tighter upper limit than the previous best published one from 2016. The way it works is by taking specific numerical constructions produced by other researchers and AI search systems competing on a public leaderboard, and then proving, using exact fraction arithmetic rather than approximate decimal numbers, that those constructions truly satisfy the mathematical rules required to count as valid. The authors are explicit that they did not invent the underlying constructions themselves. Their contribution is the proof method that takes someone else's numerical result and turns it into a fully verified, exact mathematical certificate, plus a small repair to one borderline construction that technically passed the leaderboard's own rules only due to a rounding quirk in floating point numbers. To check the claims yourself, you need Python 3.10 or newer, and everything runs using only Python's built-in standard library, no extra packages required. Running a make verify command checks the proofs and prints out whether each certificate holds. The project takes care to spell out exactly what it does and does not prove, including that the lower limit on the answer comes entirely from a different published paper and is simply quoted, not something this project improved. This is aimed at people already working in combinatorics or computer-assisted mathematical proof, not general programmers, and there is no ordinary application or user interface here, only a note, supporting code, and machine-checkable certificate files.
A computer-verified math research note proving a slightly tighter upper limit on the long-studied Erdos minimum overlap constant.
Mainly Python. The stack also includes Python.
Setup difficulty is rated easy, with roughly 5min to a first successful run.
Mainly researcher.
This repo across BitVibe Labs
double-check against the repo, no cap.