[seqfan] Re: seqs whose |differences| are 1,2,3,4,...

[franktaw at netscape.net]

OK, I'll see what I can do.

First, let me note that there are two assertions here, which I can 
clearly see are true, but I can't actually prove either of them.

The first is that Paul's sequence is not onto.  I think a careful 
analysis of exactly how it behaves will enable this to be proved.

Paul's sequence is, by construction, the lexicographically first 
one-to-one sequence with the difference property.

The second assertion that I can't prove is that, given any one-to-one 
finite sequence with the difference property, that ends with a new 
maximum, it is possible to extend to a permutation.  We do this by 
extending to a sequence which contains the minimum value not yet in the 
sequence and ends with another new maximum.  Iterating this will 
produce a permutation.  (Obviously, any sequence ending with a new 
maximum can be indefinitely extended.)  So, for example, after starting

0,1,3,6,2,7

we wish to extend to a one-to-one sequence including 4.  Simply trying 
all possibilities, the shortest such is

0,1,3,6,2,7,13,20,28,37,27,16,4

which can be extended by 17,31,46 to reach a new maximum.  (I have not 
yet determined what the shortest extension from here to include 5 and 
escape to infinity is; I think I'll have to write the program instead 
of continuing to work on it by hand.)

Now, any permutation with the difference property must be greater than 
Paul's sequence.  Find the point at which Paul's sequence is smaller, 
continue to a new maximum in the sequence, and this can be extended to 
a permutation smaller than our original one.

Franklin T. Adams-Watters

-----Original Message-----
From: N. J. A. Sloane <njas at research.att.com>

Franklin,  I had seen your message, but I had not appreciated
what it said!

I've read the message several times, but I admit I don't understand it.

The crucial two paragraphs are these, I believe:

(start)

If this is correct, it provides a negative answer to Conway's question.
  Given any infinite, one-to-one sequence with the specified difference
property, we can extend any initial segment to a bijection.  Extend the
segment to where it reaches a new maximum.  Now (this is a bit vague,
but is doable) futz around until you can extend to the smallest number
not yet used and back to another new maximum, then do so.  Repeat this
for the remainder of the sequence, and you have a bijection.

However, since the sequence Raff describes is the lexicographically
first one-to-one sequence with the difference property, any sequence we
generate in this way can be bettered by going further with the
backtracking heuristic before switching to the algorithm I describe.
In other words, Raff describes a sequence which is the greatest lower
bound of all sequences with the desired property.  If it doesn't have
the property, there is no minimum.

(end)

I don't really follow the algorithm you give in the first
of the two paragraphs.  Could you possibly explain it in more detail?

I am also having trouble following the argument in the second
paragraph.  Since Raff's sequence is not a permutation,
why should we start with it?

I can see that you are probably right, and that the sequence
we are looking for does not exist, but I would like to
see more details of the argument!


 Best regards
             Neil


_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/