Re: [math-fun] Question about nonnegative integral linear combinations of a set of positive integers

23 Dec 2020

      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
>

Re: [math-fun] Question about nonnegative integral linear combinations of a set of positive integers

Neil Sloane