Author:  Nico Benschop 
Date:    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}
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   <--

Just curious..
Ciao, Nico Benschop.             | AHA: One is Always Halfway Anyway | 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, -------------------- 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 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 -

Quatorze Juillet (14 july): Vive la Representation Finite ... sci.math 14july2000
Subject: Quatorze Juillet (14 july): Vive la Representation Finite
 Author: Nico Benschop 
  Org'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 --
(What -ism you mean? Integer State Machines; uncountable {a,b}* vs a* )
(On Powersums and Primesums: Fermat, Waring & Goldbach - revisited;(
(His Discrete Table with that Diagonal must have been square w x w ;-)

and E.T.Bell on Maths:

On constructive Balanced Object Oriented Algebra (BOOA - constructor)
 sci.math:  Re: Dear Nico B. (Not Benschop) & 5 BSM
   Author:  Nico Benschop 
     Date:  2000/05/19
Jan Stevens wrote:
> In article <>,
>         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
Not only am I a Fermat_ist, but also a Goldbach_er, and a Waring_er...

   (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
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;-) (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 --

Re: Rings & associative ... sci.math 18 oct 2000
Re: Rings & associative
Author: Nico Benschop 
Date:   2000/10/18
Forum:  sci.math
-------- 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 :
  on semigroups and FSMs, and the 5 basic state machines;-)   -- NFB

Subject: Re: infinity - an ignorant view Date: Fri, 05 Oct 2001 From: Nico Benschop Org'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: > "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 -- Integer State Machines

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

theory-edge: Message #98

theory-edge: Message #99

theory-edge: Message #100