Krdytkyu

I was reading about the Coin-problem and I am unable to fully understand the following argument:

On the other hand, whenever the GCD equals 1, the set of integers that cannot be expressed as a conical combination of ${ a_1, a_2, …, a_n }$ is bounded according to Schur's theorem, and therefore the Frobenius number exists.

Here the author is arguing for the existence of a non-negative solution to the linear Diophantine equation (LDE)
$$sum_{i=1}^{k}a_ix_i =n text{}$$
for large enough $n.$ Now I tried to understand the proof of the Schur theorem here enter link description here (Page 98), but I am not sure that I understand it fully. In particular, I don't understand why the generating function associated with the sequence $h_n$ that counts the number of solutions to the LDE is
$$H(x)= prod_{i=1}^{k}left(frac{1}{1-x^{a_i}}right).$$

Once we have $H(x)$ we can deduce that
$$h_nsim frac{n^{k−1}}{(k − 1)!a_1a_2 ··· a_k}$$
as $nto infty.$ How does this exactly show that for large enough $n,$ $h_n>0?$ Is it because the $frac{n^{k−1}}{(k − 1)!a_1a_2 ··· a_k}>0?$

A simple approach to the title:

Thanks to Bezout, there is some (not necessarily) integer combination of the $a_i$s that makes $1$. Add a large enough multiple of $a_1$ to each coefficient to make it non-negative and call the sum $k$; we have $kequiv 1 pmod{a_1}$.

Now any number $ge ka_1$ is a non-negative combination of the $a_i$s. Namely, let $n$ be the desired number, and let $m=nbmod a_1$. Then $mk$ is a positive combination, and we can add some multiple of $a_1$ to make it $n$ instead, since $mkequiv npmod{a_1}$ and $mk<n$ because $m<a_1$.

We first do this for $k =2$.

LEt us assume WLOG that $a_1 < a_2$. If gcd$(a_1,a_2)=1$ then $a_2 mod a_1 in left(mathbb{Z}/a_1 mathbb{Z}right)^{times}$. So there exists a multiplicative inverse $m_2 in left(mathbb{Z}/a_1 mathbb{Z}right)^{times}$ of $a_2$; or equivalently, there exists a nonegative integer $m_2 < a_1$ such that $m_2 times a_2 equiv_{a_1} 1$. This implies the following: There exists integers $m_2$ and $m_1$; $|m_2| < a_1$ and so $|m_1| leq a_2+1$ such that $m_2a_2 = 1 + m_1a_1$, or equivalently, $m_2a_2-m_1a_1 = 1$.

So let $y$ be a sufficiently large integer, and let $k in {0,1,ldots, a_1-1}$ be such that $Na_1 + k = y$. Then $Na_1 +k(m_2a_2-m_1a_1) = y$, and
$N-km_1$ is positive if $N > km_1$, where $k < a_1$ and $m_1 leq a_2+1$. This will hold if $y$ is at least $a_1(a_1+1)(a_2+1)$. This completes the case for $k=2$.

Having established this for $k=2$ we now use induction to show this holds for general $k$. In particular, let ${a_1,a_2,ldots, a_{k+1}}$ be a set of positive integers where the greatest common divisor is 1. We show using induction on $k$ that every integer $Y$ can be expressed $Y = sum_{i=1}^{k+1} M_ia_i$. To this end, let $c =$gcd$(a_k,a_{k+1})$. Then by induction, for any sufficiently large integer $y$, there are nonegative integers $M_k$ and $M_{k+1}$ such that $M_ka_k+M_{k+1}a_{k+1} = cy$. So pick $y$ sufficiently large such that gcd$(a_1,ldots, a_{k-1}, cy) = 1$; indeed any $y$ sufficiently large satisfying gcd$(a_1,ldots, a_{k-1}, y) = 1$ will do [make sure you see why], and there is indeed such a positive integer $y$ [make sure you see why].

Then by the inductive hypothesis for any sufficiently large integer $Y$ there exist nonegative integers $M_1,ldots, M_{k-1}, M_y$ such that
$cyM_y + sum_{i=1}^{k-1} M_ia_i = Y$, as $cy$ itself satisfies $cy = M_ka_k+M_{k+1}a_{k+1}$ the result follows.

ETA: HOWEVER, we do note that, setting $A = max {a_1,ldots, a_k}$ that we may assume WLOG that $k leq 1+log A$. Or more precisely, there is a subset $S$ of ${1,ldots, k}$ of cardinality $log A$ such that gcd${a_i; i in S}$ is 1. Then it would suffice to show that every significantly large number $Y$ can be written $Y=sum_{i in S} M_ia_i$ where each $M_i$ is a nonnegative integer.

Indeed, each $a_i$ can be written as a product of at most $log A$ primes. So we build a set $a_{i_1},a_{i_2},a_{i_l}; l leq 1+log A$ such that gcd${a_{i_1},ldots, a_{i_l}} = 1$. Let us assume that using induction, that gcd${a_{i_1},ldots, a_{i_j}}$ is a composite number that has at most $log A -j+1$ prime factors $p_1ldots p_{log A-j}$. Then there exists an $a_i$ such that at least one of $p_1,ldots, p_{log A-j+1}$ doesn't divide $a_i$. Then gcd${a_{i_1},ldots, a_{i_j}, a_i}$ is a composite number that has at most $log A -j$ prime factors.