But one does not need a Frobenius bound to prove that (a^{p_1}, ..., a^{p_k})^* is regular (and one doesn't need the condition gcd(p_1, ..., p_k)= 1 either). It follows immediately from standard results on the closure properties of regular languages. Why complicate things? On 2020-12-22 12:07 p.m., Jean Gallier wrote:
It is easy to prove that if 2 <= p_1 < …< p_k and gcd(p_1, …, p_k) = 1, then every n >= (p_1 - 1)(p_2 + … + p_k -1) can be written as n = i_1p_1 + .. + i_kp_k, with i_1, …, i_k in N (the natural numbers).
This follows from the fact (Bezout) that gcd(p_1, …, p_k) = 1 iff h_1p_1 + ... + h_kp_k = 1 for some integers h_1, …, h_k in Z.
The problem is that if n >= 0, some h_j may be negative so we use the following trick. Divide all the h_j by p_1, so that h_j = p_1a_j + r_j, 0 <= r_j <= p_1 - 1. Then n = (h_1 + a_2h_2 + … + a_kh_k)p_1 + r_2p_2 + … + r_kp_k. Now, only the coefficient of p_1 may be negative. The “bad” set S = {n \in Z | n = i_1p_1 + i_2p_2 + … + i_kp_k, i_1 < 0, 0 <= r_j <= p_1 - 1, j>= 2} has the maximum element -p_1 + (p_1 - 1)(p_2 + … + p_k). So every natural number n >= -p_1 + (p_1 - 1)(p_2 + … + p_k) +1 = (p_1 -1 )(p_2 + .. + p_k - 1) is representable using natural numbers.
The bound can be lowered to (p_1 - 1)(p_k - 1), a result attributed to I Schur 1935, and proven by Alfred Brauer (1942). It is still not optimal. Erdos, Graham and others have better lower bounds.
I got excited about this in 2014 while teaching a theory of computation course. You can reformulate the problem as: prove that if gcd(p_1, … p_k) = 1, then the language on the one letter alphabet {a}, {a^{p_1}, …, a^{p_k}}^* (* = Kleene star), is a regular language! I wrote up the following for my students. https://www.cis.upenn.edu/~cis511/Frobenius-number.pdf
Best, — Jean
On Dec 21, 2020, at 3:07 AM, christopher landauer <topcycal@gmail.com> wrote:
hihi, all -
ah, excellent, thank you, fred - i wrote a computer program (of course) this evening that suggested the sylvester result, but did not come close to proving it, and i assume that that result sort of implies the general result to answer dan's question for more than two elements (i imagine that a suitable induction on r would work):
at most finitely many positive integers n divisible by c = gcd({N_j|1<=j<=r}) are not representable in the form n = sum(1<=j<=r) (c_j * N_j), c_j non-negative integers
more later,
chris
On 12/20/20 23:43, Fred Lunnon wrote:
See Conway's money game --- https://en.wikipedia.org/wiki/Sylver_coinage
WFL
On 12/21/20, christopher landauer <topcycal@gmail.com> wrote:
hihi -
it is my vague recollection that for positive integers a, b with gcd(a, b) = 1,
then for all n >= a * b,
there is a representation n = x * a + y * b with x, y >= 0
(this is trivial for a=1 or b=1, so we can assume a, b >= 2)
that would mean density 1
(but this result is even stronger than the original density assertion:
it says that all but finitely many positive integers have such a representation;
i think i saw a reasonable proof of that once long ago)
it is my impression that essentially the same kind of thing
could/should/would be true for more than two elements:
if we take c = gcd{N_j},
then for any large enough n divisible by c,
there is a representation n = sum(x_j * N_j) with all x_j >= 0,
so the density is 1/c
(only multiples of c can occur, of course,
and the stronger assertion is that all but finitely many of them have such a representation)
more later,
chris
On 12/18/20 23:25, Dan Asimov wrote:
Let N_1, ..., N_r be a set of positive integers ≥ 2 whose prime factorizations are known.
Let X = {∑ c_j N_j} be the set of all linear combinations of the N_j with nonnegative integer coefficients c_j.
Is it easy to determine what the (asymptotic) density of X is in Z+ ???
(An N_j may have repeated prime factors, and several N_j's may have common factors.)
—Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun