Polyomino question

[Joseph S. Myers]

On Wed, 1 Mar 2006, David Wilson wrote:

> A couple of variantions on this theme:
> 
> Let a(n) be the size of the smallest polyomino cover for the n-ominoes.
> 
> Any n-omino fits into an n x n square so a(n) <= n^2.  By abutting each omino
> to the bottom and left side of the square, the omino will fit into "right
> isosoceles" polyomino so a(n) <= (n^2+n)/2.  If we also rotate the omino so
> its height does not exceed its width, we can cap it at height ceil(n/2) <=
> (n+1)/2, so that a(n) <= (3n^2 + 4n + 1)/8.  This gives us a(n) is O(n^2) with
> c <= 3/8. I imagine we can do better.  Can we get a(n) to be O(n log n)?

I think a(n) asymptotically exceeds n^(2-epsilon) for any positive 
epsilon.

Consider epsilon = 1/k for some positive integer k, and suppose n 
sufficiently large.  We consider polyominoes consisting of a straight line 
of squares of length n/2, with 2k+2 columns (each of length n/4(k+1)) 
sticking out on one side.

O O O O O O
O O O O O O
OOOOOOOOOOOO

OO  O OO   O
OO  O OO   O
OOOOOOOOOOOO

etc.

There are about (n/2 choose 2k+2)/2 such polyominoes.  Let P be the cover 
of size a(n) <= n^2.  Each polyomino can appear in at most 8a(n) <= 8n^2 
possible positions/orientations in P.  Thus some (n/2 choose 2k+2)/16n^2 = 
(n/2)^2k / (64((2k+2)!)) of the polyominoes are present in P with the same 
orientation and base line of length n/2.  If that subset of the 
polyominoes uses m columns then (m choose 2k+2) = m^(2k+2) / (2k+2)! >= 
(n/2)^2k / (64((2k+2)!)), i.e. m >= ((n/2)^2k / 64)^(1/(2k+2)).  Thus a(n) 
>= m(n/4(k+1)) = (c)(n^(2-1/(k+1))), for c a constant depending on k, and
this exceeds n^(2-1/k) for n sufficiently large.

-- 
Joseph S. Myers
jsm at polyomino.org.uk