AFTD Auto-Formalizing Theoretical Domains

Research Blogs

When Negative Three-Stamp Bases Miss the Classical Range by One

low tier2026-10-242 research-level results in one postreviewed by Codex中文版

Abstract

The postage stamp problem asks for the largest consecutive range of non-negative integers $[0, n]$ representable as an $h$-fold sum of a $(k+1)$-element basis. When the basis is required to contain a negative integer, the extremal range is denoted $n^\flat_h(k)$. For bases of size three ($k=2$) and odd $h \ge 5$, it was known from arXiv:2610.19470 that $n^\flat_h(2)$ is strictly smaller than the classical positive-basis extremal value $n_h(2) = \lfloor (h^2+6h+1)/4 \rfloor$, leaving the exact value of $n^\flat_h(2)$ and the size of the deficit $n_h(2) - n^\flat_h(2)$ open. We prove that the minimal deficit $n^\flat_h(2) = n_h(2) - 1$ is attained if and only if $h \equiv 9 \pmod{12}$. The proof constructs an explicit achieving family $\{-(2r+2), 2r+2, 4r+5\}$ when $h = 12r+9$, and shows that for all other odd $h \ge 5$ the deficit is at least $2$. In addition, we bound the deficit at $h = 419$ ($419 \equiv 59 \pmod{60}$), establishing that $n^\flat_{419}(2) \le n_{419}(2) - 6 = 44513$. This bound refutes a formula proposed in this investigation that $n^\flat_h(2) = n_h(2) - 4$ for all $h \equiv 59 \pmod{60}$, because all candidate bases leaving a deficit of 5 or less fail due to non-trivial common divisors in their step differences. All definitions, lemmas, and theorems are formally verified in Lean 4.

1. Introduction

Let $h \ge 1$ and $k \ge 1$ be positive integers. In additive number theory, an $h$-basis for a non-negative integer $n$ is a finite set of integers $A$ such that every integer in the discrete interval $[0, n]$ can be expressed as a sum of $h$ elements of $A$. In the classical formulation of the postage stamp problem, the basis $A$ consists of $k+1$ non-negative integers, typically including $0$. The classical extremal postage stamp number $n_h(k)$ is defined as the maximum integer $n$ for which there exists a $(k+1)$-element subset $A \subset \mathbb{N}_0$ with $0 \in A$ such that $[0, n] \subseteq hA$, where $hA$ denotes the $h$-fold sumset consisting of all sums of $h$ elements of $A$.

For bases of cardinality three ($k = 2$), the classical extremal postage stamp number is known for all $h \ge 1$: $$n_h(2) = \left\lfloor \frac{h^2 + 6h + 1}{4} \right\rfloor.$$ When $h$ is odd, the numerator $h^2 + 6h + 1$ is always divisible by 4. Indeed, writing $h = 2m + 1$ for an integer $m \ge 0$, an algebraic expansion yields $$(2m+1)^2 + 6(2m+1) + 1 = 4m^2 + 4m + 1 + 12m + 6 + 1 = 4(m^2 + 4m + 2),$$ which is an exact integer multiple of 4. Therefore, for all odd $h$, the floor operation is exact: $n_h(2) = (h^2 + 6h + 1)/4$.

A natural variant of the problem admits negative integers into the basis $A \subset \mathbb{Z}$. When negative entries are permitted, additive combinations can cancel, creating alternative representation patterns. For any finite set $A \subset \mathbb{Z}$, its $h$-range $n_h(A)$ is the maximum integer $n$ such that every integer from $0$ up to $n$ belongs to the exact $h$-fold sumset $hA$. Restricting attention to bases of size $k+1$ that contain at least one strictly negative integer, the negative-allowed postage stamp number $n^\flat_h(k)$ is defined as the supremum of $n_h(A)$ over all such sets.

The study of negative-allowed additive bases was formulated and analyzed in arXiv:2610.19470, titled "Positivity and negativity for $h$-bases for $n$". A central finding of that paper, proved for odd $h \ge 3$ in Theorem 4.1 of arXiv:2610.19470, with $h=1$ checked separately there, is that for every odd $h \ge 1$, the negative-allowed three-stamp number is strictly smaller than the classical non-negative stamp number: $$n^\flat_h(2) < n_h(2).$$ Because $n^\flat_h(2)$ and $n_h(2)$ are integers, this strict inequality is equivalent to the upper bound $$n^\flat_h(2) \le n_h(2) - 1.$$ However, Theorem 4.1 of arXiv:2610.19470 left the exact value of $n^\flat_h(2)$ open. In particular, it did not determine whether the strict inequality loses only one unit—that is, whether $n^\flat_h(2) = n_h(2) - 1$—or whether a larger deficit $n_h(2) - n^\flat_h(2) \ge 2$ occurs for certain or all odd values of $h$.

An experimental formula proposed in this investigation suggested a detailed classification according to residue classes modulo 60; this formula is separate from the results of arXiv:2610.19470. In particular, it conjectured that for $h \equiv 59 \pmod{60}$, the deficit is constantly 4: $$n^\flat_h(2) = n_h(2) - 4.$$

This post presents two results verified in Lean 4: a characterization of deficit one and a counterexample to that experimental formula.

- We settle the exact condition under which the deficit is minimal: for odd $h \ge 5$, $n^\flat_h(2) = n_h(2) - 1$ if and only if $h \equiv 9 \pmod{12}$, verified as postage_stamp_number_neg_two_add_one_eq_iff. When $h = 12r + 9$, the value is achieved by the parameterized family of bases $\{-(2r+2), 2r+2, 4r+5\}$. For all other odd $h \ge 5$, the deficit is at least 2.

- We refute the conjectured deficit of 4 for $h \equiv 59 \pmod{60}$. By evaluating $h = 419$, which satisfies $419 = 7 \times 60 - 1 \equiv 59 \pmod{60}$, we show in postage_stamp_number_neg_four_one_nine_two_add_six_le that $n^\flat_{419}(2) \le n_{419}(2) - 6 = 44513$. This shows that the deficit can be strictly greater than 4, caused by arithmetic divisibility obstructions in candidate difference sets.

2. Preliminaries

We work in the setting of additive combinatorics on the integers $\mathbb{Z}$ and natural numbers $\mathbb{N} = \{0, 1, 2, \dots\}$. The results rely on several formal definitions, which we state in mathematical notation alongside their corresponding Lean 4 definitions.

Definition 1 (int_mem_h_fold_sumset). Let $h \in \mathbb{N}$ and let $A \subset \mathbb{Z}$ be a finite subset. An integer $m \in \mathbb{Z}$ belongs to the $h$-fold sumset $hA$, denoted by int_mem_h_fold_sumset, if there exists a map $f : \{0, \dots, h-1\} \to \mathbb{Z}$ such that $f(i) \in A$ for all $i \in \{0, \dots, h-1\}$ and $$\sum_{i=0}^{h-1} f(i) = m.$$

Remark on Definition 1. The definition requires an exact sum of $h$ elements of $A$, rather than at most $h$ elements. When $0 \in A$, choosing $f(i) = 0$ for some indices allows representations with fewer than $h$ non-zero terms, recovering the classical "at most $h$ elements" formulation. When $0 \notin A$, however, the predicate strictly requires a sum of exactly $h$ terms from $A$.

Definition 2 (postage_stamp_basis_range). Let $h \in \mathbb{N}$ and let $A \subset \mathbb{Z}$ be a finite subset. The $h$-range of $A$, denoted $n_h(A)$ or postage_stamp_basis_range, is defined by $$n_h(A) = \sup \{ n \in \mathbb{N} \mid \forall m \in \mathbb{N}, m \le n \to m \in hA \},$$ where the supremum is taken in the conditionally complete lattice of natural numbers.

Remark on Definition 2. Because $A$ is finite, the $h$-fold sumset $hA$ is finite, so the set of integers $\{ n \in \mathbb{N} \mid \forall m \le n, m \in hA \}$ is bounded above. When $0 \notin hA$, no non-negative integer $n$ satisfies the condition (since the test at $m = 0 \le n$ fails), meaning the set of satisfying natural numbers is empty. In Lean, the supremum of the empty set in $\mathbb{N}$ evaluates to $0$ by convention. Thus $n_h(A) = 0$ whenever $0 \notin hA$.

Definition 3 (postage_stamp_number_neg). Let $h, k \in \mathbb{N}$. The negative-allowed postage stamp number, denoted $n^\flat_h(k)$ or postage_stamp_number_neg, is defined by $$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 \}.$$

Remark on Definition 3. The parameters $h$ and $k$ are fixed, while the finite set $A$ varies over all subsets of $\mathbb{Z}$ with cardinality exactly $k + 1$ that contain at least one strictly negative integer ($a < 0$). In the case $k = 2$, the set $A$ has cardinality $2 + 1 = 3$.

3. Main result

The primary result classifies when the negative-allowed postage stamp number for 3-element bases achieves the minimal deficit of 1 relative to the classical bound for odd $h \ge 5$.

Theorem 1 (postage_stamp_number_neg_two_add_one_eq_iff). Let $h \in \mathbb{N}$ be an odd integer with $h \ge 5$. Then $$n^\flat_h(2) + 1 = \frac{h^2 + 6h + 1}{4} \iff h \equiv 9 \pmod{12}.$$

Since $n_h(2) = (h^2 + 6h + 1)/4$ for every odd integer $h$, this theorem asserts that the negative-allowed postage stamp number misses the non-negative extremal range by exactly 1, $n^\flat_h(2) = n_h(2) - 1$, if and only if $h \equiv 9 \pmod{12}$.

In Lean 4, the theorem postage_stamp_number_neg_two_add_one_eq_iff takes a natural number $h$, the inequality hypothesis $5 \le h$, and the parity condition $h \% 2 = 1$, asserting the equivalence of postage_stamp_number_neg $h$ $2 + 1 = (h^2 + 6h + 1) / 4$ and $h \% 12 = 9$ where division is natural number truncation.

A second result evaluates the deficit at the instance $h = 419$.

Theorem 2 (postage_stamp_number_neg_four_one_nine_two_add_six_le). For $h = 419$, the negative-allowed postage stamp number satisfies $$n^\flat_{419}(2) + 6 \le \frac{419^2 + 6 \cdot 419 + 1}{4} = 44519.$$ Equivalently, $n^\flat_{419}(2) \le 44513$.

Theorem 2 gives an explicit counterexample to the experimental formula for odd $h$ modulo 60 described above. That formula predicted that for every odd $h$ satisfying $h \equiv 59 \pmod{60}$, the deficit is precisely 4, so that $n^\flat_h(2) = n_h(2) - 4$. Since $419 = 60 \times 6 + 59 \equiv 59 \pmod{60}$, the conjectured formula would require $n^\flat_{419}(2) = 44519 - 4 = 44515$. Theorem 2 proves that the actual value satisfies $n^\flat_{419}(2) \le 44513$, demonstrating that the deficit at $h = 419$ is at least 6 and refuting the conjecture.

Theorem postage_stamp_number_neg_two_add_one_eq_iff (Lean 4, verified)
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. Proof

Write $h=2m+1$ and $N=m^2+4m+2=n_h(2)$. The proofs use the residue argument of Theorem 4.1 in arXiv:2610.19470, applied at a target range $R$ that may be slightly smaller than $N$. We first explain its quantitative form, then the necessity and sufficiency of the congruence condition, and finally the bound at $419$.

The residue inequalities. Order any three-element set containing a negative integer as $$A=\{a,a+x,a+y\},\qquad a<0,\quad 0<x<y.$$ A representation by exactly $h$ terms is equivalent to $$n=ha+sx+ty,\qquad s,t\ge0,\quad s+t\le h.$$ Here $s$ and $t$ count the terms $a+x$ and $a+y$, while the other $h-s-t$ terms equal $a$. Suppose $[0,R]\subseteq hA$, where $R\ge h+1$.

First, $\gcd(x,y)=1$. Indeed, every represented integer is congruent to $ha$ modulo that gcd; representing both $0$ and $1$ forces the gcd to divide $1$. Also $y\le h+1$. Otherwise choose representations of $0,1,\ldots,h+1$. Two of their $s$ values must coincide, since each is in $\{0,\ldots,h\}$. Subtracting the two representations makes their nonzero difference a multiple of $y$, although its absolute value is at most $h+1<y$.

Choose $n_3\in[0,y-1]$ and $n_4\in[R-y+1,R]$ congruent to $ha-x$ modulo $y$. Their representations satisfy $(s+1)x\equiv0\pmod y$. Coprimality gives $s\equiv-1\pmod y$, and hence $s\ge y-1$. For $n_3$, this yields $$ha\le(y-1)(1-x)=U.$$ For $n_4$, the inequality $t\le h-s$ gives $$R-y+1\le n_4\le ha+hy-(y-1)(y-x),$$ so $$L:=R-(h+1)y+1+(y-1)(y-x)\le ha\le U.$$ The interval for $ha$ has width $$U-L=N-R-(y-(m+2))^2.\tag{1}$$ This identity is the key restriction: a small deficit forces $y$ close to $m+2$. At $R=N$, it forces $y=m+2$ and leads to the published strict bound. Its formal version is postage_stamp_basis_range_add_one_le_of_neg_of_odd: every admissible $A$ satisfies $n_h(A)+1\le N$.

Necessity for deficit one. Now suppose $h\ge5$, so $m\ge2$, and a basis covers $[0,N-1]$. Equation (1) implies $y\in\{m+1,m+2,m+3\}$. These three cases are the arithmetic core of postage_stamp_basis_range_add_two_le_of_neg_of_odd.

If $y=m+1$, the interval has width zero and $$ha=m(1-x).$$ Since $\gcd(2m+1,m)=1$, we obtain $h\mid x-1$. But $0\le x-1\le m-1<h$, so $x=1$ and then $ha=0$, contradicting $a<0$.

If $y=m+2$, its width is one. Thus $ha=(m+1)(1-x)$ or $ha=(m+1)(1-x)-1$. The first equality forces $h\mid x-1$, and the second forces $h\mid x+1$ after multiplication by $2$ and reduction modulo $h$. The inequalities imply $2\le x\le m+1$: $x=1$ would put the negative multiple $ha$ between $-1$ and $0$, although $h\ge5$. Consequently both possible divisibilities are impossible, since the quantities concerned are positive and smaller than $h$.

If $y=m+3$, the width is again zero and $$ha=(m+2)(1-x).$$ Multiplying by $2$ shows $h\mid3(x-1)$. Here $2\le x\le m+2$ and $m\ge2$, so $$0<3(x-1)\le3(m+1)<2h.$$ Therefore $3(x-1)=h=2m+1$, and $m\equiv1\pmod3$. If $m=6r+1$, this equality gives $x=4r+2$ and $y=6r+4$, contradicting coprimality because both are even. The remaining possibility is $m\equiv4\pmod6$, or $h\equiv9\pmod{12}$.

Thus, when the latter congruence fails, no admissible basis covers $[0,N-1]$. This gives $n_h(A)+2\le N$ for every such basis, including the conventionally zero range of a set that does not represent $0$.

A construction for the remaining class. Put $h=12r+9$, $b=2r+2$, and $$A_r=\{-b,b,2b+1\}.$$ Then $b$ is even, $b\ge2$, $h=6b-3$, and $N-1=9b^2-3$. We show how the formal proof of postage_stamp_basis_range_neg_ge_of_mod_twelve_eq_nine covers this entire interval.

For $0\le n\le9b^2-3$, write $n=qb+\rho$ with $0\le\rho<b$. Choose an integer $j\in\{0,1,2,3,4\}$ and put $$c=\rho+jb,\qquad D=q-j-2c.$$ Use $c$ copies of $2b+1$, together with $(h-c-D)/2$ copies of $-b$ and $(h-c+D)/2$ copies of $b$. Their number is exactly $h$, and their sum is $$Db+c(2b+1)=qb+\rho=n.$$ It remains to ensure that these counts are nonnegative integers.

For all five choices of $j$, one has $0\le c\le h$. The other requirements are $-(h-c)\le D\le h-c$ and $h-c-D$ even. Equivalently, $$3\rho+j(3b+1)-h\le q\le\rho+j(b+1)+h,$$ with $q-\rho$ odd for even $j$ and even for odd $j$. The five choices give the following intervals:

| $j$ | lower bound for $q$ | upper bound for $q$ | parity of $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 |

The bounds on $n$ imply $q\le9b-1$, with $\rho\le b-3$ if $q=9b-1$. For $0\le\rho<b$, these bounds ensure that at least one row applies. This is the finite set of linear inequalities and parity alternatives checked in the formal proof. The corresponding counts represent $n$ by exactly $h$ elements of $A_r$. Hence $n_h(A_r)\ge N-1$.

Passing to the extremum. The set of ranges of admissible bases is nonempty, witnessed by $\{-1,0,1\}$, and bounded above by $N-1$ using the strict bound. Its supremum in $\mathbb N$ therefore respects these upper bounds. When $h\not\equiv9\pmod{12}$, the stronger per-basis inequality gives $n^\flat_h(2)\le N-2$. When $h\equiv9\pmod{12}$, the explicit basis $A_r$ has three distinct elements, contains $-b<0$, and gives $n^\flat_h(2)\ge N-1$. Together with the universal upper bound, this proves $$n^\flat_h(2)+1=N\iff h\equiv9\pmod{12},$$ as stated in postage_stamp_number_neg_two_add_one_eq_iff.

The obstruction at $h=419$. Here $m=209$, $N=44519$, and set $R=N-5=44514$. If an admissible basis covered $[0,R]$, equation (1) would give $$(y-211)^2\le5,\qquad209\le y\le213.$$ Moreover $ha=U-k$ for an integer $0\le k\le5$. For each of these five possible values of $y$, impose $$419a=(y-1)(1-x)-k,\qquad a<0,\quad0<x<y.$$ Enumerating the six possible values of $k$ leaves only these pairs, before imposing coprimality:

| $y$ | possible $x$ | corresponding gcds | | --- | --- | --- | | 210 | $3,5,7,9$ | $3,5,7,3$ | | 212 | $138,140$ | $2,4$ |

There are no solutions at $y=209,211,213$. Every pair in the table has gcd greater than one, contradicting the necessary condition $\gcd(x,y)=1$. This finite enumeration is carried out by integer arithmetic in the Lean proof; the listed pairs are impossible candidates, not bases achieving the target range.

Thus no admissible basis covers $[0,44514]$, and every range is at most $44513$. Taking the supremum gives $$n^\flat_{419}(2)+6\le44519,$$ which is postage_stamp_number_neg_four_one_nine_two_add_six_le. Since $419\equiv59\pmod{60}$, the proposed deficit-four formula would instead require $n^\flat_{419}(2)=44515$, contradicting this bound.

5. Discussion

For odd $h\ge5$, the results determine exactly when the strict inequality from arXiv:2610.19470 loses only one: this happens precisely at $h\equiv9\pmod{12}$. The conclusion concerns the optimum over all three-element integer bases containing a negative element. It is stronger than an analysis of one selected family, because the residue inequalities exclude every competing basis outside that class.

The construction and exclusion arguments have complementary roles. The family $\{-(2r+2),2r+2,4r+5\}$ gives the lower bound for all $r\ge0$, while the strict universal bound certifies its optimality. Elsewhere, the stronger universal bound establishes a deficit of at least two. These statements do not determine the exact deficit in every other residue class.

The counterexample at $419$ also has a limited but definite conclusion. It proves that the deficit is at least six there; it does not compute the exact value of $n^\flat_{419}(2)$. It rejects the specific experimental formula assigning deficit four to the class $59$ modulo $60$. A single counterexample does not rule out every possible periodic description, and no such general impossibility is claimed.

What the example does expose is a divisibility obstruction beyond the width restriction in equation (1). That restriction first leaves a short list of possible largest step differences. The integrality of the translation then leaves six pairs of steps. Each pair fails the coprimality needed to represent consecutive integers. Keeping this last check is essential: a narrow interval for $ha$ alone does not provide a valid additive basis.

Further questions include determining exact values outside the deficit-one class and deciding whether the deficit remains bounded as odd $h$ grows. The present characterization and the bound at $419$ answer neither question. They supply an explicit optimal family in one class and a finite obstruction showing why the proposed formula for the other classes requires revision.

Why it is research-level

  • 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 declarations

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

References

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

Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Codex. Only the Lean is verified; the prose is a reading of it.