1 rectangle <= 4 squares

Question

Almost 25 years ago a professor at Indiana U showed me the following problem:

given a map $\mathbb{Z}^2\rightarrow\mathbb{R}$ such that the sum inside every square (parallel to the axes) is $\leq1$ in absolute value, prove that the sum inside every rectangle (parallel to axes) is $\leq4$ in absolute value.

It's fun and not too hard to prove. I believe that at the time I was able to show that the upper limit can be improved to 3.975 - but that was a lot harder and I can't say now that this is for sure the case. Also, with a computer search (old TRS 80) I produced an example containing a rectangle of area $3\frac{1}{3}$.

These are some of the questions that come to mind:

• can the upper limit of 4 (or 3.975?) be improved?
• can the lower limit of $3\frac{1}{3}$ be improved?
• any proof/conjecture about the optimal limit?
• do the results extend to maps $\mathbb{R}^2\rightarrow\mathbb{R}$, provided they are "nice" enough?
• are any other generalizations of this problem possible (eg. different tilings of the plane or of other manifolds, or higher dimensions)?

Update 1 (updated 7th March 2010). See answers and comments below for examples achieving ratios as high as 181/48 = 3.7708333...!

Update 2. Here is a sketch of the proof that 4 is an upper limit. A limit of 254/67=3.79104477... is now known (see answers below), but the proof for that needs to be seeded with at least some known limit.

Given a rectangle R of size AxB, with A < B, call it "thin" if $B\geq2A$ or "fat" if $B\leq2A$ (the case B=2A is irrelevant as it is the union of 2 squares). One can draw the 4 squares on the sides of R, either facing outwards (size of envelope = (2B+A)x(2A+B)), or inwards (some spilling out on the opposite sides, size of envelope = (2B-A)xB) - call these the "big-envelope" and the "small-envelope".

Assume that R has sum 4+$\epsilon$ and that every square has sum between -1 and 1. We have 3 cases, all easy exercises to work out:

(1) for any R, the fat (2A+B)x(2B+A) big-envelope will have sum $\leq-4-3\epsilon$.

(2) for a fat R, a (2A-B)x(2B-A) sub-rectangle of the small-envelope will have sum $\leq-4-3\epsilon$;

(3) for a thin R, a thin (B-2A)x(2B-A) sub-rectangle of the small-envelope, will have sum $\geq4+3\epsilon$;

Applying any of (1)+(2), (2)+(1) or (3)+(3) produces a 3Ax3B rectangle with sum $\geq4+9\epsilon$. Iterating n times produces a $3^{n}A \times 3^{n}B$ rectangle with sum $4+9^{n}\epsilon$. Such rectangle is made of no more than AxB squares (each of size $3^{n} \times 3^{n}$) and therefore, for large enough n, one of the squares will have sum >1. $\square$

Reformulation . Given an abelian group G and a map

f: GxGxGxG -> $\mathbb{R}$ such that

1) -1<=f(a,b,c,d)<=1 if d*a=c*b (boundedness of squares),

2) f(a,b,c,d)+f(c,b,e,d)=f(a,b,e,d) for all a, b, c, d, e in G (horizontal additivity of rectangles),

3) f(a,b,c,d)+f(a,d,c,e)=f(a,b,c,e) for all a, b, c, d, e in G (vertical additivity of rectangles),

can we find a universal best bound b(G) such that -b(G) <= f <= b(G)?

All the previous work on this question amounts to the result: 181/48 <= b($\mathbb{Z}$) <= b($\mathbb{Z}x\mathbb{Z}$) <= 254/67

For non-abelian groups one could perhaps generalize the notion of "square" by lifting it from G/[G,G].

Answer 1

A computer search led to the following 16x16 example with a 7/2 rectangle in the middle (scale everything by 1/12):

 0  -3   3   0   0   0   0   0   0   0   0  -6   6   0   0   0
-1   1  -3   0   3   3  -3   0   0  -3   0   6   0  -3   0   0
 4   2   0   0 -12   9  -3   0   0   0   9 -12   0  -3   6   0
-6   0   0   0   6 -12  12  -6   0  12 -12   3   3   2  -2  -6
 6   0   0   0   6   0 -12   6  12 -12   0   3   2  -1  -4  12
-3   0   0   0  -3   2  -2   0  -6   6  -6  12  -5  -7   0   0
 0   0   0   0   3   4  -4  -6   0 -12  12  -6   0  12   0  -6
 0   0   0   0  -6 -12  12   6  12  12 -12  -6   0   0   0   0
 0   9  -6   0   6   2  -2  -4  -2 -10  10   0   5  -9  -2   0
 3  -3   0   0   0   4  -4  -2  -4   4  -4   6   0   4   2  -6
 0  -6   6   0   0   0 -12   6  12 -12   0  -3  -2   1   4   6
-6   0   0   0   6 -12  12   2  -8  12 -12   3   3   0   0  -6
 8   0  -6   4 -12   9   3  -5  -1   0   9  -6  -4   4   0   3
 0   0   0  -4   4   0   0   3  -7   0   3   1  -2  -1  -4   3
-2   0   3  -1   0   3   0  -1   2   0  -6  -1   7   0   0   0
-3   0   6   1   0  -4   0   1  -1  -3   3   0   0   0   0   0 

Update : using Leonid's remark on imposing symmetry w.l.o.g., here is a smaller and symmetric 13x16 example with a 7/2 rectangle (scale by 1/4):

 0  0  0  0  1 -1  0  0  0  0 -1  1  0  0  0  0
 1  0  0 -2 -2  4 -1  0  0 -1  4 -2 -2  0  0  1
-2  0  0  2  0 -4  4 -1 -1  4 -4  0  2  0  0 -2
 1  0  0  0  0  0 -4  3  3 -4  0  0  0  0  0  1
 0  0  0  0  0  0  0 -1 -1  0  0  0  0  0  0  0
 0  0  0  0  2  2 -2 -1 -1 -2  2  2  0  0  0  0
 0  0  0  0 -2 -4  4  3  3  4 -4 -2  0  0  0  0
 0  0  0  0  2  2 -2 -1 -1 -2  2  2  0  0  0  0
 0  0  0  0  0  0  0 -1 -1  0  0  0  0  0  0  0
 1  0  0  0  0  0 -4  3  3 -4  0  0  0  0  0  1
-2  0  0  2  0 -4  4 -1 -1  4 -4  0  2  0  0 -2
 1  0  0 -2 -2  4 -1  0  0 -1  4 -2 -2  0  0  1
 0  0  0  0  1 -1  0  0  0  0 -1  1  0  0  0  0 

I also tried to find an example with a ratio better than 7/2, keeping the symmetry and a 1x4 rectangle in the middle, but could not find any (the largest size I am able to check is 33x38).

Answer 2

The upper bound is <3.95.

I hope the code below will show correctly...

It proves that assuming a sum >=3.95 in the central AxB rectangle of the grid ({-B,-B+A,-2A,-A,0,A,2A,B-A,B}+{0,A}) x ({-2B,-B-A,-B,-B+A,-2A,-A,0,A,2A,B-A,B,B+A,2B}+{0,B}) leads to a contradiction in a finite number of steps. 3.95 is NOT best possible for this grid, but 3.94 does not lead to a contradiction. It will be easy to refine the number, but more worthwhile is probably to search a larger grid (which starts to get slow in awk.)

awk 'BEGIN {

 A=1;
 # pick B large enough to ensure that there
 # are no accidental squares in the grid below
 B=1000;

 # setting up the grid
 x[0]=-B;       x[1]=-B+A;
 x[1]=-B+A;     x[2]=-B+2*A;
 x[3]=-2*A;     x[4]=-A;
 x[4]=-A;       x[5]=0;
 x[5]=0;        x[6]=A;
 x[6]=A;        x[7]=2*A;
 x[7]=2*A;      x[8]=3*A;
 x[9]=B-A;     x[10]=B;
 x[10]=B;       x[11]=B+A;
 M=11;

 y[0]=-2*B;     y[2]=-B;
 y[1]=-B-A;     y[5]=-A;
 y[2]=-B;       y[6]=0;
 y[3]=-B+A;     y[7]=A;
 y[4]=-2*A;     y[9]=B-2*A;
 y[5]=-A;       y[10]=B-A;
 y[6]=0;        y[11]=B;
 y[7]=A;        y[12]=B+A;
 y[8]=2*A;      y[13]=B+2*A;
 y[10]=B-A;     y[14]=B+B-A;
 y[11]=B;       y[15]=B+B;
 y[12]=B+A;     y[16]=B+B+A;
 y[15]=2*B;     y[17]=3*B;
 N=17;

 for(i=0; i<=M; i++)
     for(j=i; j<=M; j++)
         for(k=0; k<=N; k++)
             for(l=k; l<=N; l++)
                 # 0 sum for degenerate rectangles
                 if(i==j || k==l) {
                     lo[i,j,k,l]=0;
                     hi[i,j,k,l]=0;
                 }                   
                 # squares
                 else if(x[j]-x[i]==y[l]-y[k]) {
                     lo[i,j,k,l]=-1;
                     hi[i,j,k,l]=1;
                 }
                 # other rectangles
                 else {
                     lo[i,j,k,l]=-4;
                     hi[i,j,k,l]=4;
                 }

 # central rectangle: assume its sum is >=3.95
 lo[5,6,6,11]=3.95;

 iter=10000;
 active=1;
 while(iter-- && active) {
     active=0;

     # traverse all possible combinations of 1 rectangle split into 4
     for(i=0; i<M; i++)
         for(j=i+1; j<=M; j++)
             for(k=0; k<N; k++)
                 for(l=k+1; l<=N; l++)
                     for(m=i; m<j; m++)
                         for(n=k; n<l; n++) {
                             lo0=lo[i,j,k,l];
                             lo1=lo[i,m,k,n];
                             lo2=lo[m,j,k,n];
                             lo3=lo[i,m,n,l];
                             lo4=lo[m,j,n,l];
                             hi0=hi[i,j,k,l];
                             hi1=hi[i,m,k,n];
                             hi2=hi[m,j,k,n];
                             hi3=hi[i,m,n,l];
                             hi4=hi[m,j,n,l];

                             # 3rd argument in max() and min() funtions
                             # is for printing purposes only...
                             lo0=max(lo0, lo1+lo2+lo3+lo4, 0);
                             hi0=min(hi0, hi1+hi2+hi3+hi4, 0);
                             lo1=max(lo1, lo0-hi2-hi3-hi4, 1);
                             lo2=max(lo2, lo0-hi1-hi3-hi4, 2);
                             lo3=max(lo3, lo0-hi1-hi2-hi4, 3);
                             lo4=max(lo4, lo0-hi1-hi2-hi3, 4);
                             hi1=min(hi1, hi0-lo2-lo3-lo4, 1);
                             hi2=min(hi2, hi0-lo1-lo3-lo4, 2);
                             hi3=min(hi3, hi0-lo1-lo2-lo4, 3);
                             hi4=min(hi4, hi0-lo1-lo2-lo3, 4);

                             if(lo0>hi0 || lo1>hi1 || lo2>hi2 || lo3>hi3 || lo4>hi4) {
                                 print "CONTRADICTION AT", i,m,j,k,n,l;
                                 exit;
                             }

                             lo[i,j,k,l]=lo0;
                             lo[i,m,k,n]=lo1;
                             lo[m,j,k,n]=lo2;
                             lo[i,m,n,l]=lo3;
                             lo[m,j,n,l]=lo4;
                             hi[i,j,k,l]=hi0;
                             hi[i,m,k,n]=hi1;
                             hi[m,j,k,n]=hi2;
                             hi[i,m,n,l]=hi3;
                             hi[m,j,n,l]=hi4;
                         }
 }
 print "FINISHED OK";
}

function max(s,t, where) {

if(s<t) {
    print "lo=" t, "for", i,m,j,k,n,l, "(" where ")";
    active=1;
    s=t;
}
return(s);
}

function min(s,t, where) {

if(s>t) {
    print "hi=" t, "for", i,m,j,k,n,l, "(" where ")";
    active=1;
    s=t;
}
return(s);
}
'

Answer 3

Latest figures

FG has posted a solution for the 12x1 rectangle, attaining 181/48 = 3.3.7708333...

More results:
11x1 rectangle is 101/27 = 3.740740...
7x3 rectangle is 56/15 = 3.733333...
7x2 rectangle is 67/18 = 3.722222...
8x1 rectangle is 26/7 = 3.714285...
6x1 rectangle is 85/23 = 3.695652...
7x1 rectangle is 11/3 = 3.666666...
5x1 rectangle is 25/7 = 3.571428...

I have removed specific solutions from this answer, as they have been superseded by FG's results.

Answer 4

I remember reading about this in the Geometric Discrepancy book of Matousek. Another way of putting your statement is that if the discrepancy of squares is small, then so is that of rectangles. I think that the higher dimensional version of expressing the characteristic vector of a brick with characteristic vectors of cubes is still open. Here is a recent related paper that might be interesting for you to find the exact bound for your question: http://www.maths.qmul.ac.uk/~walters/papers/rectangles-as-sums-of-squares.pdf

Answer 5

Here is a quick description of the linear programming formulation I used to compute some configurations:

Given a $m \times n$ grid $G$, one can describe a configuration with a real vector $x \in \mathbb{R}^{mn}$. Then, for each square featuring a nonempty intersection with $G$, one can write down an indicator vector $a_i \in \mathbb{R}^{mn}$ ($i \in S$), whose components are equal to $1$ if in the square, and $0$ otherwise. Finally, one can write $c \in \mathbb{R}^{mn}$, the indicator of the rectangle whose sum is to be maximized.

The linear program is then $$ \max_{x \in \mathbb{R}^{mn}} c^T x \text{ such that } -1 \le a_i^T x \le 1\ \forall i \in S$$ This type of program can be solved extremely efficiently up to relatively large sizes $mn$ (I am using the ILOG CPLEX solver).

Taking into account the symmetry is straightforward: if you want several components of $x$ to be equal to each other, only keep one of them and adapt the remaining coefficients in $c$ and $a_i$ (i.e. replace them with the sum of the corresponding coefficients).

However, this approach has limitations because there are a lot of vectors $a_i$, and those vectors have sometimes a lot of nonzero components (which has an influence on the efficiency of the solver and crucially on the memory used). I was only able to use it up to around a $45\times 45$ grid.

To obtain solutions for larger sizes, I used the following trick: instead of defining variable $x_{ij}$ for the content of the $(i,j)$ cell in the grid, I define variable $y_{i,j}$ as follows $$ y_{i,j} = \sum_{1\le k\le i, 1\le l \le j} x_{k,l}.$$ Then it can be checked that the sum of the square or rectangle with opposite corners $(a,b)$ and $(c,d)$ is equal to $y_{c,d}+y_{a-1,b-1}-y_{c,b-1}-y_{a-1,d}$. This means each constraint in the corresponding linear program will have at most $4$ nonzeros, which improves a lot the speed and memory requirements of the solver.

By the way, I will put my latest results in the link http://dl.dropbox.com/u/217239/sol_rectangle.html

The current largest solution ($56/15$ for a $3\times 7$ rectangle), is made of fractions with common denominator 120, but this is just a happy coincidence, for nothing forces that in the linear program (and, as remarked by TonyK, enforcing it explicitly would be very costly).

Update I have run an extensive set of runs for rectangle sizes below 20x20 and put the results at the end of the file linked above. The record is still $56/15$, which is attained by many rectangles (notably by the $1 \times 9$ on a $101\times 109$ grid). It seems like even larger grids will be needed to obtain larger sums.

Update2 $1 \times 11$ in a $137 \times 63$ grid gives $101/27$=3.7407407

Update3 $1 \times 12$ in a $155 \times 68$ grid gives $15/4$=3.75

Unfortunately, I can only check $1 \times 13$ up to around $191\times 77$, which still gives 3.75, and I seem to have exhausted my tricks for the moment ...

Answer 6

Here is a summary for the $\mathbb{R}^2$ situation.

Upper limit: no improvement over the 3.8 known on $\mathbb{Z}^2$.

To create specific examples I modified the $\mathbb{Z}^2$ ones by uniformely spreading each value on the lattice over a 1x1 square:

3x1: ratio = 3-3/5 (vs. 3 on integers, 7x5 grid)
4x1: ratio = 3-1/5 (vs. 3.5 on integers, 13x16 grid)
5x1: ratio = 3-1/7 (vs. 25/7 on integers, 25x29 grid)
6x1: ratio = 3-1/23 (vs. 85/23 on integers, 31x36 grid)
8x1: ratio = 3-1/35 (vs. 26/7 on integers, 39x46 grid)
7x3: ratio = 3-1/75 (vs. 56/15 on integers, 59x57 grid)
11x1: ratio = 3-1/135 (vs. 101/27 on integers, 137x63 grid)

And the surprises are
1) that in all cases the highest sum on a square is 1.25 that of the integral case (which is the worst case scenario, but I see no obvious reason it should always be that way), and
2) we seem to be approaching 3, suggesting that for the integers perhaps the upper limit could be 3.75 and not 3.8 - but this is of course very highly speculative...

Answer 7

There is a new upper bound of 254/67 (= 3.79104477...).

Define 6 sets of cardinality 4:

X1={-B+A, 0, A, B}
Y1={0, A, B-A, B}

X2={-B, -B+3A, B-2A, B+A}
Y2={-2B+A, -A, B+A, 3B-A}

X3={-6B+2A, -2B-2A, 2B+3A, 6B-A}
Y3={-2B-2A, -B+6A, 2B-6A, 3B+2A}

then we already know that in the in the grid X1 x Y1 if the sum in the central AxB is $4+\epsilon$ the sum in the surrounding (2B-A)x(B-2A) is $\geq4+3\epsilon$,

similarly in the in the grid (X1 $\cup$ X2) x (Y1 $\cup$ Y2) if the sum in the central AxB is $19/5+\epsilon$ then the sum in the surrounding (2B-5A)x(5B-2A) is $\leq-19/5-21\epsilon$,

last, in the in the grid (X1 $\cup$ X2 $\cup$ X3) x (Y1 $\cup$ Y2 $\cup$ Y3) if the sum in the central AxB is $254/67+\epsilon$ then the sum in the surrounding (12B-3A)x(3B-12A) is $\geq254/67+135\epsilon$.

All of the above claims are easily verifiable with the tools already described in the previous answers and comments. I wonder if one can find sets X4 and Y4 (with 4 elements each?) to further improve the bound and maybe spot a general pattern.

Answer 8

Using Yaakov's speed-up, I have run his original program with x-grid {m*A + n*B} + {0,A}, and y-grid {m*A + n*B} + {0, B}, for all m,n with |m| <= 4 and |n| <= 4. The program finds no improvement on 3.8 for a generic rectangle, so it looks (to me, anyway) as if this is the best that can be done using this method.

It also looks like we might be able to approach 3.8 arbitrarily closely with concrete examples, if only we had bigger and faster computers.