Michael Schroeder · Preprint · Version 1 · 22 September 2026 · ORCID 0009-0004-3249-0195

Erdős Problem 278: Formulas and Complexity of Maximum Covered Density

Abstract

Given distinct moduli, how much of the integers can one cover by choosing one residue class for each? When classes with noncoprime moduli can be made disjoint, a signed independence-polynomial formula gives the maximum. An optimal residue vector is explicit if every prime p divides at most p moduli. Nevertheless, evaluating this formula is #P-hard for polynomially bounded squarefree three-prime moduli with a cubic noncoprime graph. Complete-covering decision is NP-hard for distinct moduli; threshold decision is deterministically NP-complete even on prime–modulus incidence trees. In contrast, exact optimization and optimizer recovery are fixed-parameter tractable in noncoprime-graph treewidth, without supplied factorizations. We also disprove an unrestricted extension of a coprime inclusion–exclusion bound. Saturated local trees and convex compression provide exact representations. A scoped Lean companion verifies structural results for supplied coprime coordinates; the complexity classifications and specified arithmetic extensions remain written proofs.

Explore the problem interactively Companion downloads

Read the Paper

Companion and Verification Materials

The archive includes the PDF and self-contained LaTeX manuscript, 187 selected Lean source files, nine Python reference and audit modules, five regression suites, an illustration checker, dependency pins, reproduction instructions and verification records.

Start with README.md in the archive, then lean/PUBLICATION_SCOPE.md for the paper-to-theorem mapping. The source-only package excludes build caches, compiled proofs, downloaded dependencies and private working notes.

Citation and file integrity

Schroeder, Michael. Erdős Problem 278: Formulas and Complexity of Maximum Covered Density. Version 1, Zenodo, 2026. DOI: 10.5281/zenodo.22874487. Download the BibTeX citation.

The PDF and ZIP on this site are byte-identical to the published Zenodo files. Download the SHA-256 checksums for both files. The archive also contains a manifest covering its 346 payload files and a verification script.

The manuscript is dated 21 September 2026; its first public release was 22 September 2026. Preparation-time references to a reserved DOI inside the unchanged archive describe the pre-publication checkpoint. The Zenodo record is now public.

The Problem

Erdős Problem 278 asks about the densities left uncovered by residue classes with prescribed distinct moduli. This paper studies the maximum covered density, or equivalently the minimum missed density. It separates choosing the residue classes from evaluating their exact density: even when an optimal choice is explicit, exact evaluation can remain counting-hard.

The results give formulas for structured families, algorithms for bounded noncoprime-graph treewidth, and hardness classifications for restricted inputs. They do not claim that the problem website has accepted Erdős Problem 278 as solved.

An interactive companion

How much of infinity can you cover?

Choose one repeating class for each modulus. Shift its starting point. Your goal: cover as many integers as possible. Because the pattern repeats, one finite period tells the whole story.

For {2, 4, 6}, the classes 1 mod 2, 0 mod 4 and 0 mod 6 cover 10 of every 12 integers. The maximum covered density is 5/6. Enable JavaScript in a modern browser to explore this and other examples.

Licence and Assistance

The original manuscript, documentation and audit outputs are licensed under CC BY 4.0. Original code, including the Lean and Python sources and build helpers, is licensed under Apache 2.0. Third-party licences and notices are preserved. See RIGHTS.md in the archive for the material-specific allocation.

This work benefited from research assistance by AI systems developed by OpenAI and Anthropic, including support for proof exploration, proof development, and exact computational checks among others.