Contradiction in Frobenius coin problem

142 Views Asked by At

The Frobenius coin problem guarantees that if $(a,b)=1$, then $$ax+by$$ does not represent exactly $(a-1)(b-1)/2$ numbers all below $ab-a-b$ if $x,y\geq0$ holds.

I am confused by following argument.

Assume $a,b\in[n+1,2n]$ with $(a,b)=1$.

Then $(n+1)^2-2(n+1)<ab-a-b<4n^2-4n\implies ab-a-b\approx cn^2$ for some $c>1$ and $(a-1)(b-1)/2\approx dn^2$ for some $d>1/2$ holds.

Then if $m<ab-a-b$ and is given by $ax+by=m$ then $x,y<4n$ holds.

Let $a<b$ and since $(2a+b)-(a+b)=a$, difference between any two representable numbers is atleast $n$.

Since $ab-a-b\approx cn^2$ and $(a-1)(b-1)/2\approx dn^2$, then number representable numbers below $g(a,b)$ is $(c-d)n^2$.

However if gap is atleast $n$, number of representable numbers below $g(a,b)$ is only $g(a,b)/n\approx cn$.

Since $$cn\ll (c-d)n^2$$ this seems to lead to a contradiction.


Above contradiction can be resolved since smaller numbers are more non-representable than numbers close to $g(a,b)$. I am looking for precise statistics of these tradeoffs so that we get the $(a-1)(b-1)/2$ estimation.