The Graph and the Primes: An Exact, Machine-Checked Bijection
This paper restates the distribution of the primes as a problem about a single graph: the vertices are the integers $1,\dots,N$ and the edges are determined by divisibility alone. We prove that the covering relation of this graph (its Hasse diagram) already pins down the primes completely — the primes are exactly the vertices that cover $1$, so that $\pi(N)$ is simply the out-degree of vertex $1$. Going further, the inverse $Z^{-1}$ of the divisibility matrix $Z$ yields the Möbius function $\mu$, the Euler function $\varphi$ and the von Mangoldt function $\Lambda$ in one stroke. On this basis we give two inversion formulas at the level of identities: one writes "$n$ is prime" as a finite signed sum, pointwise in $n$; the other writes $\pi(x)$ as a Möbius combination of $\Pi(\lfloor x^{1/j}\rfloor)$. Both hold exactly — integer equality, error $0$, not asymptotically and not on average — for all $n\le 20000$ and all $x\le 10^{6}$. We also prove an information-theoretic lower bound: describing the set of primes up to $N$ exactly requires at least $\log_2\binom{N}{\pi(N)}$ bits, whereas the "rule" of the graph itself is only $\log_2 N$ bits; at $N=10^6$ the two differ by a factor of $19911$. This explains why no graph with a minimal rule can output the primes exactly. Every statement has been machine-checked in Lean 4: the graph-theoretic layer uses no mathematical library at all, the rational inversion layer is built on mathlib, and together they comprise $27$ theorems and $8$ computational certificates, with no `sorry` and no `axiom`, independently re-checked by `leanchecker` (structural propositions are kernel proofs, finite-range numerical propositions are computational certificates; the precise boundary is stated in Section 7.3). 本文把"素数分布"重新表述为一张图上的问题:顶点是整数 $1,\dots,N$,边只由整除关系决定。我们证明,这张图的覆盖关系(Hasse 图)本身就已经把素数完全确定下来——素数恰好是覆盖顶点 $1$ 的那些点,于是 $\pi(N)$ 就是顶点 $1$ 的出度;进一步,图的整除矩阵 $Z$ 的逆矩阵 $Z^{-1}$ 一次性给出了 Möbius 函数 $\mu$、Euler 函数 $\varphi$ 与 von Mangoldt 函数 $\Lambda$。在此基础上,我们给出两条**恒等式级**的反演公式:逐点地把"$n$ 是不是素数"写成一个有限和,以及把 $\pi(x)$ 写成 $\Pi(\lfloor x^{1/j}\rfloor)$ 的 Möbius 组合。两条公式在 $n\le 20000$ 与 $x\le 10^{6}$ 上全部精确命中(整数相等,误差为 $0$,不是渐近、不是统计)。我们还给出一个信息论下界:精确描述不超过 $N$ 的素数集至少需要 $\log_2\binom{N}{\pi(N)}$ 比特,而图的"规则"本身只有 $\log_2 N$ 比特,两者在 $N=10^6$ 时相差 $19911$ 倍——这解释了为什么"规则极简却能精准给出素数"的图不可能存在。全部结论用 Lean 4 做了机器验证:图论层不依赖任何数学库,有理数反演层基于 mathlib,合计 $27$ 条定理、$8$ 条计算证书,无 `sorry`、无 `axiom`,并通过 `leanchecker` 独立复核(结构性命题为内核证明,有限范围的数值命题为计算证书,界限见第 7.3 节)。
Authors
- Yue Lu (ORCID: https://orcid.org/0009-0008-3405-9170)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-12
- DOI
- https://doi.org/10.5281/zenodo.24153372
- Primary Topic
- Analytic Number Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00