Conference rusure::math

    Here's a pretty pattern of 39 checkers for N=11.
    
	@ @ . . . . . @ @ . .
	@ . @ . . . @ . . @ .
	. @ . @ . . @ . . . @
	. . @ . @ . . @ . . @
	. . . @ . @ . @ . @ .
	. . . . @ @ @ . @ . .
	. @ @ . . @ . . . . .
	@ . . @ @ . . . . . . 
	@ . . . . @ . . . . @
	. @ . . @ . . . . @ .
	. . @ @ . . . . @ . .

>    Is the number of checkers O(N^2) for large N?

No, O(N^1.5) is an upper bound.

Suppose that we have a solution with C checkers.   Let n(i) be the number of
checkers in row i.   Every solution satisfies an inequality called Fred:

	sum(i=1..N)(n(i)(n(i)-1)) =< N(N-1)

Which is to say that each row books a certain subset of the unordered pairs of
columns, and that if Fred is false, the pigeonhole principle permits us to
conclude that some pair of columns is booked by two rows.

The set of solutions were looking for is contained within the set of values
that satisfy Fred.   So in looking for an upper bound to C = sum(i=1..N)(n(i))
it makes sense to consider upper bounds to C that satisfy Fred.

Further suppose that j and k are row such that:

	n(j) - n(k) >= 2

Then define n'(i) by

	n'(j) = n(j) - 1
	n'(k) = n(k) + 1
	otherwise n'(i) = n(i)

This evidently satisfies Fred as well, and gives the same C.

So we need consider only those vectors n(i) that satisfy the Monopoly House
Building principle: for all j,k:

	|n(j) - n(k)| = 0 or 1.

With this drastic constraint, every row has either t or t+1 checkers, and
an upper bound on t (using Fred) is:

	(sqrt(4N-3)+1)/2

Since the number of checkers is less than (t+1)N, and t is bounded by N^�,
C is bounded by N^3/2.

Andrew

    Nice result!!  BTW, it matches a computer search fairly well:
    
	t = [ sqrt(4*N-3)+1)/2 ]
    	F(N) = max number of checkers
    
	 N  (t+1)*N  F(N) (t+1)*N-F(N)
	 1	 2    1	   1
	 2	 4    3    1
	 3	 9    6    3
	 4	12    9    3
	 5	15   12    3
	 6	18   16    2
	 7	28   21    7
	 8	32   24    8
	 9	36   29    7
	10	40   34    6
	11	44   39    5
	12	48    ?    ?
    
    From whence did Fred derive?  It's not at all obvious.
    
    How about a constructive lower bound?

     re .3
     
>>    From whence did Fred derive?  It's not at all obvious.
     
     There are C(N, 2) = N(N-1)/2 ways to select two columns out
     of N columns.  There are C(n(i), 2) = (n(i))(n(i)-1)/2 ways
     to select two occupied columns out of a row with n(i)
     columns occupied.
     
     You have an aligned rectangle if any two rows both have the
     same pair of columns occupied.
     
     The sum for row i = 1, ..., N of C(n(i), 2) is how many not
     necessarily distinct pairs of occupied columns there are. 
     If this exceeds the total number C(N, 2) of pairs of
     columns, then at least one pair must be duplicated.  The way
     the count is set up the duplicated pair must show up on
     separate rows and so it makes an aligned rectangle.
     
     For example, for N=4 you have
     
     occupied pair of columns: {1,2} {1,3} {1,4} {2,3} {2,4} {3,4} n(i)(n(i)-1)
     
     Row 1: @--@                 no    no   yes    no    no    no    2
     
     Row 2: -@@@                 no    no    no   yes   yes   yes    6
     
     Row 3: @-@-                 no   yes    no    no    no    no    2
     
     The sum of the (n(i))(n(i)-1) terms is 10, or twice the
     numbers of yes's.  N(N-1) is 12, or twice the number of
     (unordered) pairs.  If row 4 has three checkers, then that
     is adding 6 (twice the number of pairs that three checkers
     make) to the sum, giving you a total of 16 compared to the
     limit of 12; i.e., a total of 8 yes's spread over 6 pairs. 
     At least one pair (one column of my table) would have to
     have two yes's in it, and that means there will be a
     rectangle.
     
     Dan

Notation summary
	t = [ sqrt(4*N-3)+1)/2 ]
	where [x] is the 'floor', the integral part of x.
    	F(N) = max number of checkers
	F(N) =< (t+1)N

>    Nice result!!  BTW, it matches a computer search fairly well:

	Thanks, but we can do better if you're looking to bound F(N) tightly.
Assume that we've got a solution satisfying the Monopoly House Rule, ie. each
row has either t or t+1 checkers in it.   Define a to be the number of rows that
have t+1 checkers.   The estimate I gave assumes a worst case: a = N.    But in
fact such a high value is often impossible.

	In reality...

F(N) =< tN + a 			(*)

	(N-a)t(t-1) + a(t+1)t =< N(N-1)
but
	(N-a-1)t(t-1) + (a+1)(t+1)t > N(N-1)

(This is just our old friend Fred, for the Monopoly House case).

Rearranging, get:

	a = [ (N-1 - t(t-1))N/2t ]

Now the good thing about (*) is that the bound is actually *attained* for some
n.   If N = n^2 - n + 1, then t = n, and a = 0.   But n^2 - n + 1 is just
the number of points (or edges) in the projective plane of degree n, PL(n).

Aha!	So we identify the rows of our square with the points of PL(n) and the
columns with the edges, and put a checker in a box iff the corresponding point
lies on the corresponding line.

(My geometry is rusty, but I believe we define a projective plane as follows:
we have points, and we have lines.   Every two points define a unique line
which passes through them;  every two lines meet at a unique point.   There is
also some criterion like 'each point has at least 3 lines' to rule out various
trivial cases.)

The problem is, that projective planes don't exist for all n.   Perhaps someone
with a text-book can look it up.   I show below the incidence (= checkers)
diagrams for n = 3,4,5.   From the dim mists of time, I seem to recall Marshall
Hall proving that Pl(6) (and other ones = 2 mod 4?) don't exist, through some
argument I can't recall).   I want to know what the answer is before I carry 
on.

	In the mean time, here is my extended version of CLT::GILBERT's table.

	 N  t (t+1)*N  	  F(N) (t+1)*N-F(N)	a	tN+a tN+a-F(N)
	 1  1	 2	    1	  1		0	 1	0
	 2  1	 4	    3	  1		1	 3	0
	 3  2	 9	    6     3		0	 6	0
	 4  2	12	    9     3		1	 9	0
	 5  2	15	   12     3		2	12	0
	 6  2	18	   16     2		4	16	0
	 7  3	28	   21     7		0	21	0
	 8  3	32	   24     8		1	25	1
	 9  3	36	   29     7		3	30	1
	10  3	40	   34     6		5	35	1
	11  3	44	   39     5		7	40	1
	12  3	48     45or46  2or3	       10	46   0or1
	13  4   65    	   52    13             0	52	0

The important thing is the last column, which shows the difference between
my bound (*), and CLT::GILBERT's computed answer.   In addition, I exhibit
below the exact projective plane solution for N=13, and by pruning the
top row and the leftmost column, we get a lower bound of F(N) >= 45.


n=3:

X X X . . . .
X . . X X . .
X . . . . X X
. X . X . X .
. X . . X . X
. . X X . . X
. . X . X X .    

n=4:

X X X X . . . . . . . . .
X . . . X X X . . . . . .
X . . . . . . X X X . . .
X . . . . . . . . . X X X
. X . . X . . X . . X . .
. X . . . X . . X . . X .
. X . . . . X . . X . . X
. . X . X . . . X . . . X
. . X . . X . . . X X . .
. . X . . . X X . . . X .
. . . X X . . . . X . X .
. . . X . X . X . . . . X
. . . X . . X . X . X . .

	Forgot to put in n=5.

X X X X X . . . . . . . . . . . . . . . .
X . . . . X X X X . . . . . . . . . . . .
X . . . . . . . . X X X X . . . . . . . .
X . . . . . . . . . . . . X X X X . . . .
X . . . . . . . . . . . . . . . . X X X X
. X . . . X . . . X . . . X . . . X . . .
. X . . . . X . . . X . . . X . . . X . .
. X . . . . . X . . . X . . . X . . . X .
. X . . . . . . X . . . X . . . X . . . X
. . X . . X . . . . X . . . . X . . . . X
. . X . . . X . . X . . . . . . X . . X .
. . X . . . . X . . . . X X . . . . X . .
. . X . . . . . X . . X . . X . . X . . .
. . . X . X . . . . . X . . . . X . X . .
. . . X . . X . . . . . X . . X . X . . .
. . . X . . . X . X . . . . X . . . . . X
. . . X . . . . X . X . . X . . . . . X .
. . . . X X . . . . . . X . X . . . . X .
. . . . X . X . . . . X . X . . . . . . X
. . . . X . . X . . X . . . . . X X . . .
. . . . X . . . X X . . . . . X . . X . .

	So tN + a is attained for N=21, and by removing the left-hand row and
top most column, tN+a-F(N) = 0 or 1 for N=20.

	View the array above (and the same applies for the arrays for n=3,4)
in the following way.   The 2n+1 left-most rows and top-most columns are a
fixed frame, and wlog we can fill in the checkers in the way defined.
The remainder of the grid consists of an array of (n-2) x (n-2) blocks, each
block consisting of an (n-1)x(n-1) square of values, P(i,j) (i,j in {1,..,n-2}

	Regarding a checker as 1 and a space as 0, each P(i,j) will be a 
permutation matrix (ie. exactly n-1 non-zero entries, one in each row & column)
The permutation matrices will be any such that:

(a)	I + sum(i)(P(i,j)) = U for all j.	
	I + sum(j)(P(i,j)) = U for all i.
where U is the matrix with all entries 1.

(b)	Let Q(i,j,k,l) = P(i,j).(P(k,j))'.P(k,l)
where A' is the transpose of A.   No entry of Q(i,j,k,l) may have a 1 in the
same site as P(i,l).

	Symmetry considerations simplify the search space enormously for these
things.

	Anyone have any book knowledge of projective planes.

	While munching my "volailles financi�res" at Jacqueline's Bistro on
the Avenue Californie, I was idly trying to prove my suspicion that PL(6)
did not exist.   I failed.   I seem to have proved that PL(6) does exist:

n=6:
X X X X X X . . . . . . . . . . . . . . . . . . . . . . . . .
X . . . . . X X X X X . . . . . . . . . . . . . . . . . . . .
X . . . . . . . . . . X X X X X . . . . . . . . . . . . . . .
X . . . . . . . . . . . . . . . X X X X X . . . . . . . . . .
X . . . . . . . . . . . . . . . . . . . . X X X X X . . . . .
X . . . . . . . . . . . . . . . . . . . . . . . . . X X X X X
. X . . . . X . . . . X . . . . X . . . . X . . . . X . . . .
. X . . . . . X . . . . X . . . . X . . . . X . . . . X . . .
. X . . . . . . X . . . . X . . . . X . . . . X . . . . X . .
. X . . . . . . . X . . . . X . . . . X . . . . X . . . . X .
. X . . . . . . . . X . . . . X . . . . X . . . . X . . . . X
. . X . . . X . . . . . X . . . . . X . . . . . . X . . . X .
. . X . . . . X . . . . . X . . . . . X . X . . . . . . . . X
. . X . . . . . X . . . . . X . . . . . X . X . . . X . . . .
. . X . . . . . . X . . . . . X X . . . . . . X . . . X . . .
. . X . . . . . . . X X . . . . . X . . . . . . X . . . X . .
. . . X . . X . . . . . . X . . . . . . X . . . X . . X . . .
. . . X . . . X . . . . . . X . X . . . . . . . . X . . X . .
. . . X . . . . X . . . . . . X . X . . . X . . . . . . . X .
. . . X . . . . . X . X . . . . . . X . . . X . . . . . . . X
. . . X . . . . . . X . X . . . . . . X . . . X . . X . . . .
. . . . X . X . . . . . . . . X . . . X . . X . . . . . X . .
. . . . X . . X . . . X . . . . . . . . X . . X . . . . . X .
. . . . X . . . X . . . X . . . X . . . . . . . X . . . . . X
. . . . X . . . . X . . . X . . . X . . . . . . . X X . . . .
. . . . X . . . . . X . . . X . . . X . . X . . . . . X . . .
. . . . . X X . . . . . . . X . . X . . . . . X . . . . . . X
. . . . . X . X . . . . . . . X . . X . . . . . X . X . . . .
. . . . . X . . X . . X . . . . . . . X . . . . . X . X . . .
. . . . . X . . . X . . X . . . . . . . X X . . . . . . X . .
. . . . . X . . . . X . . X . . X . . . . . X . . . . . . X .

	So F(31) = 6.31 = 186 = tN+a.   How does it work?

	Let's reduce our search space for PL(n) by arbitrarily putting some
extra constraints on the P(i,j) matrices that we consider.   Firstly, let's
say that P(i,j) = A(i+j-2) for some matrices A(k) (k=0,..,n-3).   i.e. we will 
have diagonal rows of the same matrix running from top-right to bottom-left.   
This is just what we have anyway in all the solutions so far exhibited.   Let's
do our addition of indices mod n-2 here.

	Secondly, let's look for a set of matrices A(k) (k=0,..,n-3) such that
together with the identity they form a group of order n-1, and such that no
A(k) when viewed naturally as a permutation of the set {1..n-1} fixes any
element.

	Certainly, such a set will satisfy the requirement (a) from the
previous reply:
I + sum(i) (A(k)) = U.

	The other requirement (b), if you work it through, translates into:
for all w in {1,..n-3}, A(d)A'(d+w) spans the set {A(k)} as d varies from 0 to 
n-3.   (To reiterate, all addition of indices is being performed mod n-2).
Let's call this constraint (b*).   It is the only constraint we are left to
satisfy, once we accept that we will pick a permutation group of order n-1,
no non-trivial element of which fixes anything, and arrange copies of it on
the NE-SW diagonals as described.

	So for all the examples of PL(n) shown so far, let p be a cyclic
element of order n-1.

n=3:
k:	0
A:	p

n=4:
k:	0	1
A:	p	p^2

n=5:
k:	0		1		2
A:	(12)(34)	(13)(24)	(14)(23)	<- perms of {1,2,3,4}

n=6:
k:	0	1	2	3
A:	p	p^2	p^4	p^8 (=p^3)

	This summarizes all the PL(n) checker arrays we've looked at.   You can 
check that the Spanning Criterion is adhered to for the above cases.   How can 
we go on? 

n=7:	currently dunno

n=8:
k:	0	1	2	3	4	5
A:	p	p^3	p^2	p^6	p^4	p^5

n=9:	presently pig-ignorant

	Generalizing, if m = n-1 is prime, then define r to be primitive mod m,
ie r is generator of cyclic multiplicative group order m.   Then:

	A(k) = p^(r^(k))

will satisfy (b*).   Therefore PL(n) exists.   There are probably many other 
n for which PL(n) exists, but in the absence of a text-book or information from
some kind Notesfile soul, my curiosity determines that I derive the existing
theory myself.   Passing stranger, pity the plight of someone marooned far
from Maths books in English, and tell me what the answer is.

	The consequences for the checkers problem is that there we now know
that there are an infinite number of N for which F(N) = tN+a.   This puts some
kind of limit on the degree to which F(N) can diverge from tN+a for N =/= 
n^2 -n +1.   But it obviously makes sense to nail dead the projective plane
question before returning to general N.

	However, once we've done that, I have some ideas about how to deal with
N =/= n^2 -n +1.

Andrew.

	The promising group to look at for each n is an abelian permutation
group of order m = n-1 and degree m which has the desired property that no
non-trivial element fixes anything.   Call this G(m).

	How can I construct such a group?   Say that m is a product of s(i),
(i=1,..I) where s(i) are primes, not necessarily distinct.   Then create an
I-dimensional array, Arr, with size s(i) in the ith dimension.   The generators
of G(n) are the I elements �(i), where �(i) acts on Arr by shifting each point
one unit in the ith direction, rotating cyclically.

	For example, m=4.   4=2x2 so define Arr to be a 2-dimensional array:

	A B
	C D

	Now define �(1) to permute the objects in Arr to

	B A
	D C

	Whilst �(2) permutes the objects in Arr to

	C D
	A B

	G(4) is isomorphic to Klein group of 4 elements.

	Now the problem of finding a projective plane (and hence the problem
of finding an optimal checker pattern for N = m� + m + 1) is solved if we
can find a cyclic ordering of the non-identity elements of G(m) (so we label
the elements A(k) from k=0..m-2) satisfying the spanning condition:

For all w in {1,..,m-1}:
	A(d)A'(d+w) spans all of G(m)\{I} as d varies across G(m)\{I}.

	Orderings are shown below for n= 3 to 10.   No such ordering exists
for n=7, and I suspect that none exists for n=11, or for any larger n=3 mod4,
but I am yet to prove it.   I am also yet to come up with an *algorithm* for
labelling G(m) when I>1.

	Projective planes for small m.   p is an element of order m.   x,y,z
are of order 2.   a,b are of order 3.   To convert these into checker patterns,
follow the style of the patterns given for the smallest examples, which appear
in earlier replies.

n=3:
k:	0
A:	p

n=4:
k:	0	1
A:	p	p^2

n=5:
k:	0	1	2
A:	x	y	xy

n=6:
k:	0	1	2	3
A:	p	p^2	p^4	p^8 (=p^3)

n=7:	Not possible by this technique.

n=8:
k:	0	1	2	3	4	5
A:	p	p^3	p^2	p^6	p^4	p^5

n=9:
k:	0	1	2	3	4	5	6
A:	x	xy	xz	y	yz	xyz	z

n=10:
k:	0	1	2	3	4	5	6	7
A:	a	b	ab	ab�	a�	b�	a�b�	a�b

Andrew.