28
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 10
    $\begingroup$ Note how your question is phrased as a command. $\endgroup$
    – François G. Dorais
    Commented Feb 13, 2010 at 15:30
  • 9
    $\begingroup$ Don't be so sensitive François! You don't have to answer, even though you were commanded to :-) $\endgroup$
    – TonyK
    Commented Feb 13, 2010 at 16:17
  • 2
    $\begingroup$ If you have this thesis, could you scan it and make it available? $\endgroup$
    – Anton Petrunin
    Commented Feb 13, 2010 at 16:40
  • 1
    $\begingroup$ 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)? $\endgroup$
    – Pandelis Dodos
    Commented Feb 17, 2010 at 14:54
  • $\begingroup$ 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? $\endgroup$
    – gowers
    Commented Mar 13, 2010 at 11:15

3 Answers 3

Reset to default
16
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ I added a nice figure from their paper; hope you don't mind the edit. $\endgroup$
    – j.c.
    Commented Feb 26, 2014 at 1:37
4
$\begingroup$

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\pi/n$. The result is like a circle with a serrated edge. The radius of the circle is $2^{-1/2}$, so its area is $\pi/2$. Its perimeter is $2^{1/2}\pi$, but because of the serration this increases to approximately $2\pi$. Unfortunately, this gives us a ratio of $4-\epsilon$. But it seems to indicate that any proof that $4$ is the correct ratio will have to be somewhat complicated.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, I was aware of this. It also shows that the theorem for the square implies it for the disc too. $\endgroup$
    – domotorp
    Commented Mar 14, 2010 at 8:23
1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I am afraid your Problem 1 is true only for convex sets while F is typically non-convex. $\endgroup$
    – domotorp
    Commented Mar 13, 2010 at 10:42
  • $\begingroup$ 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. $\endgroup$
    – user1688
    Commented Mar 13, 2010 at 13:51
  • $\begingroup$ "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. $\endgroup$
    – TonyK
    Commented Mar 14, 2010 at 16:22
  • 1
    $\begingroup$ 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. $\endgroup$
    – TonyK
    Commented Mar 30, 2010 at 12:08
  • $\begingroup$ Cool counterexample. So I guess one has to restrict Problem 1 to sets U which are intersections of finitely many unit squares. $\endgroup$
    – user1688
    Commented Mar 30, 2010 at 20:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .