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