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