[seqfan] Re: seqs whose |differences| are 1,2,3,4,...
franktaw at netscape.net
franktaw at netscape.net
Thu Mar 11 06:42:06 CET 2010
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
we wish to extend to a one-to-one sequence including 4. Simply trying
all possibilities, the shortest such is
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
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:
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.
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!
Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan