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

[Robert Munafo]

I believe this is the crucial insight:* "**hole-filling postponed without
limit" [1]*

The difficulty in definitively selecting a "lexicographically first
arrangement of the integers" seems similar to the difficulty in accepting
the Axiom of Choice. [2] We are confronted, (or possibly confounded), by the
uncountably large set of possible solutions.

But if one establishes that all the holes can be filled in later, and
further that we only need to determine some conveniently-small finite
initial portion of the sequence, then we can see that given any finite N,
the first N terms of the following two sequences are the same (using wording
of [3] and changing "one-to-one" to "injective and unbounded"):

  The lexicographically first one-to-one sequence a(n)
  satisfying |a(n+1)-a(n)| = n

  The lexicographically first injective and unbounded sequence b(n)
  satisfying |b(n+1)-b(n)| = n

Where "injective" is understood to mean that for any integer j, there is *at
most* one n such that b(n)=j (see [4]) and "unbounded" means that there is a
b(n) for all n (not quite the same as in [5], is there a better word?) or in
other words that the sequence "has an infinite number of terms" (using the
sloppy colloquial jargon of the 18th century).

Once we accept that, then the method of FTAW [6] seems to work: Use a
conditionally-greedy selection algorithm that does not accept any candidate
next term until a guaranteed "escape route" is found.

[1] from Ron Hardin's message of Mar 11, 2010 at 01:53, included below.

[2] http://en.wikipedia.org/wiki/Axiom_of_choice

[3] from Franklin T. Adams-Watters's message of Mar 10, 2010 at 15:08,
included below.

[4] http://en.wikipedia.org/wiki/Injective_function

[5] http://en.wikipedia.org/wiki/Bounded_function

[6] from Franklin T. Adams-Watters's message of Mar 11, 2010 at 00:42,
included below.

- - -

On Thu, Mar 11, 2010 at 01:53, Ron Hardin <rhhardin at att.net> wrote:
>
> I didn't follow what the note meant either.
>
> That sequence can't be continued, right; and increasing L (the lookahead)
can apparently raise the maximum of 1-1 terms 1..top reached.
>
> I'm less worried about its being lexicographically least than existing.
>
> The method so far however generates only finite sequences.  Is that always
true (so there is no 1-1 sequence with the difference property at all) or
will some patterns emerge, like  166 56 167 55 168 54 169 53 170 52 171 51
172 50 173 49 174 48 175 47 176 46 177 45 178, that can be strung together
to fill in gaps with some transitional terms.
>
> The failure that seems most likely is that the stable beginning of the
sequence, as L is increased, is strictly increasing, with that hole-filling
postponed without limit.
>
> I might be saying the same thing but I can't tell.
> [...]

 - - -

On Wed, Mar 10, 2010 at 15:08, "Franklin T. Adams-Watters" <
franktaw at netscape.net> wrote:
> How about "The lexicographically first one-to-one sequence a(n)
> satisfying |a(n+1) -a(n)| = n"?
>
> [...]

 - - -

On Thu, Mar 11, 2010 at 00:42, "Franklin T. Adams-Watters" <
franktaw at netscape.net> wrote:
> 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

--
 Robert Munafo  --  mrob.com