Conference rusure::math

    re .0
    
    Assuming I've understood the problem, here is a counterexample.
    
    Let S = I[1] R[2]		(I'm using [] for the function subscripts)
    
    It can be seen that S(x) = x == 0 ? 1 : 2   (to borrow some notation from C)
    while SS(x) = 2 (for all x)
    
    thus S != SS
    
    However since S consists of only two functions there are only two
    possibilities for T viz. T = I[1] or T = R[2]. Manifestly S does not
    equal either of these functions.
    
    More generally the only counterexamples are S = I[a] R[b] where neither
    a nor b is zero.
    
    For all other S, S == SS and hence the antecedent is false.
    
    For all S except S = I[a] (a non-zero) and S = R[b] (b non-zero) and
    the general counterexample above, S is a constant function (the
    constant value depends of course on the functions making up the
    sequence).

    Thanks! I was thrown for a bit because I do composition the other
    way round from you. Fortunately, the problem stays the same, and your
    counterexample applies. (But I'd write it R[2];I[1].)

    Actually, my conclusion is wrong: I'd meant to capture R[2];I[1],
    which of course I haven't. (Yes, I'm that stupid.)

    Can you characterise the S for which S;S = S ?

    What if I changed the conjecture to:

    REVISED CONJECTURE
    IF   S ; S != S     (where S = S_1, .. , S_k)
    THEN For any x,
            let y[1] = S_1(x),.., y[k] = S_k(y[k-1])
            then for some n in {1,..,k-1}, y[n] = y[n+1]

    You might see how I messed up: I was floundering in the general
    direction of the idea that there would have to be something
    `redundant' about such an S. In your sequence, there is always
    a step at which the integer isn't changed. (But the step can
    be different for different starting integers.)

  Thanks enormously, for the notation, counterexample, and making me switch
  my brain on. Any idea about the revised version?
  (If it is true, my application works.)

    For functions it is usually as in .-1, with the composition
    f o g meaning f after g, i.e., (f o g)(x) = f(g(x)).  But in
    studying algebraic structures such as groups or rings you will
    often see the image of element "a" under permutation or
    homomorphism "S" (for the Greek letter sigma) written as
    "aS".  If then T is tau, you have the composition ST meaning
    aST = (aS)T i.e. sigma applied first, then tau.
    
    So like many notations the conventions sometimes depend on
    context. :-)
    
    Dan

The argument at the end of .3 establishes that any S is *equivalent*
to one of a few special cases (with length <= 2).
This characterises the S for which SS != S (as I asked).

It's not obvious to me, though perhaps it should be, that this
settles the revised conjecture.

It does seem easy to check it for these special cases.
[ It's true - I'm puzzled .3 says it looks false -
  in the only case in which SS!=S, namely I[a]R[b] (in .3's notation)
                                          with a and b non-zero and different,
    0                 isn't moved by the R, the first step.
    non-zero integers may move on the R, but their images aren't moved
                      on the second (the I) ]

However, although the property S;S != S depends only on the equivalence
class of s (i.e. the composite function), its not obvious to me that
the property in the conclusion isn't sensitive to the actual sequence
of component functions. i.e. I'm only about four-fifths convinced that
(using the base note's postfix `%')
  IF S% = T% and P(S)
  THEN P(T)
  where P(X) means the `trajectory' of any integer under X includes a repetition (a non-move)
        trajectory(x) means (I'll write the compositions .3's way round)
              the sequence (y_1,..,y_k),
              where k is the length of X,
                    y_1 = X_1(x), .. , y_k = X_k(y_(k-1))
                and (to accord with .3's order of composition),
                    X=(X_k,..,X_1)

If it's obvious one way or the other, I'd be very grateful for the
insight. (I actually dimly see how it might be proved, and might still be
labouring through it when put out of my misery.)




--
re composition notation.
  Sometimes I use `;' for little-ring-with-the-operands-reversed
  It's more program-like, which sometimes helps - but it's not
  at all common. In private life I use juxtaposition for application,
  which can save a lot of brackets.
  (It takes all sorts to make a world, doesn't it!)

re .5
    
>The argument at the end of .3 establishes that any S is *equivalent*
>to one of a few special cases (with length <= 2).
>This characterises the S for which SS != S (as I asked).
    
    One point I glossed over (but you seem to have picked up) is that
    I[a]R[b] is not the only case where SS != S but that all those S such
    that SS != S are equal to a function of that form. Where a conjecture
    depends on the actual individual functions making up S this may be
    relevant.
    
    Hence a more general form would include any number of I functions
    inserted before I[a] and any number of R functions inserted after R[b]
    and any number if I[0] functions interspersed arbitrarily.

>[ It's true - I'm puzzled .3 says it looks false -
>  in the only case in which SS!=S, namely I[a]R[b] (in .3's notation)
>                                          with a and b non-zero and different,
>    0                 isn't moved by the R, the first step.
>    non-zero integers may move on the R, but their images aren't moved
>                      on the second (the I) ]
    
    You are right. I mis-interpreted the "for all x, there is an n" to mean
    that it had to be same n that works for all x whereas you meant that
    there is an n, dependent on x. Right?
    
    Given that interpretation and the elaboration of my previous paragraph
    I think your conjecture (in .3) is true.

    Must go and do some work...

re .6

>    You are right. I mis-interpreted the "for all x, there is an n" to mean
>    that it had to be same n that works for all x whereas you meant that
>    there is an n, dependent on x. Right?

Right (more like continuity than uniform continuity).
Thanks for your help.
The problem is actually about idempotence of sequences of commands
to a funny kind of storage cell. (Meaning S;S has the same net effect as S.)

  I'm interested in things around:
  * some data-types have idempotent command sequences "by their nature".
    [ As opposed to artificially, an example of an artifice being adding
    a sequence number component to a simpler data-type, and sequence
    number parameters to its commands. ]
    Are there simple ways to check you've got one?
    I've a vague intuition that "naturally idempotent data-types" (pardon
    slop) are in some sense "storage".
  * sequence idempotence is related to "restartability", meaning that
    the net effect of a command sequence isn't disturbed by a certain
    kind of backward-jumping jitter. Exactly what the relationship is
    I don't know.
  If someone knows all about this kind of stuff, or recalls seeing it
  discussed somewhere, I'd be grateful to learn.