[math-fun] Platonic surface puzzle
Let M be a compact surface and let N be the surface of one of the Platonic solids (a "Platonic surface"). A function f : M —> N is an "n-fold branched covering of N, branched over its vertices" if both 1) and 2) hold: ----- 1) For every point p of M such that f(p) is *not* a vertex of N, p has a neighborhood U that f takes homeomorphically onto the subset f(U) of N. Also, f^(-1)(f(p)) contains exactly n points of M. —and— 2) If p is a point of M such that f(p) *is* a vertex of N, then p has a neighborhood U that f takes to f(U) by wrapping around f(p) n times (just like the mapping z |—> z^n near the origin of the complex plane). In this case, f^(-1)(f(p)) contains only the point p of M. ----- Puzzle: ------- For each Platonic surface N and for each integer n ≥ 2, construct such a mapping f : M —> N for some compact surface M. —Dan
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
Isn’t it just 1/gcd({N_r})? By analogy with the case r=2, where any large enough multiple of the gcd is expressible with non-negative coefficients (at least that is the way I remember it), which means that the density is 1/gcd (since all linear combinations are multiples of the gcd) Sent from my iPhone
On Dec 18, 2020, at 23:25, Dan Asimov <asimov@msri.org> 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
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
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
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
this is called Frobenius's Problem, of course (I was expecting many people to say that, but I didn't see that mentioned here) Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Mon, Dec 21, 2020 at 3:09 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
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
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
Jeff is absolutely right, it would be a major overkill to use all this to prove that the language in question is regular! Sorry, this was not the question I asked in the homework six years ago. Actually, I was asking for the harder question that {a^{p_1}, …,a^{p_k}}^* = {a^m | m >= M} U F with F a finite set and for some positive M. For two numbers p, q with 2<= p < q and gcd(p,q) = 1, it is instructive to construct an NFA and then to make it deterministic. You can really see why for m large enough, all strings a^m are accepted. I also realized that I had downloaded some interesting talk on "The Frobenius Problem and its Generalization", by Jeff himself. I can’t find a date on the slides. Best, — Jean
On Dec 22, 2020, at 1:09 PM, Jeffrey Shallit <shallit@uwaterloo.ca> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Here's the reference for Jeff Shallit's slides:
International Conference on Developments in Language Theory
<https://link.springer.com/conference/dlt>
DLT 2008: Developments in Language Theory
<https://link.springer.com/book/10.1007/978-3-540-85780-8> pp 72-83| Cite as
<https://link.springer.com/chapter/10.1007/978-3-540-85780-8_5#citeas>
The Frobenius Problem and Its Generalizations
If anyone has access, I would appreciate a copy!
Best regards
Neil
Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane@gmail.com
On Tue, Dec 22, 2020 at 5:56 PM Jean Gallier <jean@seas.upenn.edu> wrote:
> Jeff is absolutely right, it would be a major overkill
> to use all this to prove that the language in question is regular!
> Sorry, this was not the question I asked in the homework six years ago.
> Actually, I was asking for the harder question that
> {a^{p_1}, …,a^{p_k}}^* = {a^m | m >= M} U F
> with F a finite set and for some positive M.
>
> For two numbers p, q with 2<= p < q and gcd(p,q) = 1,
> it is instructive to construct an NFA and then to make it deterministic.
> You can really see why for m large enough, all strings a^m are accepted.
>
> I also realized that I had downloaded some interesting talk on
> "The Frobenius Problem and its Generalization", by Jeff himself.
> I can’t find a date on the slides.
>
>
> Best,
> — Jean
>
>
> > On Dec 22, 2020, at 1:09 PM, Jeffrey Shallit <shallit@uwaterloo.ca>
> wrote:
> >
> > 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
> >
> > _______________________________________________
> > 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
>
https://b-ok.cc/book/646607/995bcc Merry Christmas. * Neil Sloane <njasloane@gmail.com> [Dec 23. 2020 17:59]:
Here's the reference for Jeff Shallit's slides: International Conference on Developments in Language Theory <https://link.springer.com/conference/dlt>
DLT 2008: Developments in Language Theory <https://link.springer.com/book/10.1007/978-3-540-85780-8> pp 72-83| Cite as <https://link.springer.com/chapter/10.1007/978-3-540-85780-8_5#citeas> The Frobenius Problem and Its Generalizations
If anyone has access, I would appreciate a copy! [...]
You can also use the Frobenius result to prove the following, which I find more interesting: If L is ANY unary language (doesn't have to be regular) then L* is regular. Along these lines I would like to mention an open problem. Let P denote the language of the primes in binary. Is P* regular? Almost certainly the answer is no, but nobody currently knows how to prove it. On 2020-12-22 5:56 p.m., Jean Gallier wrote:
Jeff is absolutely right, it would be a major overkill to use all this to prove that the language in question is regular! Sorry, this was not the question I asked in the homework six years ago. Actually, I was asking for the harder question that {a^{p_1}, …,a^{p_k}}^* = {a^m | m >= M} U F with F a finite set and for some positive M.
For two numbers p, q with 2<= p < q and gcd(p,q) = 1, it is instructive to construct an NFA and then to make it deterministic. You can really see why for m large enough, all strings a^m are accepted.
I also realized that I had downloaded some interesting talk on "The Frobenius Problem and its Generalization", by Jeff himself. I can’t find a date on the slides.
Best, — Jean
On Dec 22, 2020, at 1:09 PM, Jeffrey Shallit <shallit@uwaterloo.ca> wrote:
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
_______________________________________________ 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
participants (8)
-
christopher landauer -
Christopher Landauer
-
Dan Asimov -
Fred Lunnon -
Jean Gallier -
Jeffrey Shallit -
Joerg Arndt -
Neil Sloane