gitwtfhub

wtf is erdos-minimum-overlap-bound?

techno-optimist/erdos-minimum-overlap-bound — explained in plain English

Analysis updated 2026-05-18

0PythonAudience · researcherComplexity · 3/5Setup · easy

TL;DR

A computer-verified math research note proving a slightly tighter upper limit on the long-studied Erdos minimum overlap constant.

Mindmap

mindmap
  root((Erdos overlap bound))
    What it does
      Proves tighter upper bound
      Exact rational certification
      Verifies AI-found constructions
    Tech stack
      Python standard library
    Use cases
      Bound verification
      Proof methodology study
      Research reference
    Audience
      Mathematicians
      Researchers
    Setup
      Python 3.10+
      make verify
      No external packages

Code map

Detail Auto

An interactive map of this repo's files and how they connect — its source is parsed live in your browser. Click Visualize to build it.

filefunction / class

Why would anyone build with this?

REASON 1

Verify a new proven upper bound for the Erdos minimum overlap constant using exact rational arithmetic.

REASON 2

Study how a computer-assisted proof turns a numerical construction into a machine-checkable certificate.

REASON 3

Reference the current best proven bounds and their attribution when researching this specific open problem.

What's in the stack?

Python

How it stacks up

techno-optimist/erdos-minimum-overlap-bound0xallam/my-recipe0xhassaan/nn-from-scratch
Stars00
LanguagePythonPythonPython
Last pushed2022-11-22
MaintenanceDormant
Setup difficultyeasymoderatemoderate
Complexity3/52/54/5
Audienceresearchergeneraldeveloper

Figures from each repo's GitHub metadata at analysis time.

How do you spin it up?

Difficulty · easy Time to first run · 5min

Only Python 3.10 or newer and the standard library are needed to run the verification commands.

Wtf does this do

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.

Yoink these prompts

Prompt 1
Explain what the Erdos minimum overlap constant is and why a tighter upper bound matters here.
Prompt 2
Walk me through running `make verify` and interpreting whether the certificates pass.
Prompt 3
Help me understand why the lnzwz construction needed a minimal admissibility repair before certification.
Prompt 4
Summarize what this project proves versus what it explicitly does not prove.

Frequently asked questions

wtf is erdos-minimum-overlap-bound?

A computer-verified math research note proving a slightly tighter upper limit on the long-studied Erdos minimum overlap constant.

What language is erdos-minimum-overlap-bound written in?

Mainly Python. The stack also includes Python.

How hard is erdos-minimum-overlap-bound to set up?

Setup difficulty is rated easy, with roughly 5min to a first successful run.

Who is erdos-minimum-overlap-bound for?

Mainly researcher.

View the repo → Decode another repo

This repo across BitVibe Labs

Don't trust strangers blindly. Verify against the repo.