next up previous
Next: 5. Summation of the non-representable Up: index Previous: 3. The extremal Frobenius problem

4. The number of the non-representable numbers

Both representable and non-representable numbers occur up to the
greatest non-representable number, so it is a natural question, what is the exact number of these. Already SYLVESTER studied and solved this problem for two coins [30]. The Norwegian mathematician, SELMER showed that $ N(a_1, a_2, \ldots , a_n)$ can be computed in all cases, when we know the greatest non-representable number in the every residue class mod $ a_1$ [28]. Let $ H$ be a complete residue system mod $ a_1.$ To every $ h \in H$ there exists an $ r_h \equiv h \pmod {a_1}$, which is representable as $ r_h=a_2y_2 + a_3y_3 + \ldots + a_ny_n$ and is the minimal with this property. Then by this notation:

4.1.2. THEOREM

$\displaystyle N(a_1, a_2, \ldots ,a_n)=\frac {1}{a_1}
\sum_{h \in H} {r_h} -\frac {a_1-1}{2}.

We present several examples in Chapter 2 for the practical application of this method, and we use the same idea also at the summation of the non-representable numbers in Chapter 5.

We give a short survey about the special results and estimates related to $ N(A)$. About the relation of the two functions we have:

$\displaystyle \frac{G(a_1, a_2, \ldots , a_n)+1}{2} \le N(a_1, a_2, \ldots , a_n)
\le G(a_1, a_2, \ldots , a_n),

and these inequalities cannot be improved.

As the main result of this chapter we prove that the extremal number $ \nu(n, t)$ is obtained when we choose the $ n$ largest integers not exceeding $ t$ [17]. This was a conjecture by ERDŐS and GRAHAM from 1980 [7, p.86].

THEOREM 4.2.1. Let $ n$ and $ t$ be positive integers, $ 1 < n \le t.$ Then

$\displaystyle \nu(n,t)=N(t-n+1,t-n+2, \dots , t).

We also prove that for infinitely many values of $ n$ and $ t$, the extremal value $ \nu(n, t)$ is achieved also for another set $ A$ differing from the set of the greatest $ n$ numbers up to $ t$.

THEOREM 4.2.4. Let $ d, n, k$ be integers such that  $ 2 \le d < n,$ $ 0 \le k < n-d.$ If $ n-k \equiv 0 \pmod {d+1}$ or $ n-k\ \equiv -1 \pmod {d+1}$ then for $ t=dn+k$ there exist at least two optimal sets $ A$, i.e. for which

$\displaystyle N(A)=\nu(n,dn+k).$

It is an interesting duality, that for these values of $ n$ and $ t$, the value $ G(a_1, a_2, \ldots , a_n)$ will be smaller in general than $ g(n, t)$, when we choose the $ a_i$ as adjacent numbers according to the original conjecture, yet we get the most non-representable numbers. The number of the non-representable numbers, however, will be just the same also for the set giving the maximal $ G(A)$.

We do not know, whether there exists at least another optimal set for every $ t$ besides the construction of the adjacent elements, and whether there exist other types of optimal sets differing from the above-mentioned ones.

next up previous
Next: 5. Summation of the non-representable Up: index Previous: 3. The extremal Frobenius problem
root 2004-12-04