AFTD Auto-Formalizing Theoretical Domains

Research Blogs

For Odd Orders with $h \not\equiv 59 \pmod{60}$, the Negative Three-Stamp Number Equals $n_h(2)$ Minus One, Two, or Three

medium tier2026-10-272 research-level results in one postreviewed by Codex中文版

Abstract

The postage stamp problem asks for the largest integer $n$ such that every integer in $\{0, 1, \dots, n\}$ can be represented as an $h$-fold sum of elements from a $(k+1)$-element basis of integers. In the classical setting where basis elements are non-negative, the extremal range for three-stamp bases ($k = 2$) is given by $n_h(2) = \lfloor (h^2 + 6h + 1)/4 \rfloor$. When negative integers are permitted in the basis, the corresponding extremal range is denoted by $n♭_h(k)$. In arXiv:2610.19470, it was shown that for all odd orders $h \ge 1$, requiring a negative element strictly decreases the achievable range: $n♭_h(2) < n_h(2)$. However, that paper left the exact value of $n♭_h(2)$ and the size of the deficit $n_h(2) - n♭_h(2)$ undetermined. Here, we present the complete determination of $n♭_h(2)$ for all odd integers $h \ge 5$ with $h \not\equiv 59 \pmod{60}$, verified in Lean 4. The gap $n_h(2) - n♭_h(2)$ depends purely on the residue class of $h \pmod{12}$: it equals $1$ if $h \equiv 9 \pmod{12}$, $2$ if $h \equiv 1, 3, 5, 7 \pmod{12}$, and $3$ if $h \equiv 11 \pmod{12}$. For $h \equiv 59 \pmod{60}$, the gap is proved to be at least $4$. The exact values are obtained by establishing modular upper bounds on ranges of three-element integer bases containing a negative element and matching them with explicit parametric constructions through an extremal sandwiching principle.

1. Introduction

Additive basis problems form a central branch of additive number theory. Given positive integers $h$ and $k$, a finite subset $A$ of integers is called an $h$-basis for an integer $n$ if the $h$-fold sumset $$hA = \{a_1 + a_2 + \cdots + a_h : a_1, \dots, a_h \in A\}$$ contains the entire interval of integers $\{0, 1, \dots, n\}$. The postage stamp problem asks for the maximal integer $n$ for which a $(k+1)$-element set $A$ can serve as an $h$-basis.

In the classical formulation of the problem, the basis elements are restricted to be non-negative integers containing zero: $A = \{0, a_1, \dots, a_k\} \subset \mathbb{Z}_{\ge 0}$. The maximal range achievable by such an $A$ is denoted by $n_h(k)$. For bases of size three, corresponding to $k = 2$, the classical postage stamp number is given for all $h \ge 1$ by the closed-form expression $$n_h(2) = \left\lfloor \frac{h^2 + 6h + 1}{4} \right\rfloor.$$

A natural extension of this problem considers bases that are allowed to contain negative integers. Let $A \subset \mathbb{Z}$ be a finite subset of cardinality $k + 1$ that contains at least one strictly negative element. The basis range of $A$, denoted $n_h(A)$, is the largest integer $n$ such that every integer from $0$ to $n$ can be expressed as a sum of exactly $h$ elements of $A$. The extremal quantity $n♭_h(k)$ is defined as the supremum of $n_h(A)$ over all such $(k+1)$-element integer sets containing at least one negative integer.

The question of whether negative elements can expand the representable range in comparison to purely non-negative bases was investigated in arXiv:2610.19470, titled "Positivity and negativity for $h$-bases for $n$". Theorem 4.1 of arXiv:2610.19470 treats odd orders $h \ge 3$, and its proof also computes the case $h=1$. For these orders and $k = 2$, the presence of negative elements cannot increase the basis range. In fact, it established the strict inequality $$n♭_h(2) < n_h(2) = \left\lfloor \frac{h^2 + 6h + 1}{4} \right\rfloor.$$ This showed that for odd $h$, any three-element basis containing a negative integer suffers an unavoidable deficit relative to the optimal non-negative basis.

However, arXiv:2610.19470 established only the strict inequality $n♭_h(2) < n_h(2)$, leaving open the exact value of $n♭_h(2)$ and the precise magnitude of the gap $n_h(2) - n♭_h(2)$. The results below refine that strict comparison by identifying the exact deficit on specified arithmetic progressions. They do not determine the deficit for every odd order.

This post reports on the exact determination of $n♭_h(2)$ for all odd integers $h \ge 5$ outside the single residue class $h \equiv 59 \pmod{60}$, proved and checked in Lean 4 via the theorem postage_stamp_number_neg_two_of_odd_of_mod_sixty_ne. Specifically, the deficit $n_h(2) - n♭_h(2)$ is constant along arithmetic progressions modulo 12:

  • The deficit is $1$ if and only if $h \equiv 9 \pmod{12}$.
  • The deficit is $2$ if $h \equiv 1, 3, 5, 7 \pmod{12}$.
  • The deficit is $3$ if $h \equiv 11 \pmod{12}$ with $h \not\equiv 59 \pmod{60}$.

For the excluded residue class $h \equiv 59 \pmod{60}$, we report on the theorem postage_stamp_number_neg_two_add_four_le_of_mod_sixty_eq, which establishes that the deficit increases further: $$n♭_h(2) \le n_h(2) - 4.$$ At range $n_h(2) - 3$, the inequalities stemming from Theorem 4.1 in arXiv:2610.19470 leave only candidates where the differences from the smallest basis element share a common factor greater than $1$ or produce divisibility contradictions. Here $x$ and $y$ denote the differences from the smallest basis element, rather than the positive basis elements themselves.

2. Preliminaries

Let $\mathbb{Z}$ denote the ring of integers and $\mathbb{N} = \{0, 1, 2, \dots\}$ the set of natural numbers. For any subset $A \subset \mathbb{Z}$ and any $h \in \mathbb{N}$, the $h$-fold sumset $hA$ consists of all integers representable as $a_1 + \dots + a_h$ with $a_i \in A$. When $h = 0$, $0A = \{0\}$.

Definition 1 (postage_stamp_basis_range). For an order $h \in \mathbb{N}$ and a finite subset $A \subset \mathbb{Z}$, the postage stamp basis range $n_h(A)$ is defined as $$n_h(A) = \sup \{ n \in \mathbb{N} \mid \forall m \in \mathbb{N}, m \le n \implies m \in hA \}.$$ In Lean 4, this is formalized by postage_stamp_basis_range using the supremum sSup in the conditionally complete order on $\mathbb{N}$. Because $A$ is finite, the sumset $hA$ is finite, and the set of natural numbers whose initial segment $[0, n]$ is contained in $hA$ is bounded above. When $0 \notin hA$, no non-negative integer $m \le n$ can be represented for $m = 0$, so the set is empty; in Lean, the supremum of the empty set in $\mathbb{N}$ is defined to be $0$. This choice only affects sets that fail to represent $0$, which cannot form an $h$-basis for any positive range.

Definition 2 (postage_stamp_number_neg). For an order $h \in \mathbb{N}$ and a size parameter $k \in \mathbb{N}$, the negative-allowed postage stamp number $n♭_h(k)$ is defined by $$n♭_h(k) = \sup \{ n \in \mathbb{N} \mid \exists A \subset \mathbb{Z}, |A| = k + 1 \wedge (\exists a \in A, a < 0) \wedge n_h(A) = n \}.$$ In Lean 4, this is formalized by postage_stamp_number_neg. The cardinality constraint requires $|A| = k + 1$, so for $k = 2$ the sets $A$ have exactly three distinct integer elements. The definition imposes the strict inequality $a < 0$ on at least one element of $A$. Like postage_stamp_basis_range, the definition is noncomputable and uses sSup on $\mathbb{N}$.

For odd $h \ge 1$, we write $h = 2m + 1$ with $m \in \mathbb{N}$. The classical positive three-stamp bound evaluates to $$\left\lfloor \frac{h^2 + 6h + 1}{4} \right\rfloor = \left\lfloor \frac{(2m+1)^2 + 6(2m+1) + 1}{4} \right\rfloor = \left\lfloor \frac{4m^2 + 16m + 8}{4} \right\rfloor = m^2 + 4m + 2.$$ Because $4m^2 + 16m + 8$ is an exact multiple of 4, the integer division has zero remainder for all odd $h$. The condition $h \ge 5$ is equivalent to $m \ge 2$.

Repetition of elements is permitted in each sum, but the number of terms is exactly $h$. In particular, the negative bases used below need not contain zero; a representation with fewer than $h$ summands cannot automatically be padded with zeros. The constructions therefore keep track of all three multiplicities and verify that their sum is $h$.

3. Main result

The main result completely determines the value of $n♭_h(2)$ for all odd orders $h \ge 5$ not congruent to 59 modulo 60.

Theorem 1 (postage_stamp_number_neg_two_of_odd_of_mod_sixty_ne). Let $h \in \mathbb{N}$ be an odd integer with $h \ge 5$ and $h \not\equiv 59 \pmod{60}$. Then $$n♭_h(2) + \Delta(h) = \frac{h^2 + 6h + 1}{4},$$ where the deficit $\Delta(h)$ is given by $$\Delta(h) = \begin{cases} 1 & \text{if } h \equiv 9 \pmod{12}, \\ 2 & \text{if } h \not\equiv 9 \pmod{12} \text{ and } h \not\equiv 11 \pmod{12}, \\ 3 & \text{if } h \equiv 11 \pmod{12}.\end{cases}$$ Equivalently, writing $h = 2m + 1$, the extremal range is $$n♭_h(2) = (m^2 + 4m + 2) - \Delta(h).$$

In Lean 4, the statement of postage_stamp_number_neg_two_of_odd_of_mod_sixty_ne reads the English theorem by taking $h : \mathbb{N}$ under the explicit hypotheses 5 ≤ h, h % 2 = 1, and h % 60 ≠ 59, and asserting that postage_stamp_number_neg h 2 + (if h % 12 = 9 then 1 else if h % 12 ≠ 11 then 2 else 3) is equal to (h ^ 2 + 6 * h + 1) / 4.

The cases covered by $\Delta(h) = 2$ correspond precisely to the residue classes $h \equiv 1, 3, 5, 7 \pmod{12}$, since $h$ is assumed odd. Thus, Theorem 1 determines the value for 29 of the 30 odd residue classes modulo 60. Within the sixth odd residue class modulo 12, namely $h \equiv 11 \pmod{12}$, it covers $h \equiv 11,23,35,47 \pmod{60}$ and leaves $h \equiv 59 \pmod{60}$ undetermined.

For the exceptional residue class $h \equiv 59 \pmod{60}$, the following theorem establishes an upper bound, proving that the deficit is strictly larger than 3.

Theorem 2 (postage_stamp_number_neg_two_add_four_le_of_mod_sixty_eq). Let $h \in \mathbb{N}$ be an odd integer with $h \ge 5$ and $h \equiv 59 \pmod{60}$. Then $$n♭_h(2) + 4 \le \frac{h^2 + 6h + 1}{4}.$$

Theorem 2 shows that for $h \equiv 59 \pmod{60}$, no three-element integer set containing a negative element can achieve range $n_h(2) - 3$, so the gap satisfies $n_h(2) - n♭_h(2) \ge 4$.

Theorem postage_stamp_number_neg_two_of_odd_of_mod_sixty_ne (Lean 4, verified)
theorem postage_stamp_number_neg_two_of_odd_of_mod_sixty_ne (h : ℕ) (hh : 5 ≤ h) (ho : h % 2 = 1)
    (h60 : h % 60 ≠ 59) :
    postage_stamp_number_neg h 2 + (if h % 12 = 9 then 1 else if h % 12 ≠ 11 then 2 else 3) =
      (h ^ 2 + 6 * h + 1) / 4

4. Proof

Write $h=2m+1$ and $N=m^2+4m+2=(h^2+6h+1)/4$. The hypothesis $h\ge5$ gives $m\ge2$. The proof has two parts: rule out ranges above the asserted optimum, then construct bases that reach it. The final step passes from individual basis ranges to their supremum.

Upper bounds from representations. Sort an arbitrary three-element basis containing a negative integer and write it as $A=\{a,a+x,a+y\}$, where $a<0$ and $0<x<y$. Membership in $hA$ is equivalent to the existence of nonnegative integers $s,t$ satisfying $$s+t\le h,\qquad n=ha+sx+ty.$$ The multiplicities of the three elements are $h-s-t,s,t$, so this describes sums of exactly $h$ terms.

Suppose $[0,R]\subseteq hA$, with $R\ge h+1$. Comparing representations of 0 and 1 shows that $\gcd(x,y)=1$. A pigeonhole argument on representations of $0,1,\ldots,h+1$ also gives $y\le h+1$: otherwise, two integers having the same coefficient $s$ would differ by a nonzero multiple of $y$ of absolute value less than $y$, an impossibility, while there are only $h+1$ choices for $s$.

Choose representatives of the residue class $ha-x\pmod y$ in $[0,y-1]$ and $[R-y+1,R]$. These intervals lie in $[0,R]$. In either representation, coprimality forces $s\equiv-1\pmod y$, and hence $s\ge y-1$. Applying this to the lower representative, and applying $t\le h-s$ to the upper representative, gives $$R-(2m+2)y+1+(y-1)(y-x)\le ha\le(y-1)(1-x).$$ These are the inequalities used in the formal upper-bound proofs. Subtracting the left endpoint from the right endpoint, at $R=N-d$, gives the identity $$d-(y-(m+2))^2.$$ Consequently a basis covering that range must satisfy $(y-(m+2))^2\le d$. For $d=1,2,3$, there are only three possible integer values of $y$: $m+1,m+2,m+3$. This finite classification of offsets holds for all $m$; it is not a computation up to a fixed order.

The strict comparison from arXiv:2610.19470 is formalized by postage_stamp_basis_range_add_one_le_of_neg_of_odd: every admissible basis satisfies $n_h(A)+1\le N$. The stronger bound postage_stamp_basis_range_add_two_le_of_neg_of_odd excludes coverage through $N-1$ when $h\not\equiv9\pmod{12}$. In the three possible values of $y$, the displayed interval constrains the integer multiple $ha$ to finitely many offsets from $(y-1)(1-x)$. Divisibility and coprimality eliminate these offsets outside the stated congruence class.

For $m\equiv5\pmod6$, the same analysis at $R=N-2$ excludes all three values of $y$, giving postage_stamp_number_neg_two_of_odd_upper_three. For $m\equiv29\pmod{30}$ it also excludes $R=N-3$, giving postage_stamp_number_neg_two_of_odd_upper_four. To see the additional obstruction explicitly, when $y=m+1$ the latter range forces $$ha=m(1-x)-j,\qquad j\in\{0,1,2\}.$$ It follows that $h$ divides $x-1-2j$. The bounds $1\le x\le m$ make the absolute value of this expression less than $h$, so $x=1+2j$. The choice $j=0$ forces $a=0$, while $j=1,2$ give respectively $x=3,5$. Since $m+1$ is divisible by both 3 and 5, these contradict coprimality. The remaining values $y=m+2,m+3$ are excluded by the analogous divisibility cases; in the last value one possible case instead forces both $x$ and $y$ to be even. Thus this obstruction concerns the differences $x,y$, not a common factor of two basis elements considered in isolation.

Matching constructions. Four families supply the lower bounds. Each family has three distinct elements, contains a negative integer, and covers an entire initial interval by exactly $h$ summands.

If $h\equiv9\pmod{12}$, write $m=6r+4$ and $h=12r+9$. The basis $$A_0=\{-(2r+2),\ 2r+2,\ 4r+5\}$$ satisfies $N-1\le n_h(A_0)$ by postage_stamp_basis_range_neg_ge_of_mod_twelve_eq_nine. Here $N-1=36r^2+72r+33$. Its representation proof divides each target $n$ by $2r+2$, then adjusts the coefficient of $4r+5$ by multiples of $2r+2$. The remaining sum is made from the opposite elements $\pm(2r+2)$; bounds and parity ensure that their two multiplicities are nonnegative integers with the required total. Combining this coverage with the universal deficit-one upper bound gives equality for this residue class.

Now suppose $h\not\equiv9,11\pmod{12}$. The upper bound is $n_h(A)+2\le N$. If $m\equiv2\pmod3$, then $m\not\equiv5\pmod6$, so $m=6r+2$ and $h=12r+5$. Use $$A_0=\{-(2r+1),\ 2r+1,\ 4r+4\}.$$ The statement postage_stamp_number_neg_two_of_odd_family_e proves coverage through $36r^2+48r+12$. Direct expansion gives $N=36r^2+48r+14$, so the covered endpoint is $N-2$. As in the preceding family, the representation proof tracks the multiplicities of the opposite pair and the third element, including their parity constraints.

If instead $m\not\equiv2\pmod3$, then $m\ge3$ and the basis $$A_0=\{-1,2,m\}$$ is available. The statement postage_stamp_number_neg_two_of_odd_family_1 proves coverage through $m^2+4m=N-2$. Its arithmetic can be organized as follows. Write $n+h=(m+1)q+\rho$, where $0\le\rho<m+1$. Choose $j\in\{0,1,2\}$ so that $\rho+j(m+1)$ is divisible by 3; this is possible because $m+1$ is coprime to 3. Set $$s=\frac{\rho+j(m+1)}3,\qquad t=q-j.$$ Then $n=-h+3s+(m+1)t$. The formal proof uses the endpoint bound on $n$ to verify $t\ge0$ and $s+t\le h$ in every residue case. Thus $h-s-t,s,t$ are the required multiplicities of $-1,2,m$.

Finally suppose $h\equiv11\pmod{12}$ and $h\not\equiv59\pmod{60}$. Then $m\equiv5\pmod6$, $m\ge5$, and $m\not\equiv4\pmod5$. Take $$A_0=\{-2,3,m-1\}.$$ The statement postage_stamp_number_neg_two_of_odd_family_2 proves coverage through $m^2+4m-1=N-3$. This time write $n+2h=(m+1)q+\rho$ and choose $j\in\{0,1,2,3,4\}$ with $5\mid\rho+j(m+1)$. Such a choice exists because $m+1$ is coprime to 5. The counts $s=(\rho+j(m+1))/5$ and $t=q-j$ satisfy $n=-2h+5s+(m+1)t$; the proof checks their nonnegativity and the bound $s+t\le h$. The upper bound for this congruence class is $n_h(A)+3\le N$, so it matches the construction.

Passing to the extremal number. The coverage statements imply the asserted lower bounds on basis ranges by postage_stamp_number_neg_two_of_odd_range_ge. Its boundedness hypothesis is supplied by the largest element of each displayed finite basis. For each gap $g=1,2,3$, the lemma postage_stamp_number_neg_two_of_odd_sandwich combines a universal inequality $n_h(A)+g\le N$ with one admissible witness satisfying $N\le n_h(A_0)+g$. The witness makes the set of ranges nonempty, and the universal bound makes it bounded above. Its supremum therefore satisfies $n^{\flat}_h(2)+g=N$. Applying this argument in the cases above proves Theorem 1.

For Theorem 2, $h\equiv59\pmod{60}$ means $m\equiv29\pmod{30}$. The deficit-four upper bound applies to every admissible basis. The set of ranges is nonempty, witnessed for example by $\{-1,0,1\}$, and bounded above by $N-4$. Taking its supremum gives $n^{\flat}_h(2)+4\le N$. There is no matching construction asserted for this exceptional class.

5. Discussion

The exact formulas refine the strict comparison in Theorem 4.1 of arXiv:2610.19470. For odd $h\ge5$, the deficit is 1 in the class $h\equiv9\pmod{12}$ and 2 in the classes $h\equiv1,3,5,7\pmod{12}$. In the remaining odd class $h\equiv11\pmod{12}$, it is 3 on four of its five subclasses modulo 60 and at least 4 on the fifth. Both the upper bounds and the constructions are uniform in their parameters.

The exceptional progression $h\equiv59\pmod{60}$ has an arithmetic explanation. The narrow interval for $ha$ leaves only a few possible differences $x,y$ at range $N-3$. The congruences force either a nontrivial common divisor of those differences or an impossible divisibility condition. This rules out that range, but supplies no basis attaining $N-4$. Theorem 2 is therefore an upper bound rather than an exact evaluation.

Determining the exact deficit throughout this exceptional progression remains outside the present results. In particular, the theorems do not establish whether the deficit is bounded independently of $h$. The lower constructions show why the congruences modulo 3 and 5 arise: they permit adjustment of the multiplicities without changing the represented integer, while keeping the total number of summands fixed.

Even orders are already treated in arXiv:2610.19470. Its Theorems 3.3 and 3.4 establish equality $n^{\flat}_h(2)=n_h(2)$ for every positive even $h\ne4$, and Theorem 3.2 gives $n^{\flat}_4(2)=8<n_4(2)=10$. Thus the restriction to odd orders here addresses the part where the source provides a strict comparison without a general exact deficit formula. The classical expression $n_h(2)=\lfloor(h^2+6h+1)/4\rfloor$ itself applies to both parities.

These results concern three-element bases. They do not determine the comparison for larger bases, and the proof makes essential use of reducing a three-element basis to two coprime positive differences. Extending that analysis would require additional arguments beyond the statements proved here.

Why it is research-level

  • Determines n♭_h(2) exactly for all odd h ≥ 5 except h ≡ 59 (mod 60), where arXiv:2610.19470 only shows n♭_h(2) < n_h(2): the gap n_h(2) - n♭_h(2) is 1 iff h ≡ 9 (mod 12), 2 for h ≡ 1, 3, 5, 7 (mod 12) and 3 for h ≡ 11 (mod 12); for h ≡ 59 (mod 60) it is at least 4, and it is at least 6 at h = 419
  • a new question answered: For h ≡ 59 (mod 60) the gap is at least 4: at range n_h(2) - 3 the Theorem 4.1 inequalities leave only sets with gcd(x, y) > 1 or a divisibility contradiction.

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.