Conference rusure::math

Isn't an arithmetic progression one in which the differences between successive
elements is the same ?  For instance

	1 2 3

or

	6 4 2

or

	10 13 16.

If that definition is correct then it seems like a simple ordering (I'm assuming
that's what permutation means) of the positive integers NOT containing any
4-term A.P. is:

	4 5 6 1 2 3 10 11 12 7 8 9 17 18 19 13 14 15 23 24 25 20 21 22 ...

I'm suspicious that it's that simple, so I'm braced.  Embarrass me, c'mon!

/Eric

It isn't that simple.  Your sequence contains a 4-term AP in it:

	4 5 6 1 2 3 10 11 12 7 8 9 17 18 19 13 14 15 23 24 25 20 21 22 ...
			  ==                == == ==

Now you see the difficulty of the problem, right?

Ah ha !  I thought we only had to prevent four *consecutive* terms from
being in arithmetic progession.  Now that I've reread .0, I realize it's
more involved.

In the high squeaky tone of Rosanadanna: "never mind!"

/Eric

>                        <<< Note 354.0 by TOOLS::STAN >>>
>                            -< No A.P. of length 4 >-
>
>(Davies, Entringer, Graham, and Simmons)
>
>Is there a permutation of the positive integers a[1] a[2] a[3] ...
>which contains no ordered arithmetic progression of length 4?
>i.e. a[i]a[j]a[k]a[l] is never a 4-term A.P. for i<j<k<l?
>
>They can show that you can't prevent a 3-term A.P. and that you can stop a
>5-term A.P.

	Well, the first bit is easy.

	Define a permutation of the positive integers to be Davies/Ertringer/
Graham if it contains no arithmetic progression of length 3/4/5 respectively.
(Sorry, Simmons)

	First given a perm of the positive integers, a, we can construct an
inverse function a*, such that a*[a[i]] = a[a*[i]] = i.   

	Suppose a is a Davies permutation.   Then construct another such
permutation b, in the following way.
	(1) Subtract a[1]-1 from each value in the sequence
		(eg: a[1] -> 1, a[2] -> a[2]-a[1]+1, ...)
	(2) Throw out all the members of the sequence =< 0
		(there are exactly a[1]-1 of them, clearly)
	So if a began 3,6,8,1,2,999... then b begins 1,4,6,997...
[This step is not necessary, but it makes the next step clearer, and shows 
a kind of transformation that preserves the Davies property.]

	b is Davies, and b[1] = 1.
Now, 2 will appear somewhere in the sequence, say b*[2] = j.   But note that 
b*[3] < b*[2], by the Davies property.   Indeed b*[2^(n+1)+1] < b[2^n+1] for 
all n.

	But this means that there are an infinite number of positive integers
n which appear in the first j values of b, which is absurd.   So there are
no Davies series.

	A follow-on question is whether we can salvage things by permitting
a two-ended sequence:  ...a[-2], a[-1], a[0], a[1], a[2]...   The previous
technique does not carry over obviously to this case.

	A better way of approaching the two-ended sequence might be through
the finite case:  is there an n such that every perm a[1], a[2],..., a[n]
will contain an a.p. of length 3?   If so, what is the n?   This seems an
ideal topic for a computer search, if someone is interested.

	Must dash for dinner.

Regards,
Andrew.

	First, a redefinition.   Define a *permit* to be an n-permit, a 
P-permit, or a Z-permit, where:

	an n-permit is a permutation a[1],a[2],...,a[n] of the integers 1 to n.
	a P-permit is a permutation a[1],a[2],... of the positive integers.
	a Z-permit is a permutation ...a[-2],a[-1],a[0],a[1],a[2],... of
the positive integers.

	Now define: a permit is Davies/Ertringer/Graham if it contains no 
arithmetic progression of length 3/4/5 respectively.

	Finally, define: i precedes j if i =a [x] & j = a[y], and x<y.


Results:
	 No Davies P-permit exists.   
	 For every positive integer n, a Davies n-permit exists.
	 No Davies Z-permit exists.


Proofs:
	(1) No Davies P-permit exists.   
	A much simpler proof exists than the one I gave yesterday.   Say
that a[j] is the first term of the P-permit encountered which is greater
than a[1].   ie. a[i] > a [1] => i >= j.   Then {a[1],a[j],2a[j]-a[1]} is
an a.p. of length 3, and it appears in that order.

	(2) For every positive integer n, a Davies n-permit exists.
	I give a recursive construction.   It's fun to see why it works.
	Given {1,...,n}, arrange first all the *odd* numbers suitably as
a[1],a[2],...,a[c], where c = ceiling(n/2).   Then arrange all the even
numbers suitably, as a[c+1],...,a[n].

	Note, for no n > 3 is this the *only* perm possible.   (One can
always arrange to have the odds and the evens *just* overlap.)    However:

	(3) (Lemma) Let a be a Davies (4n-1)-permit.   Let b be the Davies
(2n)-permit constructed by removing every term >= 2m+1.   Then b consists
of *either* all the odd numbers followed by all the even numbers, or
vice versa.
	Proof by induction on n.   For n=1, this is trivial.   Assume that
it holds for all values < n.   Assume now that 1 precedes 2 in some Davies
(4n-1)-permit.   By induction, i precedes j, for all odd i, even j, where
|i-j| =< (2n-3).   So it remains only to show that 1 precedes 2n.
	Assume the converse.   Then 2n precedes 1 (& hence 4n-1).   But
each other odd number precedes 2n.   Consider only the odd numbers now, and
the a.p.'s of the form {k-2,k,k+2}.   Since 3 precedes 1, 3 precedes 5.
Since 3 precedes 5, 7 precedes 5. ... 4n-1 precedes 4n-3.   But this is a
contradiction, so 1 precedes 2n.
	This proves the lemma

	(4) No Davies Z-permit exists.
	Suppose the contrary, and further suppose that i<j<k, and 
a[i] <> a[j] <> a[k] mod 2.   Using Lemma (3), we can deduce an immediate
contradiction.   Therefore, in a Davies Z-permit, all the odds precede all
the evens, or vice versa.   Thus (without loss of generality) there is some i 
such that j >= i <=> a[j] is even.   Now allocating the even numbers to all the
a[i],a[i+1],... is exactly analogous to finding a Davies P-permit, which we
know to be impossible, by (1) above.

	(5) Finally, one might want to see if *all* the integers (not just
the positive ones) can be permed as a[1],a[2],... or as a[-1],a[0],a[1],...
But if such a thing was possible, then we could unearth the embedded
P-permit or Z-permit formed by the positive integers, so this is not possible.

	A re-redefinition, for clarity.   I used the word 'permutatation' 
once where I shouldn't.   It didn't affect my arguments.   So:

	a Z-permit, a, is a function mapping the integers onto the positive 
integers, such that the two sets are in 1-1 correspondence.   (Such is 
possible because both sets have the same cardinality, even though one is a 
strict subset of the other.)


	I thought I had solved Graham, but he fought back by planting a bug
in my proof.   I can't repair the proof offhand.   I'll report any progress.

Regards,
Andrew.

	An infinite number of Graham P-permits exist.

	Let n >= 4.

	We divide up the positive integers into disjoint intervals:
I[0] = {1}
I[1] = {2,...,n}
I[2] = {n+1,...n^2}
.
.
.
I[i] = {n^(i-1)+1,...,n^i}
.
.
.

	Now we will define a permutation, b, on the positive integers
such that b maps I[i] onto I[i] for all i.   If a_i is a certain
Davies (n^i - n^(i-1))-permit, then

	b[n^(i-1) + j] = a_[j] + n^(i-1).

	Thus if b contains a 5 term a.p., then no 3 of the terms can lie
in the same interval.   But that's not quite enough.   The real sneakiness
is in the selection of the a_i.

	If i is odd, then pick a_i to list all the odd numbers *before* the
even numbers.   If i is even, then pick a_i to list all the even numbers
before the odd numbers.

	Th effect of this is that if a 5 term a.p. contains 2 terms in each
of 2 adjacent intervals, then all the 5 terms must be even, or all must be
odd.

	But we can extend this: for odd i, put the 0mod4 numbers before the
2mod4, and the 1 mod4 before the 3mod4.   For even i, 2mod4 before 0mod4,
and 3mod4 before 1mod4, and so on downwards in the recursive construction of 
a_i.

	The net effect is that the 5 term a.p. cannot contain 2 terms in each
of two adjacent intervals.

	So, suppose that v<w<x<y<z and V,W,X,Y,Z is an a.p. where V=b[v], etc.
Say that Z-Y = d.   Let I[i'] be the interval containing w (& hence W), and 
I[i"] be the interval containing z.   By the foregoing, i'+1 < i".

	Since the a.p. spans more than one interval, it is clear that d > 0.

d = W - V < n^i' =< n^(i'+1)/4 =< (Z-V)/4 = 4d/4 = d.   Contradiction.

	So no 5 term a.p. exists.   End of story.


	Obviously, Graham n-permits and now Z-permits must exist, to tidy up
the Graham issue.

	Let me correct a tiny bugette my essentially sound proof, and 
rearrange a couple of things to make it clearer (I hope) what I'm
suggesting.


Result:
	An infinite number of Graham P-permits exist.

Proof:
	By construction.

	Let n >= 5.

	We divide up the positive integers into disjoint intervals:
I[0] = {1}
I[1] = {2,...,n}
I[2] = {n+1,...n^2}
.
.
.
I[i] = {n^(i-1)+1,...,n^i}
.
.
.

	Now we will define a permutation, b, on the positive integers
such that b maps I[i] onto I[i] for all i.   If a_i is a certain
Davies (n^i - n^(i-1))-permit, then

	b[n^(i-1) + j] = a_[j] + n^(i-1).

	Thus if b contains a 5 term a.p., then no 3 of the terms can lie
in the same interval.   But that's not quite enough.   The real sneakiness
is in the selection of the a_i.

	If i is odd, then pick a_i to list all the odd numbers *before* the
even numbers.   If i is even, then pick a_i to list all the even numbers
before the odd numbers.

	The effect of this is that if a 5 term a.p. contains 2 terms in each
of 2 adjacent intervals, then all the 5 terms must be even, or all must be
odd.

	But we can extend this: for even i, put the 0mod4 numbers before the
2mod4, and the 1 mod4 before the 3mod4.   For odd i, 2mod4 before 0mod4,
and 3mod4 before 1mod4, and so on downwards in the recursive construction of 
a_i.

	[We can define the ordering once and for all.   Let p,q be positive
integers, write them in binary, and reverse the order of the bits in each.   
Then p precedes q in the LR ordering iff p's reversed bitstring precedes q's.
ie: 12 = 00011 precedes 2 = 01 precedes 51 = 110011.   Now for I_i, where 
i is even, just use the LR ordering.   Where i is odd, use the reverse of
the LR ordering.]

	The net effect is that the 5 term a.p. cannot contain 2 terms in each
of two adjacent intervals.   [I leave proof to you.]

	So, suppose that v<w<x<y<z and V<W<X<Y<Z is an a.p. where V=b[v], etc.
Say that Z-Y = d <> 0.   Let I[i'] be the interval containing w (& hence W), 
and I[i"] be the interval containing z.   

	I claim that i'+1 < i".   Firstly i' < i", since otherwise there
is an a.p. of length *4* inside I[i'].   Next, if i'+1 = i", then to avoid
having an a.p. of length 3 in one of I[i'] or I[i"], we must have W & X
lying in I[i'], while Y & Z lie in I[i"].   But we know that a 5 term a.p.
cannot contain 2 terms in each of 2 adjacent intervals.

	Since the a.p. spans more than one interval, the a.p. must be
*increasing*, and hence d > 0.

d = W - V 
  < n^i'		(since W =< n^i') 
  =< [n^(i'+1)-n^i']/4	(since n-1 >= 4)
  =< (Z-n^i')/4 	(since Z >= n^(i'+1)
  < (Z-V)/4 		(since V < n^i')
  = 4d/4		
  = d.   Contradiction.

	So no 5 term a.p. exists.   End of story.

	Obviously, Graham n-permits exist.   Graham Z-permits exist, by 
setting b[i] odd <=> i < 0.   This tidies up the question of Graham.

	Can this be extended to Ertringer?   I don't think so.   My guess
is that a length 4 a.p. cannot be prevented.   I base this purely on the
relative difficulties of solving Davies & Graham, and on the fact that
the proof above breaks down fairly irreparably when dealing with a length
4 a.p.

Regards,
Andrew.