0
$\begingroup$

Given $a,b\in\Bbb N$ we know from http://www.emis.ams.org/journals/INTEGERS/papers/i33/i33.pdf that the smallest number that cannot be written as a non-negative linear combination of integers with weights $a^ib^j$ can be explicitly given when $i+j$ is fixed and $i,j\in\Bbb N\cup\{0\}$.

Sylvester gave that $ax+by$ cannot represent exactly $(a-1)(b-1)$ different positive integers.

What would be analog of Sylvesters result for general weighted linear combinations of non-negative numbers with weights $a^ib^j$ where $i+j$ is fixed where $a,b\in\Bbb N$ and $i,j\in\Bbb N\cup\{0\}$ holds?

$\endgroup$
9
  • 1
    $\begingroup$ I cannot understand the question. What is the difference between "can be written" and "can be explicitly written"? What is a "non-negative linear combination of integers with weights $a^ib^j$ where $i+j$ is fixed and $i,j\in N∪\{0\}$ can be explicitly given"? $\endgroup$
    – Seva
    Jul 3, 2016 at 7:41
  • $\begingroup$ @seva If $i+j=1$ then we have Sylvester's classic result on Frobenius problem. $\endgroup$
    – Turbo
    Jul 3, 2016 at 8:52
  • $\begingroup$ @seva there is no diff. $\endgroup$
    – Turbo
    Jul 3, 2016 at 11:59
  • 1
    $\begingroup$ I think the question for $i+j=2$ is something like the following: Given positive coprime integers $a$ and $b$, how many positive integers cannot be made using coins with values $a^2$, $ab$ and $b^2$? The link is perhaps to some reference for the largest value that can't be made. $\endgroup$
    – znt
    Jul 3, 2016 at 12:25
  • $\begingroup$ For $i+j=2$ and $a=2$, both the largest elements and counts of the numbers not expressible as $4x+2by+b^2z$ appear to be polynomials, $(b+1)^2-5$ and $\frac{1}{2}(b+1)^2-2$. $\endgroup$ Jul 3, 2016 at 15:02

1 Answer 1

1
$\begingroup$

Consider $i+j=2$, and consider a representation with $x,y,z$ whole numbers of $n = xa^2 + yab +zb^2$. Note that we can restrict $x$ and $z$ to be less than $b$ and $a$ respectively, as we can find an alternate representation using a multiple of $ab$ to replace one with larger $x$ or $z$. Thus the largest number which can't be represented is $(b-1)a^2 + (a-1)b^2 -ab$, which should be contrasted with $a^2b^2 - a^2 - b^2$ just using a nonnegative linear integral combination of $a^2$ and $b^2$ alone.

Now suppose we have $k\geq 2$ and a polynomial $P_k(a,b)$ which represents the largest integer not represented with a nonnegative linear integral combination of the $k+1$ numbers $a^k$ through to $b^k$. To consider the quantity $P_{k+1}(a,b)$ coming from representations using the $k+2$ numbers $a^{k+1}$ through $b^{k+1}$, note that we can use the last $k+1$ terms to represent $Mb$ for all integers $M$ greater than $P_k(a,b)$. Also, as before, any representation which has $xa^{k+1}$ as a term can be replaced by one where $x\lt b$. This leads as before to $P_{k+1}(a,b) = a^{k+1}(b-1) + bP_k(a,b)$.

EDIT 2016.07.04 A remark on the Sylvester number is requested. For a given $k$, note that any representable $n$ by $xa^k + ya^{k-1}b + \cdots + zb^k$ has such a representation where all the coefficients $y$ through $z$ are at least $0$ and less than $a$, as shown above. If $x$ is allowed to be negative, then any integer has such a representation with $0 \leq y, \cdots, z \lt a$. In particular, the largest nonrepresentable integer is $N= -a^k + (a-1)(a^{k-1}b + \cdots + b^k)$. Now pick an integer $m$ greater than 0 which is not representable, and write it as above with a negative value for $x$. Then $N-m$ is representable, just by considering the coefficients. This leads to a bijection on the interval $[0, P_k(a,b)]$ between representable and non representable integers. Thus the desired count is $(1+P_k(a,b))/2$. END EDIT 2016.07.04.

Gerhard "Induction Is A Time Saver" Paseman, 2016.07.03.

$\endgroup$
8
  • $\begingroup$ Gee, I could have used $k=1$ as a base case. Oh well. Gerhard "Can Hindsight Come Without Regret?" Paseman, 2016.07.03. $\endgroup$ Jul 4, 2016 at 0:21
  • $\begingroup$ What does $k$ refer to here? Also I think you solve Frobenius problem here and not Sylvester's problem as requested. $\endgroup$
    – Turbo
    Jul 4, 2016 at 0:51
  • $\begingroup$ $k$ is what it says. It is also the sum of the powers, I.e. $k=i+j$. I suspect the answer to Sylvester's question is $P_k(a,b)/2$. You might try an argument similar to above to prove such a result. Gerhard "Prefers To Suggest Than Direct" Paseman, 2016.07.03. $\endgroup$ Jul 4, 2016 at 0:58
  • $\begingroup$ "suspect not accountable until proven" Turbo, 07/03/2016. $\endgroup$
    – Turbo
    Jul 4, 2016 at 1:07
  • $\begingroup$ For the traditional problem with $a$ and $b$, there is a duality between representable and non representable numbers between 0 and $(a-1)(b-1) - 1=N$. I think if $c$ is representable, then $N-c$ is not. I believe the same (or a similar) duality exists for this problem, and that the answer is $(P_k(a,b) + 1)/2$. Gerhard "Hopes To Inspire Other Work" Paseman, 2016.07.03. $\endgroup$ Jul 4, 2016 at 5:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.