Benoit Jubin, Improved lower bound for A250000
==============================================
Posting to Sequence Fans Mailing List, Feb 24 2015
with comments from Ron Pratt and Bob Selcoe.
(Partially edited by N. J. A. Sloane, Nov 18 2018.)

----------------------------------------------
Benoit Jubin, Feb 24 2015:
Let a(n)=A250000(n) be the maximum size of coexisting armies of queens on
an (n,n) chessboard.

By modifying the Pratt--Selcoe configuration, I improved the best known
lower bound from
a(n) > (9/4)*(n/4)^2
to
a(n) > (7/3)*(n/4)^2.
I have been sloppy with side effects, but to be on the safe side, let's say
a(n) > (7/3)*(floor(n/4))^2 - (3+8*sqrt(2)/3)*ceiling(n/4), where the
coefficient 3+8*sqrt(2)/3 is a perimeter that you can compute from the
following description.

The configuration in the limit n = infinity is as follows: denoting by x,y
in [0,1] the coordinates on the chessboard, the queens of one color are in
the two regions
x<1/4, y<1/2, x<y<x+1/3
and
1/2<x<3/4, y<x-1/3, y<1-x
and the queens of the other color are obtained by central symmetry. As you
can guess, I obtained these coefficients by equalizing the lengths of the
"opposite" boundaries of the armies (this already improves (by 1) on the
"Board 4" example of the webpage).

Using an easy upper bound, one has asymptotically
(2+1/3)*(n/4)^2 < a(n) < 4*(n/4)^2.
Would anyone like to help fill the gap?

----------------------------------------------


Rob Pratt, Feb 24 2015:
Please share your n =24 solution.  Under the central symmetry constraint, I get a maximum of 80, not 84.

----------------------------------------------

Benoit Jubin, Feb 24 2015:
Dear Rob,
I improved by one the final board on the webpage by using the same idea as
for my asymptotic bound, but you are right that in this specific case, the
result is not centrally symmetric. From the last example on the webpage, I
made marginal changes along the diagonals (in the [0,1]^2 coordinates)
y=x+1/3 (deleted 3 Ws, added 5 Bs) and y=x-1/3 (deleted 4 Bs, added 4Ws):

......WWWWWW............
......WWWWWW...........W
......WWWWWW..........WW
......WWWWWW.........WWW
......WWWWWW........WWWW
......WWWWW........WWWWW
.......WWW........WWWWWW
........W.........WWWWWW
..................WWWWWW
..................WWWWW.
..................WWWW..
..................WWW...
....BB..................
...BBB..................
..BBBB..................
.BBBBB..................
BBBBBB..........B.......
BBBBBB.........BBB......
BBBBBB........BBBB......
BBBBB........BBBBB......
BBBB........BBBBBB......
BBB.........BBBBBB......
BB..........BBBBBB......
B...........BBBBBB......


----------------------------------------------

Bob Selcoe, Feb 25 2015:
Excellent!  This certainly is an improvement.

But I'm having a little difficulty following how you've obtained the upper 
and lower bounds, as well as your description of coordinates.

So for my n=24 a(n)=83 board, wouldn't you also say the queens of one color 
are in the two regions x<1/4, y<1/2, x<y<x+1/3
and 1/2<x<3/4, y<x-1/3, y<1-x, while the queens of the other color are 
obtained by central symmetry (or at least something approximating central 
symmetry)???

So I don't see how the definitions between your and my configurations 
differ; that is, when you say:

>> I obtained these coefficients by equalizing the lengths of the "opposite" 
>> boundaries of the armies  (this already improves (by 1) on the "Board 4" 
>> example of the webpage).

I'm not sure what you "equalized" to gain the improvement.

But still, there is definite improvement.

I probably won't have time to look into a structural pattern for n = 4m for 
several days; my guess is one exists based on your approach, which will 
improve upon mine.  Will you have a chance to see if such a pattern exists?


----------------------------------------------

Benoit Jubin, Feb 25 2015:

Dear Bob 
I think that you interpret the coordinates correctly. My configuration is
only a slight modification of yours, but not exactly the same, as you can
see in my example for n=24 (in a previous email of this conversation).
Also, the bound you give on the webpage, namely (after simplification),
a(4m) >= floor( (9/4)*m^2 + m/2 - 3/4 )
made me think that your configuration is given as follows (for n=4m):
One decomposes the chessboard into 16 smaller (m,m) chessboards as follows:
.A.B
.C.D
W.X.
Y.Z.
where the dots are empty chessboards and
A, B, C, D contain the queens of one color
and
W, X, Y, Z contain the queens of the other color.
Borrowing to the language of matrices, the occupied squares are as follows:
A: all squares,
B: strict lower-right half,
C: strict upper quarter, that is, intersection of the strict upper-left
half and the strict upper-right half,
D: upper-left half plus the first subdiagonal,
W: lower-right half,
X: intersection of the strict lower-right half minus the first subdiagonal
and the lower-left half,
Y: upper-left half,
Z: all squares minus the upper-left one.

What I meant by "equalizing the opposite boundaries" is this: in the picture

....|....|......../
....|....|......./.
....|....|....../..
....|.../....../...
....|../....../....
.....\/.......|....
..............|....
..............|.../
..............|../.
..--+.........+--..
./..|..............
/...|..............
....|..............
....|......./\.....
..../....../..|....
.../....../...|....
../......|....|....
./.......|....|....
/........|....|....

each of the lines x=1/4, x=1/2, x=3/4, y=1/2, y=x, y=x+1/3, y=x-1/3,y=1-x
borders a white region and a black region, and the length during which it
borders each is equal. This is how I optimized your solution: by
translating these lines, one adds to the army of one color while removing
from the other color (compensate this on the other pair of regions, to
still have equally sized armies), so one deduces that for the optimal
configuration of this sort, "opposite boundaries" must have same length.


I am mainly interested in asymptotics, where it does not matter whether n
is divisible by 4 or not. But for a given n, not necessarily divisible by
4, I would first draw these regions, and for any given square, if more than
half of it is within the region, I would put a queen. For the 50%-squares,
put queens for one out of the two regions. Finally (possibly not needed),
give or take a few queens on the boundaries to get an admissible
configuration.

----------------------------------------------