6
$\begingroup$

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_n\sim \frac{n^{k−1}}{(k − 1)!a_1a_2 ··· a_k}$$ as $n\to \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?$

$\endgroup$
9
  • 3
    $\begingroup$ Yes.$\phantom{}$ $\endgroup$ Jan 2, 2019 at 23:49
  • 3
    $\begingroup$ Consider just the case $k=2,a_1=3,a_2=7$ for clarity. Can you see that the coefficient of $x^n$ in $$(1+x^3+x^6+x^9+\ldots)(1+x^7+x^{14}+x^{21}+\ldots)$$ is exactly the number of ways for writing $n$ as $3A+7B$? $\endgroup$ Jan 2, 2019 at 23:51
  • 1
    $\begingroup$ Well, by geometric series $(1+x^3+x^6+\ldots)=\frac{1}{1-x^3}$ and $(1+x^7+x^{14}+\ldots)=\frac{1}{1-x^7}$. $\endgroup$ Jan 2, 2019 at 23:53
  • 3
    $\begingroup$ The meromorphic function $\frac{1}{(1-x^3)(1-x^7)}$ has a double pole at $x=1$ but the other singularities are all simple poles. Any simple pole provides a bounded contribution, since the coefficients of $\frac{1}{1-x\xi}$ have unit modulus for $\xi\in S^1$, hence the magnitude of the representation function is linear, since $[x^n]\frac{1}{(1-x)^2}=\Theta(n)$. $\endgroup$ Jan 2, 2019 at 23:55
  • 2
    $\begingroup$ Linear and with a bounded perturbation implies strictly positive from some point on - the hidden constant in $\Theta$ is not really important, but it can be derived from stars and bars. $\endgroup$ Jan 2, 2019 at 23:56

2 Answers 2

4
$\begingroup$

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 $k\equiv 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=n\bmod a_1$. Then $mk$ is a positive combination, and we can add some multiple of $a_1$ to make it $n$ instead, since $mk\equiv n\pmod{a_1}$ and $mk<n$ because $m<a_1$.

$\endgroup$
6
  • $\begingroup$ How do you get the coefficients all integers though? I see that $k=\sum c_ia_i$ where each $c_i$ is rational.... $\endgroup$
    – Mike
    Jan 4, 2019 at 18:08
  • $\begingroup$ *nonegative rational $\endgroup$
    – Mike
    Jan 4, 2019 at 18:16
  • 1
    $\begingroup$ @Mike: It's a generalization of Bézout's identity. (How would they become non-integral?) $\endgroup$ Jan 4, 2019 at 18:45
  • $\begingroup$ Ahh. Gotcha. That makes sense. BUT, there is a direct way to show all this though, without having to refer to Bezout's indentity--my answer above. [I did just edit it for clarity ] $\endgroup$
    – Mike
    Jan 4, 2019 at 18:48
  • $\begingroup$ @Mike: Your "direct way" seems to look a lot longer than mine, though. $\endgroup$ Jan 4, 2019 at 18:52
1
$\begingroup$

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_1\ldots 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.

$\endgroup$
1
  • $\begingroup$ Editted for clarity. Caught a crucial typo! $\endgroup$
    – Mike
    Jan 4, 2019 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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