42
$\begingroup$

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].

$\endgroup$
17
  • 5
    $\begingroup$ I still found the question hard to understand. Lemme just check: is it the following? given f:Z^2->R with, for all integers i,j and N>=0, |sum_{i<=x<=i+N,j<=y<=j+N}f(x,y)|<=1, then for all i,j and M,N>=0, |sum_{i<=x<=i+N,j<=y<=j+M}f(x,y)|<=4? I'm not saying you should rewrite it like this, I just don't have a very geometric mind. $\endgroup$ Feb 2, 2010 at 13:26
  • 2
    $\begingroup$ Professor's name? $\endgroup$ Feb 2, 2010 at 16:25
  • 3
    $\begingroup$ Hari Berkovici. $\endgroup$ Feb 2, 2010 at 17:20
  • 11
    $\begingroup$ Why not give the proofs for 4 and 10/3? $\endgroup$ Feb 3, 2010 at 0:36
  • 3
    $\begingroup$ I have setup a Google Docs page to record progress on this problem, hopefully we can stop continually updating this page. It is at docs.google.com/View?id=ajkfbpjb4hfn_182c4hq2qfj If you want to help edit the page, send me an email ; by the way, for those following the search for better configurations, there is something new there (a new 1x12 solution ...) $\endgroup$
    – F_G
    Mar 5, 2010 at 23:32

8 Answers 8

13
$\begingroup$

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).

$\endgroup$
14
  • $\begingroup$ twice awesome! (Twice because comments are 15 chars minimum.) $\endgroup$ Feb 7, 2010 at 21:14
  • $\begingroup$ notice that specific AxB rectangles may encounter lower upper bounds than the general case. In particular the above proof of 4 as an upper bound, shows that a sum of 4 for a 4x1 rectangles would imply also a sum of 4 for a 6x9, which is a union of 3 squares. From this one can work out some stricter limit on the 4x1, but I haven't got around to computing it $\endgroup$ Feb 8, 2010 at 12:47
  • $\begingroup$ Your epsilon doesn't have to be positive, right? So if a 4x1 rectangle has sum >= 4 - epsilon, then the 6x9 rectangle has sum >= -4 + 3*epsilon, which is impossible if epsilon < 1/3. So a 4x1 rectangle has sum <= 11/3. The same is true for 7x8 (because (2A-B)x(2B-A) = 6x9) and 1x5 (because (B-2A)x(2B-A) = 3x9). $\endgroup$
    – TonyK
    Feb 9, 2010 at 10:17
  • 1
    $\begingroup$ A 1x4 cannot have sum more than 7/2, i.e. FG's example is best possible for 1x4. This can be seen working inside the 9x6 envelope... use the fact that the 4x2 which includes (and is limited on a side by) the 2 central units of the 1x4, has sum <=2. $\endgroup$ Feb 11, 2010 at 13:09
  • 1
    $\begingroup$ Write AxB+C+D for R with vertices (C,D), (C+A,D), (C,D+B), (C+A,D+B). Now let R=1x4+3+0. Then 1x1+3+0=1x1+3+3=1-a, 1x1+3+1=1x1+3+2=1-b, 4x4+0+0=1-e and 3x3+0+0=3x3+0+1=-1+g, for a,b,e,g>=0. Then work out that 4x2+0+1=3-2a-4b+e+2g but any 4x2<=2 implies 2a+4b>=1, implies 2a+2b>=1/2, implies R=4-2a-2b<=7/2. $\endgroup$ Feb 11, 2010 at 16:34
10
$\begingroup$

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);
}
'
$\endgroup$
16
  • $\begingroup$ This a preemptive comment: one could argue that I'm proving the result only for thin enough rectangles (as hinted by my pick of a huge B=1000). However this is not essential. If one thinks in term of "negative rectangles" it is easy to see that set of constraints imposed by the key decomposition of one rectangle in 4 sub-rectangles, remains the same. $\endgroup$ Feb 26, 2010 at 9:03
  • 1
    $\begingroup$ I have used your program to do a binary search for the limiting value. For the grid that you use, it turns out to be exactly 154/39 = 3.9487... $\endgroup$
    – TonyK
    Feb 26, 2010 at 10:34
  • 1
    $\begingroup$ Another update: assuming the already proven limits of -3.95 and +3.95 for all rectangles, then 3.945 is a limit! (This works even with the original 12x18 grid.) $\endgroup$ Feb 26, 2010 at 11:56
  • 1
    $\begingroup$ Now I am using generated grids: the x-grid is {mA + nB} + {0,A}, and the y-grid is {mA + nB} + {0, B}, for all m,n with |m| <= L and |n| <= L, for some parameter L. With L = 2, we get a 30x30 grid, and the iteration process results in a bound of 19/5 = 3.8 (!). I am going to try L=3, but it will be slow... $\endgroup$
    – TonyK
    Feb 27, 2010 at 17:07
  • 1
    $\begingroup$ I just realized (fun exercise) that the set of inequalities derived from decomposing rectangles into 2 in all ways (cutting vertically or horizontally) imply the set of inequalities derived from splitting rectangles into 4. Since the first approach involves 5 nested loops instead of 6, it is MUCH faster for large grids. For a medium grid I timed a speed improvement 6x. $\endgroup$ Mar 1, 2010 at 22:07
10
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ TonyK, this is great ! I thought for a while that 3.5 could not be beaten, but I was looking at wrong (central rectangle/grid) size combinations (mostly too small grids). $\endgroup$
    – F_G
    Mar 2, 2010 at 2:08
  • $\begingroup$ As far as I can check, 25/7 can also be obtained on a smaller 23x29 grid ; 31x36 seems optimal for 85/23. $\endgroup$
    – F_G
    Mar 2, 2010 at 3:17
  • $\begingroup$ Yes, LK, the upper bounds are proved. (But the program uses floating-point arithmetic. For a proper computer-assisted proof, I suppose it would need to use rationals.) $\endgroup$
    – TonyK
    Mar 2, 2010 at 7:52
  • 1
    $\begingroup$ TonyK, I can confirm 26/7 is possible for a 1x8 rectangle within a 39x46 grid. Maybe we can discuss how we obtain those grids ? I use a linear programming formulation (a variable for every cell, a constraint for every square), which is quick (optimally solved in less than a minute) but runs out of memory around the 45x45 size (too many squares - it should be possible to remove some redundancies). $\endgroup$
    – F_G
    Mar 2, 2010 at 11:35
  • $\begingroup$ Once you have a consistent and non-improvable set of bounds, you can collapse one interval to a point within, one rectangle at a time, then refresh the set of bounds and repeat the procedure until all intervals have shrunk to a point. Unfortunately, I don't know if one can also collapse the 3 (or 1) symmetric images of the chosen rectangle without a refresh in between. $\endgroup$ Mar 2, 2010 at 11:40
6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ The paper seems related to the topic, but not useful to providing any bounds, because here squares and rectangles can form equations with signs and multiplicities, while in the paper they only form disjoint unions $\endgroup$ Feb 4, 2010 at 12:11
  • 2
    $\begingroup$ They discuss the "plus/minus problem" as well: We prove polylogarithmic (C(log n)d) upper and lower bounds for the number of hypercubes needed to tile a hypercuboid in either of the above senses. In more than two dimensions this is a huge improvement on anything previously known. It was not even known whether an n × 1 × 1 cuboid could be tiled with fewer than n cubes in the plus/minus sense. (page 3) $\endgroup$ Feb 4, 2010 at 13:05
5
$\begingroup$

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 ...

$\endgroup$
7
  • $\begingroup$ I can confirm that FG's 3x7 solution attains 56/15. Well done! $\endgroup$
    – TonyK
    Mar 2, 2010 at 21:27
  • $\begingroup$ the update is impressive. Shouldn't it be part of an update to the main question itself? $\endgroup$ Mar 3, 2010 at 11:53
  • $\begingroup$ I can confirm the 101/27 result. I also checked the real case (no surprises) and I'm updating the related post. $\endgroup$ Mar 3, 2010 at 13:49
  • $\begingroup$ I can confirm your new 15/4 result for the 12x1 rectangle. (And your first two rows are all zero, so the rectangle is really 157x82.) $\endgroup$
    – TonyK
    Mar 3, 2010 at 21:54
  • 1
    $\begingroup$ I can confirm your latest result for the 12x1 rectangle in a 241x126 grid. (And the first five rows are all zero, so the grid is really 231x126.) 181/48 = 3.7708333...! That's more than 3.75, isn't it? :-) $\endgroup$
    – TonyK
    Mar 7, 2010 at 22:44
4
$\begingroup$

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...

$\endgroup$
5
  • $\begingroup$ I bet you it's 3.8. $\endgroup$
    – TonyK
    Mar 2, 2010 at 22:21
  • $\begingroup$ An idea: if L=4 there are rectangles of size Ax4A, 4AxA, Bx4B and 4BxB on which we can impose the known limit of 3.5, rather than 3.8 - well, that won't help any because the proof of a 3.5 on a 4x1 was all contained in a 4x4, and the L=4 grid contains the 4Ax4A and 4Bx4B needed for the proof! However, and THIS is the idea, if L=5 in one direction, the limit of 25/7 for Ax5A etc. is not contained in the grid and so imposing that could add the extra oomph to break the 3.8 barrier. I'd try L=2 in one direction and L=5 in the other, with those 25/7 limits... Even if that fails, I bet on 3.75. $\endgroup$ Mar 2, 2010 at 22:52
  • $\begingroup$ I also bet on 3.75 (and have for the moment nothing better to report than 56/15 on the lower bound front). $\endgroup$
    – F_G
    Mar 2, 2010 at 23:14
  • $\begingroup$ Correction: there are of course Ax5A and similar rectangles for L=3 (since m,n range from -3 to +3). Also, the limits 2 on Ax2A, 3 on Ax3A, 3.5 on Ax4A etc., while achievable by the program, nonetheless could make it run faster if imposed from the outset. $\endgroup$ Mar 2, 2010 at 23:58
  • $\begingroup$ I have just tried L=3 in one direction and L=5 in the other, and I still get 3.8. $\endgroup$
    – TonyK
    Mar 3, 2010 at 0:17
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I can confirm this result. Amazing! How did you find these grids? $\endgroup$
    – TonyK
    Mar 9, 2010 at 9:44
  • $\begingroup$ @Tony, 1 and 2 by stripping down unnecessary grid points from the known results, and 3 by then trying to extrapolate 1 and 2, overshooting big and stripping down again after (which is what I've been trying towards X4,Y4 without success). The sequence 4,4,4 by the way may be misleading... the 1st set X1 maybe should be regarded as X0={0,A} U X1'={-B+A,B}, which makes the sequence 2,2,4,4 and suggests that X4,Y4 could have 6 or 8 points each, not 4. More far fetched speculation: the sequence 3, 21, 135 looks like 2^2-1, 3*(2^3-1), 9*(2^4-1)... $\endgroup$ Mar 9, 2010 at 18:39
1
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.