\input amstex \documentstyle{amsppt} \NoBlackBoxes \magnification 1200 \hsize 6.5truein \vsize 8truein \topmatter \title On the self crossing six sided figure problem \endtitle \author Nets Hawk Katz \endauthor \affil University of Illinois, Chicago \endaffil \subjclass 42B25 \endsubjclass \thanks The author was supported by EPSRC GR/l10024 \endthanks \endtopmatter \head Introduction \endhead The purpose of this paper is to prove the following theorem. We say that four points in $\Bbb R^2$ are the vertices of an axis parallel rectangle if they are of the form $(x_1,y_1),(x_1,y_2),(x_2,y_1),(x_2,y_2)$ with $x_1 \neq x_2$ and $y_1 \neq y_2$. We say that the area of the rectangle is $|x_1-x_2||y_1-y_2|$. We say that six points in $\Bbb R^2$ are the vertices of a right angled, axis parallel hexagon (possibly self-crossing) if they are of the form, $(x_1,y_2),(x_1,y_3),(x_2,y_1),(x_2,y_3),(x_3,y_1),(x_3,y_2)$ with $x_1,x_2,x_3$ pairwise distinct and with $y_1,y_2,y_3$ pairwise distinct. We say that the area pf the hexagon is $A=\max(|x_i-x_j|) \min(|y_i-y_j|) + \max(|y_i-y_j|) \min (|x_i-x_j|)$. While not exactly the geometrical area (by which we mean the absolute area rather than the oriented area), the quantity $A$ is comparable to it. \proclaim{Theorem} There exists a constant $C>0$ so that whenever $E \subset [0,1] \times [0,1]$ is a set which does not contain the vertices of any axis parallel rectangle with area greater than $\epsilon^2$ and does not contain the vertices of any axis parallel hexagon with area greater than $\epsilon^2$ then $|E| \leq C \epsilon$. \endproclaim We explain the motivation of the theorem, which arose in the study of Fourier integrals. Carbery, Christ, and Wright [CCW] were studying the sublevel sets of phase functions for Fourier integral operators. They were looking for higher dimensional analogues of the statement that a real valued function $f$ on the reals satisfying $f^{\prime} > \lambda$ has small sublevel sets. (I.e. the set of $x$ for which $|f(x) \leq 1|$ has measure smaller than ${2 \over \lambda}$.) This fact is the underlying idea behind Van der Corput's Lemmas and the method of stationary phase, (see [S], Chapter 8). They observed that a function $f$ on the unit square in $\Bbb R^2$ satisfying ${\partial^2 f\over \partial x \partial y} > \lambda$ must satisfy the estimate $$|\{(x,y): |f(x,y)| \leq 1\}| \leq C{\sqrt{\log \lambda} \over \sqrt{\lambda} }. \tag -1$$ The question arose whether (-1) is sharp. A simple example shows one can find such an $f$ for which the sublevel set is as large as ${1 \over \sqrt{\lambda}}$. The question, as is often the case, is whether the log is really there. This question is open. The question is related to another more geometrical question. Suppose we are given a set $E$ with the property that it does not contain the vertices of any axis parallel rectangle with area larger than $\epsilon^2$. We then trivially have the estimate $$|E| \leq C \epsilon \sqrt{\log {1 \over \epsilon}}. \tag -2$$ The question is again whether the log is really there. The estimate (-2) implies the estimate (-1). We may see this by letting $E$ be the sublevel set, by letting $\lambda={1 \over \epsilon^2}$. We see that $E$ satisfies the geometric condition we have stated by integrating $d \omega$ over any axis parallel rectangle with vertices in the set, where $\omega$ is the one form $$\omega={\partial f \over \partial x} dx -{\partial f \over \partial y}dy.$$ The same argument shows that when $E$ is the sublevel set of $f$, it satisfies more stringent geometrical conditions. Indeed it cannot contain the vertices of large non self-crossing axis parallel hexagons. (Or for that matter $2n$-sided polygons where large depends inversely on $n$.) One might suppose that with the exclusion of these six sided polygons, one might improve (-2) which would imply an improvement of (-1). This, unfortunately, is also an open problem. The theorem we prove says that when we exclude also those axis parallel hexagons which are not polygons, i.e. those which self-cross, one gets the sharp improvement on (2). \head \S 1 Proof of the Theorem \endhead The main point of the proof is the following jigsaw puzzle lemma. \proclaim{Lemma} There exists a universal constant $C>0$ so that for any large $N$, one has that if $A_1,\dots,A_K,B_1,\dots, B_K$ satisfying $${1 \over N^{1 + {1 \over 100}}} \leq |A_j|,|B_j| \leq {1 \over N} \tag 1.$$ and further that if $A_j \cap A_k \neq \emptyset$ then $B_j \cap B_k = \emptyset$ and if $B_j \cap B_k \neq \emptyset$ then $A_j \cap A_k = \emptyset,$ further still if $A_j \cap A_k \neq \emptyset,$ and $A_k \cap A_l \neq \emptyset$ then $B_j \cap B_l =\emptyset$ and analogously if $B_j \cap B_k \neq \emptyset$ and $B_k \cap B_l \neq \emptyset$ then $A_j \cap A_l =\emptyset$ and finally if we have $$|A_j \cap A_k|, |B_j \cap B_k| \leq {1 \over |j-k|},\tag 2$$ then we reach the following conclusion: We have $$K \leq C N^{2-{1 \over 100}}.$$ \endproclaim In proving the jigsaw puzzle lemma, we will frequently make use of the following proposition. \proclaim{Proposition X} Let $a_1, \dots,a_N$ be nonnegative real numbers. Suppose that for all $j$, one has $$a_j< M.$$ Suppose further that $$\sum_{j=1}^N a_j > S.$$ Then there exist at least ${S \over 2M}$ values of $j$ for which $$a_j \geq {S \over 2N}.$$ \endproclaim \demo{Proof} Define $\Cal G$ to be the subset of $\{1,\dots,N\}$ so that for any $j \in \Cal G$, one has $a_j \geq {S \over 2N}$. One has $$\sum_{j \in \Cal G} a_j \geq {S \over 2}.$$ But since each $a_j$ is bounded above by $M$, we have $$\#(\Cal G) \geq {S \over 2M}.$$ \qed \enddemo \demo{Proof of jigsaw puzzle lemma} We suppose the Lemma is false. Then $K \geq C N^{2-{1 \over 100}}$. (By the pairwise disjointness of the product sets $A_j \times B_j$, however, we certainly have $K \leq N^{2 +{2 \over 100}}.$) Now, we have that $$\sum_{j=1}^K |A_j| \geq {K \over N^{1 +{1 \over 100}}} \geq N^{49 \over 50},$$ but $$\eqalign{&\sum_{j=1}^K |A_j| \cr &=\sum_{j=1}^K \int_0^1 \chi_{A_j}(x) dx \cr &=\int_0^1 (\sum_{j=1}^K \chi_{A_j}(x)) dx \cr &\leq (\int_0^1 (\sum_{j=1}^K \chi_{A_j}(x))^2 dx)^{{1 \over 2}} \cr &\leq (\sum_{j=1}^K \sum_{k=1}^K |A_j \cap A_k|)^{{1 \over 2}}.}$$ We conclude $$\sum_{j=1}^K \sum_{k=1}^K |A_j \cap A_k| \geq K^2 {1 \over N^{2 + {1 \over 50}}}. \tag 1$$ Fixing $j$ arbitrary, we observe that $$\sum_{k=1}^K |A_j \cap A_k| \leq \sum_{k=1}^K {1 \over |j-k|} \leq \log N \leq C^{{1 \over 2}} N^{{1 \over 100}}. \tag 2$$ Now combining (1), (2), and Proposition X, we conclude that there are at least ${K^2 \over 2 C^{{1 \over 2}} N^{2 +{3 \over 100}}}$ values of $j$ for which $$\sum_{k=1}^K |A_j \cap A_k| \geq {K \over 2N^{2 +{1 \over 50}}}. \tag 3$$ We refer to set of $j$'s for which (3) holds as $\Cal G_1$, the first good set. Using our estimate on $K$, we rewrite (3) as $$\sum_{k=1}^K |A_j \cap A_k| \geq {C \over 2 N^{3 \over 100}}. \tag 4$$ Now we make a couple of observations. First whenever we have distinct $k_1,k_2$ with $A_j \cap A_{k_1} \neq \emptyset$ and $A_j \cap A_{k_2} \neq \emptyset,$ by assumption, we must have $B_{k_1} \cap B_{k_2} = \emptyset.$ But by the lower bound on the measures of the $B_j$'s, we conclude that $$\#(\{k:A_j \cap A_k \neq \emptyset\}) \leq N^{1 + {1 \over 100}}. \tag 5$$ Furthermore, by the upper bound on the measure of $A_j$, we have automatically that $$|A_j \cap A_k| \leq {1 \over N}, \tag 6$$ for every value of $k$. Combining (4),(5),(6), and Proposition X, we conclude that for every $j \in \Cal G_1$ there must be at least ${C N^{{97 \over 100}} \over 2}$ values of $k$ with $$|A_j \cap A_k| \geq {C \over 2 N^{{26 \over 25}}}. \tag 7$$ Now we repeat the same argument for the $B_j$'s indexed by $j \in \Cal G_1.$ We observe that $$\sum_{j \in \Cal G_1} |B_j| \geq \# (\Cal G_1) {1 \over N^{1 + {1 \over 100}}}, \tag 8$$ and also that $$\sum_{j \in \Cal G_1} |B_j| \leq (\sum_{j \in \Cal G_1} \sum_{k \in \Cal G_1} |B_j \cap B_k|)^{{1 \over 2}}, \tag 9$$ and of course, that for any fixed $j$, $$\sum_{k \in \Cal G_1} |B_j \cap B_k| \leq C^{{1 \over 2}} N^{{1 \over 100}}. \tag 10$$ Now combining (8),(9),(10), and Proposition X, we obtain as usual that there are at least ${C^{{5 \over 2}} N^{{187 \over 100}} \over 8}$ values of $j$ for which $$\sum_{k \in \Cal G_1} |B_j \cap B_k| \geq {C^{3 \over 2} N^{-7 \over 100} \over 4}. \tag 11$$ We refer to those $j$'s for which (11) is satisfied as the elements of $\Cal G_2$, the second good set. We observe, as before, that $$\# (\{k: B_j \cap B_k \neq \emptyset\}) \leq N^{1 + {1 \over 100}}, \tag 12,$$ and for any $k$ one has $$|B_j \cap B_k| \leq {1 \over N}. \tag 13$$ Combining (11),(12),(13) and Proposition X, we obtain that whenever $j \in \Cal G_2$ there are at least $C^{{3 \over 2}} N^{{93 \over 100}}$ values of $k$ for which $$|B_j \cap B_k| \geq {C^{{3 \over 2}} \over 8 N^{{27 \over 25}}}. \tag 14 $$ Now we are in a position to reach a contradiction. We pick a fixed $j \in \Cal G_2$. Then we know there are $C^{{3 \over 2}} N^{{93 \over 100}}$ values of $k \in \Cal G_1$ for which (14) holds. Denote this set of $k$ by $\Cal P_1$. Now (14) implies that for each $k \in \Cal P_1$ one has $$|j-k| \leq {8 N^{27 \over 25} \over C^{3 \over 2}}.$$ Further, the $A_k$'s indexed by $\Cal P_1$ are pairwise disjoint. Finally, since $\Cal P_1$ is a subset of $\Cal G_1$, for each $k \in \Cal P_1$, one has ${C N^{{97 \over 100}} \over 2}$ values of $l$ for which $|A_k \cap A_l| \geq {C \over 2 N^{{26 \over 25}}}.$ We denote the set of all these $l$'s by $\Cal P_2$. Since the $A_k$'s are pairwise disjoint and the $A_l$'s have measure at most ${1 \over N}$, each $l$ may occur for at most ${2 N^{{1 \over 25}} \over C}$ different values of $k$. Thus we have $$\#(\Cal P_2) \geq {C^{{7 \over 2}} N^{{93 \over 50}} \over 4}. \tag 15$$ But, fixing $k$, we have that for each $l$ corresponding to that $k$, one has $$|k-l| \leq {2 N^{{26 \over 25}} \over C},$$ so that for every $l \in \Cal P_2$, one has $$|j-l| \leq {8 N^{27 \over 25} \over C^{{3 \over 2}}} + {2 N^{{26 \over 25}} \over C}. \tag 16$$ However, for sufficiently large $C$, we have that (15) and (16) imply a contradiction. \qed \enddemo In what remains, we make use of the jigsaw puzzle lemma to prove the theorem. Suppose $\eta > 0$ is a number. We define $K(\eta)$ to be the smallest number so that if $E$ is any set satisfying the hypotheses of the theorem for parameter $\epsilon > \eta$, one always has $$|E| \leq K(\eta) \epsilon.$$ By a well known method of extremal graph theory, one can show a priori that $K(\eta) \leq C (1 + \log (|{1 \over \eta}|))$. We will proceed by proving a bootstrapping inequality for $K(\eta)$. First, we need a lemma about rescaling. \proclaim{Lemma(rescaling)} Let $E$ be any set satisfying the hypotheses of the theorem with parameter $\epsilon$. Suppose that the $x$-projection of the set, $\Pi_x E$ satisfies $$|\Pi_x E| \leq c,$$ then one has $$|E| \leq c^{{1 \over 2}} K(\epsilon) \epsilon.$$ \endproclaim The main tool in proving the rescaling lemma will be the following proposition of one dimensional measure theory. \proclaim{Proposition(compression)} Let $A \subset [0,1]$ be a measurable set with $|A| = c$. Then there is a map $Q$ from a full measured subset of $A$ one-to-one and onto a full measured subset of $(0,c)$ which is measure preserving and monotone and so that one always has $$|Q(y)-Q(x)| \leq |y-x|.$$ \endproclaim \demo{Proof of the rescaling lemma} We apply the compression lemma to the $x$-projection of $E$. By applying the map $Q$ tensored with the identity to the set $E$, one obtains a new set $F$ with $|F|=|E|$, with $F$ satisfying the hypotheses of the theorem and with $F \subset [0,c] \times [0,1]$. Denote by $G$, the set $F$ dilated by ${1 \over c}$. Then $G \subset [0,1] \times [0,1]$ and $G$ satisfies the hypotheses of the theorem with parameter ${1 \over \sqrt{c}} \epsilon$ which is larger than $\epsilon$. Thus $$|G| \leq K(\epsilon) {\epsilon \over \sqrt{c}}.$$ But $$|E|=|F|=c|G|,$$ so that $$|E| \leq K(\epsilon) \sqrt{c} \epsilon,$$ which was to be shown. \qed \enddemo The rescaling lemma easily implies the following \proclaim{Lemma(distribution)} Let $E$ be a set satisfying the hypotheses of the theorem with parameter $\epsilon$. Define $$H=\{(x,y) \in E: \int \chi_E(x,z) dz \geq K(\epsilon)^3 \epsilon \}.$$ Then $$|H| \leq \epsilon.$$ \endproclaim \demo{Proof} By the definition of $K(\epsilon)$, one has $$|\Pi_x H| \leq {1 \over K(\epsilon)^2}.$$ Applying the rescaling lemma, we obtain $$|H| \leq \epsilon.$$ \enddemo Observe that the same is true if we replace the $x$ direction by the $y$ direction. The theorem will now be implied by the following bootstrapping lemma: \proclaim{Lemma(bootstrap)} Let $E$ be a set satisfying the hypotheses of the theorem, so that it is true for no value of $x$ that $$\int \chi_E(x,z) dz \geq K(\epsilon)^3 \epsilon,$$ and for no value of $y$ is it true that $$\int \chi_E(z,y) dz \geq K(\epsilon)^3 \epsilon.$$ Then $$|E| \leq C(\sqrt{1 + \log K(\epsilon)}) \epsilon.$$ \endproclaim The bootstrap lemma would imply together with the distribution lemma that $$K(\epsilon) \leq 2 + C \sqrt{1 + \log K(\epsilon)},$$ which in turn implies that $K(\epsilon)$ is bounded by a universal constant. We will prove the bootstrap lemma by reducing it to well known methods of extremal graph theory combined with the jigsaw puzzle lemma. We introduce some notation. We define $$E_x=\{y \in [0,1]: (x,y) \in E \},$$ and $$E^y=\{x \in [0,1]: (x,y) \in E \}.$$ Now we are ready to proceed. We observe as usual that $$\eqalign{& |E| \cr &=\int \int \chi_E(x,y)dx dy \cr &=\int |E_x| dx \cr &\leq (\int |E_x|^2 dx )^{{1 \over 2}} \cr &\leq (\int \int |E^y \cap E^z| )^{{1 \over 2}} \cr &\leq (\sum_j \int_{\{ ({4 \over 3})^j \epsilon \leq |y-z| \leq ({4 \over 3})^{j+1} \} } |E^y \cap E^z|)^{{1 \over 2}}.}$$ Now, from the hypotheses of the theorem, we have the estimate $$|E^y \cap E^z| \leq {\epsilon^2 \over |y-z|},\tag 16$$ by from the hypotheses of the bootstrap lemma, we have $$|E^y \cap E^z| \leq |E^y| \leq K(\epsilon)^3 \epsilon. \tag 17$$ Define the constant $C$ sufficiently large so that $j \geq C \log K(\epsilon)$ implies that $$({4 \over 3})^j \geq K(\epsilon)^{500}.$$ Then it is immediate from (16) and (17) that $$\sum_{j \leq C \log K(\epsilon)} \int_{({4 \over 3})^j \epsilon \leq |y-z| \leq ({4 \over 3})^{j+1}\epsilon } |E^y \cap E^z| \leq C \log K(\epsilon).$$ We need only consider the sum over large $j$. Our strategy from this point on will be to show that there are constants $C>0$ and $\mu > 0$ so that whenever $$R=S K(\epsilon)^{500} \epsilon,$$ with $S > 1$, one has that $$\int_{{3R \over 2} \leq |y-z| \leq R} |E^y \cap E^z| \leq C S^{-\mu} \epsilon^2. \tag 18$$ Summing the geometric series will prove the theorem. We now make a trivial remark about the set of pairs $(y,z)$ with $${3R \over 2} \leq |y-z| \leq 2R.$$ We cover [0,1] by disjoint intervals of width $R$ in two ways. We define $$\Cal D_R=\{[0,R],[R,2R],\dots,[R [{1 \over R}], (R+1)[{1 \over R}]] \}=\{I_0,I_1,\dots,I_{[{1 \over R}]}\},$$ and $$\Cal D_R^{\prime}=\{[{-R \over 2},{R \over 2}],\dots,[(R+{1 \over 2}) [{1 \over R}],(R+{3 \over 2})[{1 \over R}]] \} =\{J_{-1},J_0,\dots,J_{[{1 \over R}]} \}.$$ Now, any pair $y,z$ having the desired distance with $y |B_k|$ and $2^{-l} {1 \over S} > |A_k| \geq 2^{-l-1} {1 \over S}$ and $k \in \Cal C_{B,l}$ if $|B_k| \geq |A_k|$ and $2^{-l} {1 \over S} > |B_k| \geq 2^{-l-1} {1 \over S}$. It suffices to show $$\sum_{k \in \Cal C_{A,l}} |A_k||B_k| \leq C S^{-\mu} 2^{-l \mu}. \tag 22$$ We let ${1 \over N}=2^{-l} {1 \over S}$. We divide $\Cal C_{A,l}= C_g \cup C_b,$ where $k \in C_b$ if $|B_k| \leq {1 \over N^{{101 \over 100}}}.$ We claim that $$\# (C_b) \leq C N^2 \log N \leq C N^{{401 \over 200}}. \tag 23$$ This is because $${1 \over N} \# (C_b) \sim \sum_{j \in C_b} |A_j| \leq \sqrt{\sum_{j \in C_b} \sum_{k \in C_b} {1 \over |j-k|}}.$$ Thus $$\sum_{k \in C_b} |A_k||B_k| \leq C N^{{401 \over 200}} {1 \over N} {1 \over N^{{101 \over 100}}} \leq C N^{-1 \over 200}. \tag 24$$ On the other hand, $C_g$ satisfies the hypotheses of the jigsaw puzzle lemma, so that applying the lemma we get $$\# (C_g) \leq CN^{{199 \over 100}},$$ so that $$\sum_{j \in C_g} |A_j| |B_j| \leq {1 \over N^2} C N^{{199 \over 100}} \leq C N^{{-1 \over 100}}. \tag 25$$ The inequalities (24) and (25) together imply (22) and hence the theorem. \Refs\nofrills{References} \widestnumber\key{CCW} \ref \key CCW \by A. Carbery, M. Christ, and J. Wright \paper Title to be announced \jour preprint \endref \ref \key S \by E. Stein \book Harmonic Analysis: Real-variable methods, orthogonality, and oscillatory integrals \publ Princeton University Press \yr 1993 \endref \endRefs \end