THE LARGEST AMOUNT YOU CAN'T PAY, NOW TIGHTLY BOUNDED

Imagine a till that accepts only a few kinds of coins, in unlimited supply, and never gives change. Some amounts can be paid exactly; others never can. Mathematicians call the coin values generators, and ask a deceptively simple question: what is the largest amount that cannot be paid?

Amounts that can never be paid

Take whole numbers a₁ < a₂ < … < aₙ with no factor shared by all of them. A total obtained by adding these numbers, each as many times as you like, is “representable”. Only finitely many whole numbers are not; the largest is the Frobenius number, F. (If one of the values is 1, everything can be paid and F is set to −1.)

A small example: with coins of 3, 4 and 6, you can pay 3, 4, 6, 7, 8 and every amount after that, but never 1, 2 or 5. So F = 5. Note that 3 and 6 share a factor; what matters is that no factor is common to all three.

For two coins there is an exact answer, Sylvester’s formula: F(a₁, a₂) = a₁a₂ − a₁ − a₂. For three or more, the work consists of bounding F: proving it cannot exceed some value computed from the coins.

A stubborn factor of 2

Paul Erdős and Ronald Graham proved, for three or more generators:

F ≤ 2aₙ₋₁⌊aₙ/n⌋ − aₙ

Here aₙ is the largest value, aₙ₋₁ the second largest, n the number of values, and ⌊ ⌋ means rounding down. Like Sylvester’s formula, it involves the two largest coins.

They also estimated the worst case, the largest F possible when all n values are at most t. The gap between their estimates, roughly a factor of 2, led to a conjecture recorded as Erdős Problem #433. Jacques Dixmier resolved it, and also proved a simpler bound valid for every set: F ≤ aₙ²/(n − 1). The factor 2 is gone, but so is the second-largest coin.

Keeping both largest coins

Lin Chen, Tingwei Hu, Yuchen Mao and Guochuan Zhang, of the College of Computer Science and Technology at Zhejiang University, wanted both: no factor 2, and the second-largest coin kept. Their answer, valid for any set of two or more values:

F ≤ aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ − 1

Here ⌈ ⌉ means rounding up. Compared with Erdős and Graham, the factor 2 has disappeared, at the price of dividing by n − 1 instead of n and rounding up. Compared with Dixmier, the new bound can be substantially smaller when the second-largest coin is small next to the largest one.

On the 3, 4, 6 example, Erdős and Graham’s bound gives 10, Dixmier’s gives 18, and the new one gives 4 × 3 − 6 − 1 = 5, exactly the true value. No surprise: this set belongs to the family of extreme cases described below, built to reach the bound exactly; the paper gives no comparison on typical sets.

Sorting amounts by remainder

The proof follows Erdős and Graham’s route. Sort every amount by its remainder after division by the largest coin, aₙ. Once a sum of the smaller coins reaches a given remainder, adding copies of aₙ reaches every larger amount with that remainder. The task is to show that every remainder can be reached cheaply.

The key tool is Kneser’s theorem, on how large a set of sums must be. Erdős and Graham used it to show that sums of about aₙ/n coins cover more than half of the remainders, then doubled up to cover them all. Each coin in these sums is worth at most aₙ₋₁, so doubling the number of coins doubles the cost: hence the factor 2.

The new proof uses sums of ⌈aₙ/(n − 1)⌉ coins. When these sums miss some remainders, Kneser’s theorem says the missing ones are not scattered at random: they form whole families of remainders spaced at regular intervals. The more families are missing, the more of the smaller coins must crowd into each family that is reached, so each of those families contains some small coins, and the few extra coins needed to reach the missing families are cheap. The total never exceeds ⌈aₙ/(n − 1)⌉ × aₙ₋₁.

That first step gives the bound without its final “− 1”. The last unit comes from a separate argument, based on a theorem of Scherk and Kemperman about sums that can be formed in only one way: it shows that the borderline amount aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ can itself always be paid. According to the acknowledgements, the authors first proved the weaker bound; GPT-6 then helped find the argument that lowers it by one, and also assisted with the proof that the bound cannot be lowered and with editing the English. The authors state that they take responsibility for the final manuscript.

Cases that hit the limit exactly

This bound cannot be lowered: for every n ≥ 3, the authors build infinitely many sets where F equals it exactly. Take any q ≥ 2 and the values q, 2q, …, (n − 1)q, plus (n − 2)q + 1. All but one are multiples of q, so they pay nothing that q alone cannot. The set behaves like two coins, q and (n − 2)q + 1, and Sylvester’s formula gives an F that matches the new bound exactly. With n = 3 and q = 3, this recipe produces precisely the 3, 4, 6 example above.

Fewer coins, a lower ceiling

The bound can also be read in terms of density. It applies to any reduced set made of the i smallest values plus the largest, as long as those still share no common factor. Removing coins can only make paying harder, so a ceiling proved for the reduced set also holds for the full one. What controls the result is roughly aᵢ/i, the inverse of how densely the first i values fill the numbers from 1 to aᵢ: the densest group wins. In particular, the authors note, the second-largest coin can simply be set aside whenever the remaining coins still have no factor common to all of them.

The paper stays purely theoretical: it gives no number for how much smaller the new bound is on typical sets of coins, and its sharpness is proved only for three coin values or more.