Author: Nico BenschopDate: 1999/10/14 (14oct99) Forum: sci.math (NB: Integer State Machine ISM(Z,A) with state_set theintegers Z, and: input_set A={increment,decrement,swap2} = {+1, -1, swap(0,1)} = {a,b,c} See http://www.iae.nl/users/benschop/cantor.htm ) Ilias Kastanas wrote: > > In article , > Fred Galvin wrote: > @On Wed, 13 Oct 1999, Fred Galvin yelped: > @ > @> Even if it were as easy as a, bc ...?! > @> > @ Ouch! (OK, I've finished beating my head against the wall.) > @ > @ Fine, now do it with 2 permutations of finite order. > @ I only know an ugly (and general) way to do that; > @ is there a neat solution in this special case? > > Let's take g: g(-1)=0, ... okay, its cycles are (-1,0,1,2) and, > for k = 2,3...: (-k, 2k) and (fixed points) (2k-1). > Let f = cgb [in detail, f has cycles (0,1), (-1), (2k-1, 2k-2, -k)]. > Then g^4 = 1, f^6 = 1, f^3 = c, f^2 g = a, g^3 f^4 = b. > > So, composing f's and g's we get a set dense in Z!. -- Ilias Thanks, that is cool, Ilias. So for k-->inf we get in A*, with |A|=2, all finite permutations in Z! (forget about the uncountable reals, for-the-moment;-) Question: Does |A^k| grow exponentially like 2^k ? Probably not, because there are equivalences like f^6=1, etc. But does it grow polynomial ? Probably not, because each k-->k+1 multiplies the # of potentially new permutations by |A|, minus some equivalences ('old' cq shorter expressible perm's). Now I just read in the latest AMM (aug99) an article on semigroup S = A* of 2 x 2 matrices with two generators A={a,b} where: a = 1 1 b = 1 0 0 1 1 0 having a 'spectrum' function S(k) = |A^k| that grows faster with k than any polynomial, but less than exponential. Is'nt that related to the continuum hypothesis: some infinity between the cardinalities of N^k and 2^N ? And has that not to do with _function-composition_ (or modular forms, if you like;-) being "between" (*) and (^) ...? See http://www.iae.nl/users/benschop/sgrp-flt.htm http://www.iae.nl/users/benschop/func.htm http://www.iae.nl/users/benschop/ism.htm <-- Just curious.. -- Ciao, Nico Benschop. | AHA: One is Always Halfway Anyway http://www.iae.nl/users/benschop | Institute of Advanced Engineering ------------ Subject: Re: Subgroupgs of S_n (sci.math 29 oct 2002) From: Nico Benschop

Org: Digital Research : Finite Associative Networks Newsgroups: sci.math, alt.math.undergrad, alt.algebra.help -------------------- Nico Benschop wrote: > > Heather wrote: > > > > A problem I have says to give an example of a subgroup of S_5 > > with 10 elements and to give an example of a subgroup of S_4 > > with 12 elements. > > I'm not too familiar with the structure of the permutation groups, > > so this problem really seems like hodgepodge to me...is there a > > systematic way of attacking it? How so? -- Heather > > If G is the sought subgroup |G| = 10 = 2.5, then if commutative: > G = C2 x C5 (direct product) with two components of prime order, > hence must be cyclic C2 and C5. They are both commutative, and > the direct product of two commutative groups is also commutative, > which should help to find the proper C2 subgroup (of one or two > transpositions), given C5 = {1 2 3 4 5}. > Or: G is a non-cummutative semi-direct product: C2 -> C5, > with coupling function '->' where C5 is normal in G, > and C2 is the corresponding image group C2 =~= G / C5, > mapping C2 into Endo(C5) to prevent a larger closure then |G|=10. > > -- NB I think the commutative case does not occur, while a non-cmt decomposition (in permutation state-machine notation) runs as: a b | aA bA | aA^2 bA^2 | aA^3 U bA^3 --+--A--+---------+---------+---------+-----no new perm's in A^4---- 1 | 2 4 | 3 3 0 1 | 4 2 4 2 | 1 0 2 4 | 2 | 3 3 | 4 2 4 2 | 0 1 3 3 | 0 1 3 3 | 3 | 4 2 | 0 1 3 3 | 1 0 2 4 | 4 2 4 2 | 4 | 0 1 | 1 0 2 4 | 2 4 1 0 | 3 3 0 1 | 0 | 1 0.| 2 4 1 0 | 3 3 0 1 | 2 4 1 0 | <--A^2--> b a a b Note: C5 = Z5(+) = (+1)* = a* C2 = (n -> -n) mod 5 = (n -> 4n) mod 5 < Endo(C5) Recursively compose all sequences in A^{k+1} = {aA^k , bA^k} : row-wise by 'copy/paste', and delete 'old'= non-new columns. -- NB - http://home.iae.nl/users/benschop

Subject: Quatorze Juillet (14 july): Vive la Representation Finite Author: Nico BenschopOrg'n: Research Date: Fri, 14 Jul 2000 11:52:44 GMT (MathForum) -------- Just for fun (205 years ago, hardly 10 generations;-) "Leve eindige Representaties" -- There's more Structure, and more Fun, in the Finite. "Wie het kleine niet eert, is het Grote niet weerd" (who does not honor [take seriously] the Small, does not deserve the Large) .. from FST to FLT (;-) The Carry makes the Difference: breaking the Hensel Lift. Dual precision: mod p^k _and_ mod p^{3k+1} "Vive la Representation Finite" - On finite Computers & the Carry (English translation almost verbatim;( owing much to French;-) Re: Integer State Machines (ISM), and their Sequential (Associative) Closure (Specify and design sequential behaviour = CS / CE = Specify & Generate and factorize Finite Semigroups) Extend associative commutative idempotent (Boolean/Set) algebra, to associative commutative (Digital/Binary) arithmetic, to associative (Function composition) algebra (= Semigroups;-) ...finally, for APP (All Practical Purposes)... Happy Birthday! -- Ciao, Nico Benschop -- http://home.iae.nl/users/benschop/ism.htm (What -ism you mean? Integer State Machines; uncountable {a,b}* vs a* ) http://home.iae.nl/users/benschop/fewago.htm (On Powersums and Primesums: Fermat, Waring & Goldbach - revisited;( http://home.iae.nl/users/benschop/cantor.htm (His Discrete Table with that Diagonal must have been square w x w ;-) and E.T.Bell on Maths: http://home.iae.nl/users/benschop/quotes.htm

On constructive Balanced Object Oriented Algebra (BOOA - constructor)

sci.math: Re: Dear Nico B. (Not Benschop) & 5 BSM Author: Nico BenschopDate: 2000/05/19 ----------- Jan Stevens wrote: > > In article <39226CB3.EF7B32ED@pop.hit.fi>, > Pertti Lounesto writes: > > Dear Nicolas Bourbaki, > > How many sci.math readers thought that this post concerned > our Fermatist Nico B? Typical PL-trick of mis-representation, cq out-of-context reference;-) Moreover: Boubaki was the epitome of 'abstract' method, I'm told, while I prefer rather the very opposite: finite representation, and an approach balancing objects & operations: semantics & syntax. ^^^^^^^^^ = BOOA Constructor = = Balanced Object Oriented Algebra BTW: Not only am I a Fermat_ist, but also a Goldbach_er, and a Waring_er... See http://www.iae.nl/users/benschop/nf-abstr.htm http://www.iae.nl/users/benschop/ng-abstr.htm http://www.iae.nl/users/benschop/nw-abstr.htm ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ (redundant strings for lazy clickers;-) All solved with the same 2-pronged method: finite semigroup Z(.) mod m additively analysed qua structure, with modulus m chosen to fit the problem: m = p^k (prime p>2, k>1) for powersums [Fermat, Waring] m = m_k = \prod first k>1 primes [Goldbach]: map all primes p between p_k and m_k into the units group at the top of the Boolean Lattice of 2^k groups, which Z(.) mod m_k is; ... followed by considering the carry (k>2) going global (integers>0). In fact I'm interested, more generally, in a Digital Network Theory which would allow to decompose any FSM (Finite State Machine) into a network of the five basic State Machine (5 BSM) types ... ... unlike the rather 'cripple' Krohn-Rhodes ('65) decomposition into permutation/reset machines: which uses only 2 of the 5 BSM's. I suspect they (in the sixties) just generalized the Jordan/Hoelder group decomposition theorem, by adding reset machines (basically: flip-flops in case of binary code). Theory is complete but 'useless': simulating the non-used other 3 component types with reset- and permutation machines is NOT very efficient. Hence the theory flopped for APP (all practical purposes ;-( The 5 BSM correspond to the 5 non-isomorphc semigroups of order 2: --- with appealing computer engineering interpretations: C, Z: periodic & monotone counters (1 generator), next H = Hierarchy: H : combinational logic gate (2 commuting idempotents, AND isomorphic OR) R, L: short & long memory (reset & branch, FF & mux, left & right copy sgrp) (2 non-commuting idempotents) And semigroups (finite associative) are the general model of state- transformation closures = function composition. (you know: blocks coupled by input/output arrows;-) http://www.iae.nl/users/benschop/c-ranksm.dvi (almost typed crank-sm;-) "The structure of Constant Rank State Machines" (IFIP workshop on "Logic & Architecture Synthesis", Paris, may 1990) > [...corrected Bourbaki of 39 years ago...] > It would be really helpful for readers of Bourbaki if Lounesto > pointed out which step of the proof in the original version > is wrong. After all the case distinction dim E even or odd is > made there. -- Groetjes (speciaal voor Nico) Jan Bedankt Jan. Nu ken ik (partially;-) eindelijk eens 1 van mijn ca. 3000 homepage bezoekers (sinds jan98)... -- Ciao, Nico Benschop -- http://www.iae.nl/users/benschop

Re: Rings & associative Author: Nico BenschopDate: 2000/10/18 Forum: sci.math -------- ebool@my-deja.com wrote: > > I've been reading in Russian Algebra papers about rings and they do not > assume associativity in multiplication. Could someone explain the > importance of having or not this property. Thanks. --E. From a relative outsider (;-): Associative, although much more general than commutative (arithmetic) and idempotent (sets), is a VERY restrictive property compared with just 'closure'. For instance, one needs it for the simple concept of 'iteration' because only then: a(aa) = (aa)a = a^3 makes sense, otherwise brackets much remain and tree-structures are required to represent 'strings' over a single-letter alphabet! Estimate the fraction of all groupoids G_n (just closure required) of order n (for say only n=10) that are associative: You can write down n^(n^2) square composition tables for all G_n, and dividing by n! for isomorphisms, that is still an enormous amount. Now check how many (few;-) of these are associative: my guess is - almost vanishing. [... how many non-isomorphic semigroups of order n are there ?-) Conclusion: one can expect a LOT of 'structure' from an associtive closure (=semigroup, in general: of function composition). [any finite semigroup of order n, if left cancellative(?), is a State Machine over n states...] see http://www.iae.nl/users/benschop/c-ranksm.dvi : on semigroups and FSMs, and the 5 basic state machines;-) -- NFB

Subject: Re: infinity - an ignorant view Date: Fri, 05 Oct 2001 From: Nico BenschopOrg'n: Digital Research Newsgrp: sci.math Dann Corbit wrote: > > "Eric Kniffin" wrote: > > > > I'm not very knowledgable about this, so apologies in advance. > > My question might have a very simple, obvious answer that I would > > know if I learned more about it. > > > > So on with it. I have difficulty with the idea of infinities of > > different size. [...] > [...] > Another kind of infinity is uncountable. The number of real > numbers between zero and one is an infinity of this sort. Cantor > proved that you cannot number them in a one-to-one correspondence > with the integers (not fair using p-adics). ..[*] > -- > C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html > "The C-FAQ Book" ISBN 0-201-84519-9 Re[*]: Not fair to 'count the continuum' either: a contradiction in terms! The framework of Cantor's uncountability should better not be 'cardinality' ('size') but 'generating syntax', in the sense of noticing the minimal number of (sequential) generators involved. For Peano's naturals N(+) this is 1, and for Cantor's 2^N it is 2, with 2^Z \subset Z! (group of all permutations of the integers Z, sothat each subset of Z is a 'linked-list' or 'cycle' in group Z! and fixing all other states/integers). If you prefer a simpler mapping: 2^N (or 2^Z) is a Boolean Lattice which is a subsemigroup [ of commuting idempotents ] of Z^Z, the semigroup of all transformations of Z, with 'seq_dimension=3' (minimal nr of genetators). -- NB -- http://home.iae.nl/users/benschop/cantor.htm http://home.iae.nl/users/benschop/seqdim.htm http://home.iae.nl/users/benschop/ism.htm Integer State Machines

Continued: Semigroup S x S --> S is an FSM(Q,A) with ONE set S = Stateset Q & Inp.Alphabet A