Why Semigroups Are Important?

Can anyone explain Rodseth's algorithm for numerical semigroups in easy language?

• Answer:

  Rodseth's algorithm is used to compute the Frobenius number [math]g(a,b,c)[/math], which is defined as the largest positive integer that cannot be expressed as a non-negative integer linear combination of [math]a, b [/math] and [math]c[/math]. It is well-known that [math]g(a,b)=ab-a-b[/math] when [math]a[/math] and [math]b[/math] are relatively prime. Rodseth's algorithm assumes that the numbers [math] a < b < c [/math] are pairwise relatively prime. There is a result due to Johnson that helps in dealing with other cases -- by defining [math]f(a,b,c)=g(a,b,c)+a+b+c [/math], it can be shown that [math]f(da,db,c) = d f(a,b,c)[/math], when [math]a[/math] and [math]b[/math] are relatively prime. I will illustrate the algorithm with a "generic example". First, recall that any  rational number, like [math]\frac{19}{7}[/math], can be expanded as a finite continued fraction, and intermediate truncations give better and better approximations to the original rational number. So [math]\frac{19}{7}[/math] is [math]2+\frac{1}{x}[/math], where [math]x[/math] is [math]1+\frac{1}{y}[/math], and so on. Successive truncation yields the sequence [math]\frac{2}{1}, \frac{3}{1}, \frac{8}{3}[/math] and [math]\frac{19}{7}[/math] itself. This is called the sequence of convergents, though I will call them dextroconvergents, with a nod to organic chemistry. I could also define levoconvergents. [math] \frac{19}{7} [/math] is [math]3-\frac{1}{x}[/math], where [math]x[/math] is [math]4-\frac{1}{2}[/math]. This gives the sequence [math]\frac{3}{1}, \frac{11}{4}[/math] and [math]\frac{19}{7}[/math]. Note that levoconvergents are monotone decreasing, unlike dextroconvergents which alternately underestimate and overestimate the number in question. Now suppose you want to compute [math]g(19,29,89)[/math]. First, find the unique positive integer [math]s < 19[/math] such that [math]29s \equiv 89(\rm{ mod } \; 19)[/math]. It turns out that [math]s=7[/math]. Starting from [math]1[/math], take the sequence of numerators of levoconvergents to [math]\frac{a}{s}=\frac{19}{7}[/math],  to get [math]1,3,11,19 [/math]. Also, [math]19 \; {\rm { mod }} \; 7 = -2 ; \;  7 \; {\rm { mod }} \; 2 = -1; \; 2 \; {\rm { mod }} \; 1 =0 [/math]. Take the sequence of moduli, ending with [math]0[/math], to get [math]7,2,1,0 [/math]. Putting these together, we get an increasing sequence [math]0=\frac{0}{19} < \frac{1}{11} < \frac{2}{3} < \frac{7}{1}=s [/math] Determine the two consecutive terms between which [math]\frac{c}{b}=\frac{89}{29}[/math] lies. (Observe that the definition of [math]s[/math] ensures that [math]s > c/b[/math].) Clearly, [math]\frac{T}{U}=\frac{2}{3} < \frac{c}{b}=\frac{89}{29} < \frac{V}{W}=\frac{7}{1} [/math] Now, [math]f(a,b,c) = bV+cU - min(bT,cW) = 412. [/math] [math]g(a,b,c)= f(a,b,c)-a-b-c = 275. [/math] The result can be verified here: http://mathsjavascript.free.fr/frobenius_9_page.html