postage_stamp_basis_range
def
n_h(A): the largest n such that every integer in [0, n] belongs to hA (A is an h-basis for n).
Statement
noncomputable def postage_stamp_basis_range (h : ℕ) (A : Finset ℤ) : ℕ
- Defined in
- arXiv:2610.19470 (Positivity and negativity for h-bases for n), Sec. 1 (n_h(A)).
- Verified
- 17 Oct 2026
- Axioms
- none listed
- Built on 1
- int_mem_h_fold_sumsetm belongs to the h-fold sumset hA: m is a sum of exactly h, not necessarily distinct, elements of A.
- Used by 27
- postage_stamp_number_negn♭_h(k): the largest n_h(A) over sets A of k + 1 integers containing at least one negative integer.
- postage_stamp_number_neg_two_of_odd_upper_threeFor odd h ≥ 5 with h ≡ 11 (mod 12), every 3-element set with a negative element has h-range at most n_h(2) - 3.
- postage_stamp_number_neg_two_add_one_eq_iffFor odd h ≥ 5, the negative-allowed three-stamp number misses n_h(2) = ⌊(h²+6h+1)/4⌋ by exactly one, n♭_h(2) = n_h(2) - 1, if and only if…
- postage_stamp_basis_range_eight_neg_four_one_thirteen_fourteenThe set A = {−4, 1, 13, 14} is an 8-basis for 99: every integer in [0, 99] is a sum of exactly 8 elements of A, so n_8(A) ≥ 99.
- postage_stamp_basis_range_ge_of_mod_four_eq_twoFor h = 4w − 2 (w ≥ 1), the set A = {−w, w, w + 1} satisfies n_h(A) ≥ (w + 1)h = (h² + 6h)/4.
- postage_stamp_basis_range_one_zero_one_twoSanity check: with h = 1, A = {0, 1, 2} covers exactly [0, 2], so n_1(A) = 2.
- postage_stamp_number_neg_two_add_four_le_of_mod_sixty_eqFor odd h ≥ 5 with h ≡ 59 (mod 60), n♭_h(2) ≤ n_h(2) - 4, where n_h(2) = ⌊(h²+6h+1)/4⌋.
- postage_stamp_number_neg_three_eight_gen♭_8(3) ≥ 99: some 4-element set of integers with a negative element is an 8-basis for 99 (namely {−4, 1, 13, 14}).
- postage_stamp_number_neg_two_of_odd_range_geIf A is bounded above and h-fold covers [0, R], its h-range is at least R.
- postage_stamp_basis_range_add_one_le_of_neg_of_oddFor odd h ≥ 1, every 3-element set A of integers containing a negative integer has h-range n_h(A) < ⌊(h² + 6h + 1)/4⌋ = n_h(2); hence…
- postage_stamp_number_neg_four_one_nine_two_add_six_leFor h = 419 (h ≡ 59 mod 60), the negative-allowed three-stamp number satisfies n♭_h(2) ≤ n_h(2) - 6, where n_h(2) = ⌊(h²+6h+1)/4⌋ = 44519.…
- postage_stamp_basis_range_zero_one_ge_of_mod_four_eq_zeroFor h = 4w (w ≥ 1), the basis {0, 1, 2w + 1} = {0, 1, (h+2)/2} has h-range at least w(4w + 6) = (h² + 6h)/4: every integer in [0, w(4w+6)]…
- postage_stamp_number_neg_two_of_odd_range_ltIf a set does not h-fold cover [0, R] (R > 0), its h-range is less than R.
- postage_stamp_number_three_eight_eqThe classical postage stamp number with four stamps (one of them 0) and h = 8: n_8(3) = 89, attained by {0, 1, 9, 14}.
- postage_stamp_number_neg_two_eq_of_mod_four_eq_twoIf h ≥ 2 and h ≡ 2 (mod 4), then n♭_h(2) = n_h(2) = (h² + 6h)/4.
- postage_stamp_numberThe postage stamp number n_h(k): the largest n_h(A) over sets A of k + 1 nonnegative integers.
- postage_stamp_basis_range_neg_ge_of_mod_twelve_eq_nineFor h = 12r + 9, the set {-(2r+2), 2r+2, 4r+5} (which contains a negative integer) has h-range at least ⌊(h²+6h+1)/4⌋ - 1 = n_h(2) - 1.
- postage_stamp_number_three_eight_lt_negWith four stamps and h = 8, allowing a negative denomination strictly helps: n_8(3) = 89 < 99 ≤ n♭_8(3). (For three stamps the opposite…
- postage_stamp_basis_range_succ_le_card_powIf A is a nonempty finite set of integers, n_h(A) + 1 ≤ |A|^h: the integers 0, ..., n_h(A) are distinct elements of hA, which has at most…
- postage_stamp_number_neg_two_of_odd_sandwichIf every 3-set with a negative element has h-range ≤ n_h(2) - g and one such set reaches n_h(2) - g, then n♭_h(2) + g = n_h(2).
- postage_stamp_basis_range_zero_one_ge_of_mod_four_eq_twoFor h = 4w - 2 (w ≥ 1), the basis {0, 1, 2w} = {0, 1, (h+2)/2} has h-range at least (w+1)h = (h² + 6h)/4: every integer in [0, (w+1)h] is…
- postage_stamp_number_neg_two_of_odd_upper_fourFor odd h ≥ 5 with h ≡ 59 (mod 60), every 3-element set with a negative element has h-range at most n_h(2) - 4.
- postage_stamp_basis_range_add_two_le_of_neg_of_oddFor odd h ≥ 5 with h ≢ 9 (mod 12), every 3-element set of integers containing a negative integer has h-range at most n_h(2) - 2 =…
- postage_stamp_basis_range_zero_one_ge_of_oddFor odd h = 2m + 1, Stöhr's extremal basis {0, 1, (h+3)/2} = {0, 1, m+2} has h-range at least m² + 4m + 2 = (h² + 6h + 1)/4: every integer…
- postage_stamp_basis_range_ge_of_mod_four_eq_zeroFor h = 4w with w ≥ 2, the set A = {−(w − 1), w, w + 2} satisfies n_h(A) ≥ w(4w + 6) = (h² + 6h)/4.
- postage_stamp_number_two_eqThe classical postage stamp number for three stamps: n_h(2) = ⌊(h² + 6h + 1)/4⌋ for every h ≥ 1.
- postage_stamp_number_neg_two_of_odd_of_mod_sixty_neExact value of the negative-allowed three-stamp number for odd h ≥ 5 with h ≢ 59 (mod 60): n_h(2) - n♭_h(2) = 1 if h ≡ 9 (mod 12), 2 if h…
Lean source view module on GitHub
/-- `n_h(A)`: the largest `n` with `[0, n] ⊆ hA`. The set of such `n` is bounded since `hA` is finite; it is `0` (not `-1`) when `0 ∉ hA`, which only matters for sets that are no basis at all. -/ noncomputable def postage_stamp_basis_range (h : ℕ) (A : Finset ℤ) : ℕ := sSup {n : ℕ | ∀ m : ℕ, m ≤ n → int_mem_h_fold_sumset h A m}