3
$\begingroup$

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

Assume $m\in[0,ab-a-b]$ and assume $\max\big(\frac a b,\frac ba\big)<2$.

Approximately what fraction of numbers less than $m$ is represented by $ax+by$? In other words what is a good point-wise approximation to the function $$f_{a,b}(m)=\big|\{n\in\Bbb N_{\leq m}:\exists x,y\in\Bbb N_{\leq\min(a,b)}\cup\{0\}\mbox{ }\mathsf{ with }\mbox{ }ax+by=n\}\big|?$$

For instance, I am looking for an approximation that will explain the fact that every integer $m\in[1,\min(a,b)]$ is not represented. There seems to be more smaller non-representable numbers than larger ones. It seems lower the $m$, there are more non-representable numbers and there should be comparatively more representable numbers close to $g(a,b)$ to get upto half the numbers to be representable. What exactly is this distribution?

Improve this question
$\endgroup$
5
  • $\begingroup$ Why do you think the difference between any two representable numbers is at least $n$? Such a difference is an integral linear combination of $a$ and $b$, which surely can be much smaller than $n$, in fact it can be as small as $(a,b)$ by Euclid's algorithm. At any rate, this question does not seem to be appropriate here. $\endgroup$
    – GH from MO
    Commented Nov 28, 2015 at 2:50
  • $\begingroup$ If you look at my end comment I am saying the gap can be as small as $1$ if number is large enough or less $g(a,b)$ will be infinity. My problem is about how the statistics change as the numbers increase. $\endgroup$
    – Turbo
    Commented Nov 28, 2015 at 4:59
  • 1
    $\begingroup$ Your reformulated question is much better than the original one. $\endgroup$
    – GH from MO
    Commented Nov 28, 2015 at 22:17
  • $\begingroup$ What is the purpose of the assumption that $a/b,b/a \lt 2$? $\endgroup$
    – Douglas Zare
    Commented Nov 28, 2015 at 23:16
  • $\begingroup$ @DouglasZare they are nor far apart $a=3$, $b=10^9$ not allowed. $\endgroup$
    – Turbo
    Commented Nov 29, 2015 at 0:22

1 Answer 1

Reset to default
2
$\begingroup$

The smallest number with two representations is $ab$, so in the range you're talking about, all representations are unique. You're looking for the number of solutions to $ax+by\le m$ with $x,y\ge 0$; this is the number of integer points in the triangle formed by the intersection of the three half-planes $x\ge 0$, $y\ge 0$, and $ax+by\le m$. Up to low-order terms (which your assumption that $a$ and $b$ are near each other makes insignificant, $O(\sqrt m)$) it will be approximately the same as the area of this triangle, which (as a right triangle with sides $m/a$ and $m/b$) is $$\frac{1}{2}\cdot\frac{m}{a}\cdot\frac{m}{b}=\frac{m^2}{2ab}.$$ This is the number of representable points; the fraction of representable numbers is therefore approximately $$\frac{m}{2ab}.$$

Improve this answer
$\endgroup$
9
  • $\begingroup$ I think this works only if $m$ is sufficiently big right (say $\sqrt[i]{ab}$ at some $i\geq2$)? There seems more non-representable integers when $m$ is small (infact first consecutive $\min(a,b)-1$ non-zero integers are non-representable). $\endgroup$
    – Turbo
    Commented Nov 29, 2015 at 2:05
  • $\begingroup$ The error term in the number of solutions is $O(\sqrt m)$, and in the fraction of representable numbers is $O(1/\sqrt m)$. So that should tell you how big you need to make $m$ for whatever accuracy you want. $\endgroup$
    – David Eppstein
    Commented Nov 29, 2015 at 2:07
  • $\begingroup$ Actually since $c\sqrt{m}$ is error term, upto constant factor $m>c'ab$ for some $c,c'>0$. Actually I am not sure how to interpret error terms in these kind of calculations. Could you please add a line or two? my first guess is $m>ab$ but since $\min(a,b)<\sqrt{ab}$ I am not completely certain whether I am right and/or the triangle area trick is sufficient. $m>c'ab$ seems too high for anything more subtle like non-representability of $\min(a,b)-1$ initial integers. $\endgroup$
    – Turbo
    Commented Nov 29, 2015 at 2:29
  • $\begingroup$ Sorry, that was sloppy of me. Error term is square root of triangle area, not of m. $\endgroup$
    – David Eppstein
    Commented Nov 29, 2015 at 2:47
  • $\begingroup$ That then does not give any effective bound on $m$. $\endgroup$
    – Turbo
    Commented Nov 29, 2015 at 2:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .