AFTD Auto-Formalizing Theoretical Domains

Research Blogs

当含负数的3元邮票基与经典范围相差为1时

low tier2026-10-24本文含 2 个研究级成果审阅: CodexEnglish

摘要

邮票问题旨在寻找可表示为 $(k+1)$ 元基的 $h$ 重和的最大非负整数连续区间 $[0, n]$。当要求基中包含负整数时,其极值范围记为 $n^\flat_h(k)$。对于大小为 3 的基($k=2$)以及奇数 $h \ge 5$,由 arXiv:2610.19470 已知 $n^\flat_h(2)$ 严格小于经典正基极值 $n_h(2) = \lfloor (h^2+6h+1)/4 \rfloor$,而 $n^\flat_h(2)$ 的确切值以及差额 $n_h(2) - n^\flat_h(2)$ 的大小仍未解决。本文证明,达到最小差额 $n^\flat_h(2) = n_h(2) - 1$ 当且仅当 $h \equiv 9 \pmod{12}$。该证明在 $h = 12r+9$ 时构造了一个达到该界的显式族 $\{-(2r+2), 2r+2, 4r+5\}$,并证明了对于所有其他奇数 $h \ge 5$,差额至少为 $2$。此外,本文给出了 $h = 419$($419 \equiv 59 \pmod{60}$)处的差额界限,确立了 $n^\flat_{419}(2) \le n_{419}(2) - 6 = 44513$。该界限否定了本项调查中提出的一条公式——该公式猜想对所有 $h \equiv 59 \pmod{60}$ 均有 $n^\flat_h(2) = n_h(2) - 4$,其原因在于所有差额不超过 5 的候选基都因其步长差存在非平凡公因子而失效。所有定义、引理和定理均已在 Lean 4 中形式化验证。

1. 引言

设 $h \ge 1$ 和 $k \ge 1$ 为正整数。在加法数论中,非负整数 $n$ 的 $h$-基是有限整数集 $A$,使得离散区间 $[0, n]$ 中的每个整数都可以表示为 $A$ 的 $h$ 个元素之和。在邮票问题的经典表述中,基 $A$ 由 $k+1$ 个非负整数组成,通常包含 $0$。经典极值邮票数 $n_h(k)$ 定义为使得存在包含 $0$ 的 $(k+1)$ 元子集 $A \subset \mathbb{N}_0$ 满足 $[0, n] \subseteq hA$ 的最大整数 $n$,其中 $hA$ 表示由 $A$ 的 $h$ 个元素的所有和组成的 $h$ 重和集。

对于基数大小为 3 的基($k = 2$),经典极值邮票数对所有 $h \ge 1$ 是已知的: $$n_h(2) = \left\lfloor \frac{h^2 + 6h + 1}{4} \right\rfloor.$$ 当 $h$ 为奇数时,分子 $h^2 + 6h + 1$ 总是能被 4 整除。事实上,对于整数 $m \ge 0$,令 $h = 2m + 1$,代数展开可得 $$(2m+1)^2 + 6(2m+1) + 1 = 4m^2 + 4m + 1 + 12m + 6 + 1 = 4(m^2 + 4m + 2),$$ 这恰好是 4 的整数倍。因此,对于所有奇数 $h$,向下取整运算是精确的:$n_h(2) = (h^2 + 6h + 1)/4$。

该问题的一个自然变体允许基 $A \subset \mathbb{Z}$ 中包含负整数。当允许负数项时,加法组合可以相互抵消,从而产生其他表示模式。对于任何有限集 $A \subset \mathbb{Z}$,其 $h$-范围 $n_h(A)$ 是使得从 $0$ 到 $n$ 的每个整数都属于精确的 $h$ 重和集 $hA$ 的最大整数 $n$。将注意力限制在包含至少一个严格负整数的大小为 $k+1$ 的基上,允许负数的邮票数 $n^\flat_h(k)$ 定义为 $n_h(A)$ 在所有此类集合上的上确界。

允许负数的加法基的研究在题为“Positivity and negativity for $h$-bases for $n$”的 arXiv:2610.19470 中提出并进行了分析。该论文的一个核心结论(在 arXiv:2610.19470 的定理 4.1 中对奇数 $h \ge 3$ 给出证明,并在其中对 $h=1$ 进行了单独验证)是:对于每个奇数 $h \ge 1$,允许负数的 3-邮票数严格小于经典非负邮票数: $$n^\flat_h(2) < n_h(2).$$ 由于 $n^\flat_h(2)$ 和 $n_h(2)$ 都是整数,这个严格不等式等价于上界 $$n^\flat_h(2) \le n_h(2) - 1.$$ 然而,arXiv:2610.19470 的定理 4.1 未能确定 $n^\flat_h(2)$ 的确切值。特别是,它没有确定严格不等式是否仅相差一个单位——即是否 $n^\flat_h(2) = n_h(2) - 1$——或者对于某些或所有奇数 $h$,是否会出现更大的差额 $n_h(2) - n^\flat_h(2) \ge 2$。

本项调查中提出的一条实验公式建议根据模 60 的剩余类进行详细分类;该公式独立于 arXiv:2610.19470 的结果。特别是,它猜想对于 $h \equiv 59 \pmod{60}$,差额恒为 4: $$n^\flat_h(2) = n_h(2) - 4.$$

本文介绍了在 Lean 4 中验证的两个结果:差额为 1 的特征刻画以及对该实验公式的一个反例。

- 确定了差额达到最小值的确切条件:对于奇数 $h \ge 5$,$n^\flat_h(2) = n_h(2) - 1$ 当且仅当 $h \equiv 9 \pmod{12}$,在形式化中验证为 postage_stamp_number_neg_two_add_one_eq_iff。当 $h = 12r + 9$ 时,该值由参数化基族 $\{-(2r+2), 2r+2, 4r+5\}$ 达到。对于所有其他奇数 $h \ge 5$,差额至少为 2。

- 否定了关于 $h \equiv 59 \pmod{60}$ 时差额为 4 的猜想。通过计算满足 $419 = 7 \times 60 - 1 \equiv 59 \pmod{60}$ 的 $h = 419$,在 postage_stamp_number_neg_four_one_nine_two_add_six_le 中证明了 $n^\flat_{419}(2) \le n_{419}(2) - 6 = 44513$。这表明差额可以严格大于 4,其原因在于候选差集中的算术整除性障碍。

2. 预备知识

我们在整数 $\mathbb{Z}$ 与自然数 $\mathbb{N} = \{0, 1, 2, \dots\}$ 上的加性组合学背景下开展工作。这些结果依赖于若干形式化定义,我们在数学记号旁同时列出它们对应的 Lean 4 定义。

定义 1(int_mem_h_fold_sumset)。设 $h \in \mathbb{N}$,并设 $A \subset \mathbb{Z}$ 为有限子集。若存在映射 $f : \{0, \dots, h-1\} \to \mathbb{Z}$ 使得对所有 $i \in \{0, \dots, h-1\}$ 都有 $f(i) \in A$ 且 $$\sum_{i=0}^{h-1} f(i) = m.$$ 则整数 $m \in \mathbb{Z}$ 属于 $h$ 重和集 $hA$,记作 int_mem_h_fold_sumset。

关于定义 1 的注记。该定义要求恰好为 $A$ 的 $h$ 个元素之和,而非至多 $h$ 个元素。当 $0 \in A$ 时,对某些下标选取 $f(i) = 0$ 允许使用少于 $h$ 个非零项进行表示,从而恢复了经典的“至多 $h$ 个元素”的表述。然而,当 $0 \notin A$ 时,该谓词严格要求由来自 $A$ 的恰好 $h$ 项求和。

定义 2(postage_stamp_basis_range)。设 $h \in \mathbb{N}$,并设 $A \subset \mathbb{Z}$ 为有限子集。$A$ 的 $h$-范围记为 $n_h(A)$ 或 postage_stamp_basis_range,定义为 $$n_h(A) = \sup \{ n \in \mathbb{N} \mid \forall m \in \mathbb{N}, m \le n \to m \in hA \},$$ 其中上确界取在自然数的条件完备格中。

关于定义 2 的注记。因为 $A$ 是有限集,所以 $h$ 重和集 $hA$ 是有限集,从而整数集 $\{ n \in \mathbb{N} \mid \forall m \le n, m \in hA \}$ 有上界。当 $0 \notin hA$ 时,没有非负整数 $n$ 满足该条件(因为在 $m = 0 \le n$ 处的检验失败),这意味着满足条件的自然数集为空集。在 Lean 中,按照惯例,$\mathbb{N}$ 中空集的上确界计算为 $0$。因此,只要 $0 \notin hA$,就有 $n_h(A) = 0$。

定义 3(postage_stamp_number_neg)。设 $h, k \in \mathbb{N}$。允许负数的邮票数记为 $n^\flat_h(k)$ 或 postage_stamp_number_neg,定义为 $$n^\flat_h(k) = \sup \{ n \in \mathbb{N} \mid \exists A \subset \mathbb{Z}, |A| = k + 1 \land (\exists a \in A, a < 0) \land n_h(A) = n \}.$$

关于定义 3 的注记。参数 $h$ 和 $k$ 是固定的,而有限集 $A$ 在包含至少一个严格负整数($a < 0$)且基数恰好为 $k + 1$ 的所有 $\mathbb{Z}$ 的子集上变化。在 $k = 2$ 的情况下,集合 $A$ 的基数为 $2 + 1 = 3$。

3. 主要结果

主要结果刻画了对于奇数 $h \ge 5$,3 元基的允许负数邮票数何时相对于经典界限达到最小差额 1。

定理 1(postage_stamp_number_neg_two_add_one_eq_iff)。设 $h \in \mathbb{N}$ 为满足 $h \ge 5$ 的奇整数。则 $$n^\flat_h(2) + 1 = \frac{h^2 + 6h + 1}{4} \iff h \equiv 9 \pmod{12}.$$

由于对每个奇整数 $h$ 都有 $n_h(2) = (h^2 + 6h + 1)/4$,该定理表明允许负数的邮票数与非负极值范围恰好相差 1(即 $n^\flat_h(2) = n_h(2) - 1$)当且仅当 $h \equiv 9 \pmod{12}$。

在 Lean 4 中,定理 postage_stamp_number_neg_two_add_one_eq_iff 接收自然数 $h$、不等式假设 $5 \le h$ 以及奇偶性条件 $h \% 2 = 1$,断言 postage_stamp_number_neg $h$ $2 + 1 = (h^2 + 6h + 1) / 4$ 与 $h \% 12 = 9$ 的等价性,其中除法为自然数截断除法。

第二个结果评估了在特例 $h = 419$ 处的差额。

定理 2(postage_stamp_number_neg_four_one_nine_two_add_six_le)。对于 $h = 419$,允许负数的邮票数满足 $$n^\flat_{419}(2) + 6 \le \frac{419^2 + 6 \cdot 419 + 1}{4} = 44519.$$ 等价地,$n^\flat_{419}(2) \le 44513$。

定理 2 给出了上述关于奇数 $h$ 模 60 的实验公式的一个显式反例。该公式预测对于满足 $h \equiv 59 \pmod{60}$ 的每个奇数 $h$,差额恰好为 4,从而 $n^\flat_h(2) = n_h(2) - 4$。由于 $419 = 60 \times 6 + 59 \equiv 59 \pmod{60}$,猜想公式将要求 $n^\flat_{419}(2) = 44519 - 4 = 44515$。定理 2 证明了实际值满足 $n^\flat_{419}(2) \le 44513$,证明了在 $h = 419$ 处差额至少为 6,从而否定了该猜想。

定理 postage_stamp_number_neg_two_add_one_eq_iff (Lean 4 已验证)
theorem postage_stamp_number_neg_two_add_one_eq_iff (h : ℕ) (hh : 5 ≤ h) (ho : h % 2 = 1) :
    postage_stamp_number_neg h 2 + 1 = (h ^ 2 + 6 * h + 1) / 4 ↔ h % 12 = 9

4. 证明

令 $h=2m+1$ 且 $N=m^2+4m+2=n_h(2)$。证明使用了 arXiv:2610.19470 中定理 4.1 的剩余论证,应用于可能略小于 $N$ 的目标范围 $R$。我们首先解释其定量形式,然后说明同余条件的必要性与充分性,最后给出在 $419$ 处的界限。

剩余不等式。 将任意包含负整数的三元集排序为 $$A=\{a,a+x,a+y\},\qquad a<0,\quad 0<x<y.$$ 用恰好 $h$ 项表示等价于 $$n=ha+sx+ty,\qquad s,t\ge0,\quad s+t\le h.$$ 这里 $s$ 和 $t$ 分别计算项 $a+x$ 和 $a+y$ 的个数,而其余 $h-s-t$ 项等于 $a$。假设 $[0,R]\subseteq hA$,其中 $R\ge h+1$。

首先,$\gcd(x,y)=1$。事实上,每个被表示的整数模该最大公约数都与 $ha$ 同余;同时表示 $0$ 和 $1$ 迫使该公约数整除 $1$。此外 $y\le h+1$。否则选取 $0,1,\ldots,h+1$ 的表示。其中两个表示的 $s$ 值必定重合,因为每个都在 $\{0,\ldots,h\}$ 中。将这两个表示相减,其非零差将是 $y$ 的倍数,然而其绝对值至多为 $h+1<y$。

选取模 $y$ 与 $ha-x$ 同余的 $n_3\in[0,y-1]$ 和 $n_4\in[R-y+1,R]$。它们的表示满足 $(s+1)x\equiv0\pmod y$。互素性给出 $s\equiv-1\pmod y$,从而 $s\ge y-1$。对于 $n_3$,这导出 $$ha\le(y-1)(1-x)=U.$$ 对于 $n_4$,不等式 $t\le h-s$ 给出 $$R-y+1\le n_4\le ha+hy-(y-1)(y-x),$$ 因此 $$L:=R-(h+1)y+1+(y-1)(y-x)\le ha\le U.$$ $ha$ 所在的区间宽度为 $$U-L=N-R-(y-(m+2))^2.\tag{1}$$ 该恒等式是关键约束:较小的差额迫使 $y$ 接近 $m+2$。当 $R=N$ 时,它迫使 $y=m+2$ 并导出已发表的严格界限。其形式化版本为 postage_stamp_basis_range_add_one_le_of_neg_of_odd:每个容许的 $A$ 均满足 $n_h(A)+1\le N$。

差额为 1 的必要性。 现假设 $h\ge5$,从而 $m\ge2$,且一个基覆盖了 $[0,N-1]$。方程 (1) 蕴含 $y\in\{m+1,m+2,m+3\}$。这三种情况构成了 postage_stamp_basis_range_add_two_le_of_neg_of_odd 的算术核心。

若 $y=m+1$,区间宽度为零且 $$ha=m(1-x).$$ 由 $\gcd(2m+1,m)=1$,可得 $h\mid x-1$。但 $0\le x-1\le m-1<h$,故 $x=1$,进而 $ha=0$,与 $a<0$ 矛盾。

若 $y=m+2$,其宽度为 1。因此 $ha=(m+1)(1-x)$ 或 $ha=(m+1)(1-x)-1$。第一个等式迫使 $h\mid x-1$;乘以 $2$ 并模 $h$ 约简后,第二个等式迫使 $h\mid x+1$。由不等式可知 $2\le x\le m+1$:因为尽管 $h\ge5$,$x=1$ 仍会使负倍数 $ha$ 落在 $-1$ 和 $0$ 之间。因此,这两种可整除性均不可能成立,因为所涉及的量均为正数且小于 $h$。

若 $y=m+3$,宽度再次为零且 $$ha=(m+2)(1-x).$$ 两边乘以 $2$ 表明 $h\mid3(x-1)$。此处 $2\le x\le m+2$ 且 $m\ge2$,因此 $$0<3(x-1)\le3(m+1)<2h.$$ 从而 $3(x-1)=h=2m+1$,且 $m\equiv1\pmod3$。若 $m=6r+1$,该等式给出 $x=4r+2$ 以及 $y=6r+4$,由于二者皆为偶数,与互素性矛盾。剩下的可能性是 $m\equiv4\pmod6$,即 $h\equiv9\pmod{12}$。

因此,当后一个同余式不成立时,不存在容许基覆盖 $[0,N-1]$。对每个此类基(包括不表示 $0$ 的集合按惯例范围为零的情况),均有 $n_h(A)+2\le N$。

剩余类的构造。 令 $h=12r+9$,$b=2r+2$,并设 $$A_r=\{-b,b,2b+1\}.$$ 则 $b$ 为偶数,$b\ge2$,$h=6b-3$,且 $N-1=9b^2-3$。我们展示 postage_stamp_basis_range_neg_ge_of_mod_twelve_eq_nine 的形式化证明如何覆盖整个区间。

对于 $0\le n\le9b^2-3$,令 $n=qb+\rho$,其中 $0\le\rho<b$。选取整数 $j\in\{0,1,2,3,4\}$ 并令 $$c=\rho+jb,\qquad D=q-j-2c.$$ 取 $c$ 个 $2b+1$,以及 $(h-c-D)/2$ 个 $-b$ 和 $(h-c+D)/2$ 个 $b$。它们的数量恰好为 $h$,其和为 $$Db+c(2b+1)=qb+\rho=n.$$ 接下来只需确保这些计数是非负整数。

对于 $j$ 的所有 5 种选择,均有 $0\le c\le h$。其他要求是 $-(h-c)\le D\le h-c$ 且 $h-c-D$ 为偶数。等价地, $$3\rho+j(3b+1)-h\le q\le\rho+j(b+1)+h,$$ 其中当 $j$ 为偶数时 $q-\rho$ 为奇数,当 $j$ 为奇数时 $q-\rho$ 为偶数。这 5 种选择给出了下列区间:

| $j$ | $q$ 的下界 | $q$ 的上界 | $q-\rho$ 的奇偶性 | | --- | --- | --- | --- | | 0 | $3\rho-6b+3$ | $\rho+6b-3$ | odd | | 1 | $3\rho-3b+4$ | $\rho+7b-2$ | even | | 2 | $3\rho+5$ | $\rho+8b-1$ | odd | | 3 | $3\rho+3b+6$ | $\rho+9b$ | even | | 4 | $3\rho+6b+7$ | $\rho+10b+1$ | odd |

$n$ 的界限蕴含 $q\le9b-1$,且若 $q=9b-1$ 则 $\rho\le b-3$。对于 $0\le\rho<b$,这些界限确保至少有一行适用。这是形式化证明中所检验的有限个线性不等式与奇偶性分支。相应的计数通过 $A_r$ 的恰好 $h$ 个元素表示了 $n$。因此 $n_h(A_r)\ge N-1$。

过渡到极值。 容许基的范围集合非空(以 $\{-1,0,1\}$ 为例),且由严格界限知有上界 $N-1$。因此其在 $\mathbb N$ 中的上确界满足这些上界。当 $h\not\equiv9\pmod{12}$ 时,更强的逐基不等式给出 $n^\flat_h(2)\le N-2$。当 $h\equiv9\pmod{12}$ 时,显式基 $A_r$ 具有三个不同元素,包含 $-b<0$,且给出 $n^\flat_h(2)\ge N-1$。结合普遍上界,这证明了 $$n^\flat_h(2)+1=N\iff h\equiv9\pmod{12},$$ 如 postage_stamp_number_neg_two_add_one_eq_iff 所陈述。

$h=419$ 处的障碍。 此时 $m=209$,$N=44519$,并设 $R=N-5=44514$。若存在容许基覆盖 $[0,R]$,则方程 (1) 给出 $$(y-211)^2\le5,\qquad209\le y\le213.$$ 此外,对于整数 $0\le k\le5$ 有 $ha=U-k$。对 $y$ 的这 5 个可能取值中的每一个,施加条件 $$419a=(y-1)(1-x)-k,\qquad a<0,\quad0<x<y.$$ 在施加互素性之前,枚举 $k$ 的 6 个可能取值只剩下这些数对:

| $y$ | 可能的 $x$ | 对应的最大公约数 | | --- | --- | --- | | 210 | $3,5,7,9$ | $3,5,7,3$ | | 212 | $138,140$ | $2,4$ |

在 $y=209,211,213$ 处无解。表中的每个数对的最大公约数都大于 1,与必要条件 $\gcd(x,y)=1$ 矛盾。该有限枚举在 Lean 证明中通过整数算术完成;所列出的数对是不可能的候选,而非达到目标范围的基。

因此不存在容许基覆盖 $[0,44514]$,且每个范围至多为 $44513$。取上确界给出 $$n^\flat_{419}(2)+6\le44519,$$ 此即 postage_stamp_number_neg_four_one_nine_two_add_six_le。由于 $419\equiv59\pmod{60}$,提议的差额为 4 的公式本应要求 $n^\flat_{419}(2)=44515$,这与此界限矛盾。

5. 讨论

对于奇数 $h\ge5$,这些结果精确确定了 arXiv:2610.19470 中的严格不等式何时仅相差 1:这恰好发生在 $h\equiv9\pmod{12}$ 时。该结论涉及所有包含负元素的三元整数基的最优值。它强于对某一选定族的分析,因为剩余不等式排除了该类之外的每一个竞争基。

构造与排除论证起着互补的作用。基族 $\{-(2r+2),2r+2,4r+5\}$ 给出了所有 $r\ge0$ 的下界,而严格的普遍上界证明了其最优性。在其他情况下,更强的普遍界限确立了至少为 2 的差额。这些论断并未确定每个其他剩余类中的确切差额。

在 $419$ 处的反例也有一个有限但明确的结论。它证明了此处的差额至少为 6;它并没有计算出 $n^\flat_{419}(2)$ 的确切值。它否定了将差额 4 分配给模 $60$ 的剩余类 $59$ 的特定实验公式。单个反例并不排除所有可能的周期性描述,也没有声称此类普遍的不可能性。

该反例所揭示的,是方程 (1) 中的宽度限制之外的整除性障碍。该限制首先留下了最大步长差的简短可能列表。平移的整性随后留下了六对步长。每一对都无法满足表示连续整数所需的互素性。保留这最后的检验至关重要:仅凭 $ha$ 的狭窄区间并不能提供有效的加法基。

进一步的问题包括确定差额为 1 的类之外的确切值,以及确定随着奇数 $h$ 的增长差额是否保持有界。目前的特征刻画和在 $419$ 处的界限均未回答这两个问题。它们在一个类中提供了一个显式的最优族,并提供了一个有限障碍,说明了为什么其他类的提议公式需要修正。

为什么是研究级成果

  • a new question answered: decides when the strict inequality n♭_h(2) < n_h(2) loses only one: exactly when h ≡ 9 (mod 12) (h ≥ 5)
  • a new question answered: At h = 419 the gap is at least 6: the Theorem 4.1 inequalities at range N - 5 leave only six sets a + {0,x,y}, and each has gcd(x,y) > 1 (y = 210 = 2·3·5·7 with x ∈ {3,5,7,9}, or y = 212 with x ∈ {138,140}).

Lean 声明

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

参考文献

  1. arXiv:2610.19470 — Positivity and negativity for $h$-bases for $n$

由 gemini-3.8-flash 根据知识库起草,经过检查并由 Codex 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。