Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Update: As I have just learned, this is called Keleti's perimeter area conjecture.

Prove that if H is the union of a finite number of unit squares in the plane, then the ratio of the perimeter and the area of their union is at most four.

Remarks. If the squares must be axis-aligned, then this is easy to prove. If we replace unit squares with unit circles, then the statement is sharp and true for two (instead of four). The best known bound (to me) is 5.551... by Zoltán Gyenes. There is much more about the problem in his master thesis which you can find here.

share|improve this question
9  
Note how your question is phrased as a command. –  François G. Dorais Feb 13 '10 at 15:30
9  
Don't be so sensitive François! You don't have to answer, even though you were commanded to :-) –  TonyK Feb 13 '10 at 16:17
2  
If you have this thesis, could you scan it and make it available? –  Anton Petrunin Feb 13 '10 at 16:40
1  
If Conjecture 8.3 in Gyenes' Thesis is true, then if (S_1,...,S_n) is an extreme set of unit squares (i.e. perimeter(H)/Area(H)=4 where H is the union of S_1,...,S_n) then every subset of (S_1,...,S_n) is extreme. Can someone prove this property directly (i.e. without characterizing the extreme cases)? –  Pandelis Dodos Feb 17 '10 at 14:54
    
Suppose you have an arbitrary union U of unit squares and another unit square S. Is it possible that the ratio of the length of the part of the boundary of S that is not in U to the area of S\U is greater than 4? I presume it is, or else there would be an easy inductive proof. Or is it that this is essentially the question one wants to answer? –  gowers Mar 13 '10 at 11:15

3 Answers 3

up vote 12 down vote accepted

Disproved by Viktor Kiss and Zoltán Vidnyánszky, see http://arxiv.org/abs/1402.5452

counterexample with 25 squares and ratio about 4.28 from the paper

share|improve this answer
2  
I added a nice figure from their paper; hope you don't mind the edit. –  j.c. Feb 26 at 1:37
    
Sure not, thanks. –  domotorp Feb 26 at 18:16

I have a small observation, which is a construction that only just fails to give a counterexample (and is not something trivial like a single unit square). Take a large n and take a unit square and take the union of the n rotations about its centre through angles of 2π/n. The result is like a circle with a serrated edge. The radius of the circle is $2^{-1/2}$, so its area is π/2. Its perimeter is $2^{1/2}π$, but because of the serration this increases to approximately 2π. Unfortunately, this gives us a ratio of 4-ε. But it seems to indicate that any proof that 4 is the correct ratio will have to be somewhat complicated.

share|improve this answer
    
Yes, I was aware of this. It also shows that the theorem for the square implies it for the disc too. –  domotorp Mar 14 '10 at 8:23

I cannot give a full proof, but I can reduce the problem to another one that I think some people might know the answer to.

Here is the problem:

PROBLEM 1. Let $U$ be an open subset of the unit square with rectifiable boundary. Then $$ P\ge 4A, $$ where $P$ is the length of the boundary of $U$ and $A$ is the area of $U$.

"PROOF:" I can prove this if $A\le \pi/4$ and I have a precise idea how to prove it in general.

First assume $A\le\pi/4$, say $A=\pi r^2$ for some $r\le\frac12$. Since the circle minimizes the boundary length for a given area, we get $P\ge 2\pi r$ which gives the claim. (Note that this also works if you assume that the diameter of $U$ is $\le 1$ and so this gives a second proof of Proposition 7.1 in the mentioned thesis.)

If $A>\pi/4$ this proof doesn't work. We have to replace the circle with the corresponding minimizer inside the square. I do not know what this minimizer looks like, somewhat like a balloon you blow up inside a box. But minimal surface people might know and once you know the shape of that set, you can compute the boundary length to solve the problem as above. Q.E.D.

Next I show how to solve the original problem once you have Problem 1. I use induction on the number of squares. For $n=1$ there is nothing to show. We do $n\to n+1$. So let a set $F$ in the plane be given which is the union of $n$ unit squares. Let $A(F)$ be its area and $P(F)$ its boundary length. By induction hyothesis we have $P(F)\le 4A(F)$. Add another unit square $S$, then the boundary length of the new set will be $P(F)+4-P$, where $P$ is the boundary lenght of some open set $U$ inside $S$, more precisely, $U$ is the intersection of the interior of $S$ and the interior of $F$. Anyway, $U$ is the interior of a polygon, hence has rectifiable boundary. The area of $F\cup S$ is $A(F)+1-A$, where $A$ is the area of $U$. Problem 1 now tells us $P\ge 4A$. Together with the induction hypothesis this gives the claim. Q.E.D.

share|improve this answer
    
I am afraid your Problem 1 is true only for convex sets while F is typically non-convex. –  domotorp Mar 13 '10 at 10:42
    
If you prove it for convex sets, you've proven it in general. Because for each area A there is a minimizer of P, that is, a set with area A and minimal boundary length. Now if Problem 1 holds for that minimizer, it holds in general. This minimizer must be convex. –  doug Mar 13 '10 at 13:51
    
"Anyway, U is the interior of a polygon, hence has rectifiable boundary." No, U is the interior of a union of zero or more polygons whose interiors are disjoint. But it's still rectifiable. –  TonyK Mar 14 '10 at 16:22
    
Problem 1 is false, even for convex polygons. Just let U be the whole square, and snip off a small triangle from one corner, with sides x, x, sqrt(2)*x. Then P = 4-(2-sqrt(2))*x, and 4*A = 4-2*x^2, so P < 4A for small enough x. –  TonyK Mar 30 '10 at 12:08
    
Cool counterexample. So I guess one has to restrict Problem 1 to sets U which are intersections of finitely many unit squares. –  doug Mar 30 '10 at 20:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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