3. The extremal Frobenius problem

Chapter 3 is devoted to be investigation of $G(A)$ and $g(n, t)$. The determination of the geatest non-representable number, $G(A)$, seems to be a very difficult task already in the case $n=3$. The exact values can be given only under special conditions, for which we show several examples in Chapter 2. Maybe, just these difficulties induced that the evolution of the topic brought the various estimations into the center of interest. In fact, in connection with these estimations ERDŐS introduced and began to study the extremal function $g(n, t)$ in 1971. Since our main result is related to this function, we give a complete survey of the previous investigations about $g(n, t)$.

Particularly we stress DIXMIER's estimate from 1990 [4]:

THEOREM 3.1.3.

$$\left\lfloor\frac{t-2}{n-1}\right\rfloor(t-n+1)-1 \le g(n, t) \le \left(\left\lceil\frac{t-1}{n-1}\right\rceil-1\right)t-1.$$

DIXMIER gave an even sharper upper bound, which has many consequences and implies nearly all previously known results.

THEOREM 3.2.5.

$$g(n, t) \le (v-1)(t-r-1)-1,$$    where $$t-1=v(n-1)-r$$    and $$0 \le r < n-1.$$

The exact results on $g(n, t)$ can be divided into two larger groups. For the smaller values of $n$, the case $n=2$ has been known long since, and later LEWIN gave the exact value for $n=3$ in the early 70-es. The cases $n=4$ and $n=5$ follow from Dixmier's theorems [4], except for the numbers $t=4k+3$ and $n=5$. For larger values of $n$ one could obtain exact values only if $t$ was not much greater than $n$. The most general result of this type was the theorem of ERDŐS and GRAHAM from 1972 [6]:

THEOREM 3.2.3. Let $n$ and $k$ be positive integers, $n \ge 9k^2+15k+2,$ then

$$g(n, 2n+k)= \left\{ \begin{gathered}2n+4k+1,\text{ } \text{ if } ... ...\\ 2n+4k-1, \text{ }\text{ if } n-k \equiv 1 \pmod{3}. \end{gathered} \right.$$

LEV gave a different proof for this theorem, with the weaker assumption $k \le {n-2}$. Our main result is a generalization of this theorem, determining the exact value of $g(n, dn+k)$ for two residue classes mod $(d+1)$ [16]:

THEOREM 3.3.1. Let $d, n, k$ be integers such that $2 \le d < n,$    $0 \le k \le n-d.$ If $n-k \equiv 0 \pmod {d+1}$    or $n-k\ \equiv -1 \pmod {d+1}$ then

$$g(n, dn+k)=d(d-1)n+2dk+d^2-d-1.$$

Using our theorem we can compute $g(n, t)$ also in some further special cases, for instance

COROLLARY 3.4.2. Let $n$ and $k$ be integers such that $n > 3$, $0 \le k \le n-3.$ If $n-k \equiv 0 \pmod {4}$$\text { or } n-k \equiv -1 \pmod {4}$ then

$$g(n, 3n+k)= 6n+6k+5.$$