Positivity and negativity for $h$-bases for $n$

Abstract

A set $A$ of integers is an $h$-basis for $n$ if every integer in $[0,n]=\{0,1,2,\dots ,n\}$ belongs to the sumset $hA$, that is, can be represented as the sum of exactly $h$ not necessarily distinct elements of $A$. The classical postage stamp problem asks for the largest integer $n_h(k)$ such that $[0,n_h(k)]\subseteq hA$ for some set $A$ of nonnegative integers of size $k+1$. We consider the effect of allowing negative elements. Let $n_h^{♭}(k)$ be the largest integer such that $[0,n_h^{♭}(k)]\subseteq hA$ for some set $A$ of integers of size $k+1$ containing at least one negative integer. For $k=2$, we have $n_h^{♭}(2)<n_h(2)$ if $h$ is odd or $h=4$ and $n_h^{♭}(2)=n_h(2)$ if $h$ is even and $h\ne 4$. Proofs of these comparison results were autonomously discovered and formally verified in Lean by https://aristotle.harmonic.fun/}{Aristotle}, a formal reasoning agent developed by https://www.harmonic.fun/}{Harmonic}. In this paper we give new proofs of these results.

arXiv comment11 pages