On the Self Crossing Six Sided Figure Problem

New York Journal of Mathematics

New York J. Math. ⁵(1999) 121{130.

On the Self Crossing Six Sided Figure Problem

Nets Hawk Katz

Abstract. It was shown by Carbery, Christ, and Wright that any measurable set^Ein the unit square in^R2 not containing the corners of a rectangle with area greater than has measure bounded by^O(^qlog¹). We remove the log under the additional assumption that the set does not contain the corners of any axis-parallel, possibly self-crossing hexagon with unsigned area bigger than. Our proof may be viewed as a bilinearization of Carbery, Christ, and Wright's argument.

Contents

0. Introduction 121

1. Proof of the Theorem 122

References 130

0.

Introduction

We say that four points in^R2 are the vertices of an axis parallel rectangle if they are of the form (^x1y1), (^x1y2), (^x2y1), (^x2y2) with^{x1 6}=^x2 and^y16=^y2. We say that the area of the rectangle is^{jx1;x2jjy1;y2j}.

We say that six points in ^R2 are the vertices of a right angled, axis parallel hexagon (possibly self-crossing) if they are of the form (^x1y2), (^x1y3), (^x2y1), (^x2y3), (^x3y1), (^x3y2) with^x1x2x3pairwise distinct and with^y1y2y3pairwise distinct. We say that the area of the hexagon is

A= max(^jxi;xjj)min(^jyi;yjj) + max(^jyi;yjj)min(^jxi;xjj)^:

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.

The purpose of this paper is to prove the following theorem.

Received June 11, 1998.

Mathematics Subject Classication. 42B25.

Key words and phrases. Cauchy-Scwartz, Hexagons, Bilinear.

The author was supported by EPSRC GR/l10024.

c1999StateUniversityofNewYork

ISSN1076-9803/99

121

Theorem.

There exists a constant^C>0 so that for any number^>0, whenever

E 01]01] is a set which does not contain the vertices of any axis parallel rectangle with area greater than ² and does not contain the vertices of any axis parallel hexagon with area greater than ² then^jEjC.

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^f0>has small sublevel sets. (I.e., the set of^xfor which^jf(^x)^j1 has measure smaller than ².) This fact is the underlying idea behind Van der Corput's Lemma and the method of stationary phase, (see S, Chapter 8]).

They observed that a function ^f on the unit square in ^R2 satisfying ^{@x@y@2f >}

must satisfy the estimate

jf(^xy) :^jf(^xy)^j1^gjC

plog

p

(^;1) :

The question arose whether (^;1) is sharp. A simple example shows one can nd such an^f for which the sublevel set is as large as ^p1. 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². We then trivially have the estimate

jEjC r

log 1

(^;2) :

The question is again whether the log is really there. The estimate (^;2) implies the estimate (^;1). We may see this by letting^Ebe the sublevel set, by letting= ¹². We see that ^E satises the geometric condition we have stated by integrating^d!

over any axis parallel rectangle with vertices in the set, where^! is the one-form

!=^@f

@x dx;

@f

@y dy:

The same argument shows that when^Eis the sublevel set of^f, it satises more stringent geometrical conditions. Indeed it cannot contain the vertices of large non self-crossing axis parallel hexagons. (Or for that matter 2ⁿ-sided polygons where large depends inversely onⁿ.) 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).

1.

Proof of the Theorem

The main point of the proof is the following jigsaw puzzle lemma.

Lemma

(jigsaw puzzle)

.

There exist universal constants ^{C >}0 so that for any large^N, one has that if ^{A1:::AKB1:::BK} 01] satisfying

1

N 1+

jA

j jjB

j j

1

N

(1)

and further that if ^{Aj \Ak 6}= then ^Bj\Bk = (note this is symmetric in ^A and ^B) and further still if ^{Aj \Ak 6}= and ^{Ak \Al 6}= then ^Bj\Bl =and analogously if^Bj\Bk6=and^Bk\Bl6=then^Aj\Al=and nally if we have

jA

j

\A

k jjB

j

\B

k j

1

jj;kj

(2)

then we reach the following conclusion: We have

KCN 2;

:

In proving the jigsaw puzzle lemma, we will frequently make use of the following lemma.

Lemma X.

^{Let a1:::aN} be nonnegative real numbers. Suppose that for all ^j, one has

a

j

<M:

Suppose further that

N

X

j=1 a

j

>S:

Then there exist at least ^2MS values of ^j for which

a

j

S

2^N:

Proof.

^{Dene G} to be the subset of ^f1^:::Ng so that for any^{j 2 G}, one has

a

j

S

2N. One has

X

j2G a

j

S

2^: But since each^aj is bounded above by^M, we have

#(^G)2^SM:

Now before proving the jigsaw puzzle lemma, we spend a moment explaining the philosophy and the logic of the proof. If we remove the hypothesis (which is what relates to hexagons) that^Aj\Ak6=and^Ak\Al6=imply that^Bj\Bl=and vice versa, ^K can be as large as ^N2. However, all examples for which ^K is even within a factor of^N of^N2 (for suciently small) share certain properties which force the hexagon condition to be violated.

The precise logic as far as quantiers is as follows. We suppose that for any ^>0 a counterexample can be found with^Cas large as desired, provided^Nis suciently large. (In other words, we choose things so that powers of ^N which arise always dominate^C.) We choose suciently small and reach a contradiction, thus proving the lemma. We abuse the notation slightly, as is the custom in analysis, changing the in every line with the understanding that it remains small. (This means

we must have chosen it very, very small at the beginning.) We also occasionally introduce new constants ^C which are small compared to any power of ^N which arises.

Proof of jigsaw puzzle lemma.

We suppose the conclusion of the lemma is false.

Then there exist sets for which we have^KCN2; with^Carbitrarily large. (By the pairwise disjointness of the product sets ^AjBj, however, we certainly have

K N 2+

:) (We have changed the and simply applied the lower bound on^jAjj and^jBjj.)

Now, we have that

K

X

j=1 jA

j j

K

N 1+

N 1;

but

K

X

j=1 jA

j j=^XK

j=1 Z

1

0

A

j(^x)^dx

=

Z

1

0

(^XK

j=1

Aj(^x))^dx

(^{Z 1}

0

(^XK

j=1

A

j(^x))^2dx)¹²

(^XK

j=1 K

X

k =1 jA

j

\A

k j)^12: We conclude

K

X

j=1 K

X

k =1 jA

j

\A

k jK

2 1

N 2+

(3) :

Fixing^j arbitrary, we observe that

K

X

k =1 jA

j

\A

k j

K

X

k =1

1

jj;kj

Clog^{N C12N:} (4)

Now combining (3), (4), and Lemma X, we conclude there are at least ^K2

2C 1

2

N

values of^j for which 2+

K

X

k =1 jA

j

\A

k j

K

2^N2+: (5)

We refer to the set of^j's for which (5) holds as^G1, the rst good set.

Using our estimate on^K, we rewrite (5) as

K

X

k =1 jA

j

\A

k j

C

2^N: (6)

Now we make a couple of observations. First, whenever we have distinct^k1k2with

A

j

\A

k1

6=and^{Aj\Ak2 6}=by assumption, we must have^Bk1\Bk2 =^:But by the lower bound on the measures of the^Bj's, we conclude that

#(^fk:^{Aj\Ak 6}=^g)^N1+:

(7)Furthermore, by the upper bound on the measure of ^Aj, we have automatically that

jA

j

\A

k j

1

N

(8)

for every value of^k. Combining (6), (7), (8), and Lemma X, we conclude that for every^j2G1there must be at least ^CN21; values of^kwith

jA

j

\A

k j

C

2^N1+: (9)

Now we repeat the same argument for the^Bj's indexed by^{j 2G1:} We observe that

X

j2G

1 jB

j

j#(^G1) 1

N 1+

(10)

and also that

X

j2G

1 jB

j j=

Z

1

0 X

j2G

1

B

j(^x)^dx (11)

(

Z

1

0

(^X

j2G1

B

j(^x))^2dx)¹²

(

Z

1

0 X

j2G1 X

k 2G1

Bj(^x)^Bk(^x)^dx)¹²

= (^X

j2G1 X

k 2G1 jB

j

\B

k j)¹² and of course, that for any xed^j,

X

k 2G1 jB

j

\B

k jC

1

2

N

(12) :

Now combining (10), (11), (12), and Lemma X, we obtain as usual that there are at least^CN2; values of^j for which

X

k 2G1 jB

j

\B

k j

CN

;

4 ^: (13)

(Roughly speaking, we have shown that the sum whose square root appears in (11) is almost as large as^N2 by combining (11) and (10). The inequality (12) says that no summand is much larger than 1. Since the sum is over^N2terms, there must be many almost as large as 1.) We refer to those^j's for which (13) is satised as the elements of^G2, the second good set.

We observe, as before, that

#(^fk:^Bj\Bk6=^g)^N1+

(14)

and for any^kone has

jB

j

\B

k j

1

N

(15) :

Combining (13), (14), (15) and Lemma X, we obtain that whenever ^{j 2G2} there are at least^CN1; values of^kfor which

jB

j

\B

k j

C

N 1+

(16) :

Now we are in a position to reach a contradiction. We pick a xed^{j 2G2}. Then we know there are^CN1; values of^k2G1 for which (16) holds. Denote this set of

kby^P1. Now (16) implies that for each^k2P1 one has

jj;kj N

1+

C :

Further, the^Ak's indexed by^P1are pairwise disjoint. Finally, since^P1 is a subset of^G1, for each^k2P1, one has ^CN21; values of^lfor which^{jAk\Alj 2NC1+:}We denote the set of all these^l's by ^P2. Since the ^Ak's are pairwise disjoint and the

A

l's have measure at most ^N1, each^lmay occur for at most ^2NC dierent values of

k. Thus we have

#(^P2)^CN2;:

(17)But, xing^k, we have that for each^lcorresponding to that^k, one has

jk;lj

2^N1+

C

so that for every^l2P2, one has

jj;lj N

1+

C

+ 2^N1+

C

(18) :

However, (17) and (18) imply a contradiction, for otherwise there would be a set of^N2; distinct^l's at a distance of^N1+ from^j.

In what remains, we make use of the jigsaw puzzle lemma to prove the theorem.

Suppose^>0 is a number. We dene^K() to be the smallest number so that if^E is any set satisfying the hypotheses of the theorem for parameter^>, one always has

jEjK()^:

By a well known method of extremal graph theory (essentially the application of Cauchy Schwartz in (11) again), one can show a priori that^K()^C(1+log(^j1j)).

We will proceed by proving a bootstrapping inequality for^K().

First, we need a lemma about rescaling.

Lemma

(rescaling)

.

^LetEbe any set satisfying the hypotheses of the theorem with parameter. Suppose that the ^x-projection of the set,^xE satises

j^xEjc then one has

jEjc 1

2

K()^:

The main tool in proving the rescaling lemma will be the following lemma of one dimensional measure theory.

Lemma

(compression)

.

Let^A01] be a measurable set with^jAj=^c. Then there is a map ^Qfrom 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

jQ(^y)^;Q(^x)^jjy;xj:

Proof of the rescaling lemma.

We apply the compression lemma to the^x-pro- jection of ^E. By applying the map ^Q tensored with the identity to the set ^E, one obtains a new set ^F with ^jFj =^jEj, with ^F satisfying the hypotheses of the theorem and with ^F 0^c]01]. Denote by ^G, the set ^F dilated by ^1c. Then

G 01]01] and ^G satises the hypotheses of the theorem with parameter

1

p

c

which is larger than. Thus

jGjK()^p

c :

But

jEj=^jFj=^cjGj so that

jEjK()^pc which was to be shown.

The rescaling lemma easily implies the following

Lemma

(distribution)

.

Let^Ebe a set satisfying the hypotheses of the theorem with parameter. Dene

H =^f(^xy)^2E:

Z

E(^xz)^dzK()^3g:

Then

jHj:

Proof.

By the denition of^K(), one has

j^xHj 1

K()^2: Applying the rescaling lemma, we obtain

jHj:

Observe that the same is true if we replace the^xdirection by the^y direction.

The theorem will now be implied by the following bootstrapping lemma:

Lemma

(bootstrap)

.

^{Let E} be a set satisfying the hypotheses of the theorem, so that it is true for no value of^x that

Z

E(^xz)^dzK()³ and for no value of^y is it true that

Z

E(^zy)^dzK()^3:

Then

jEjC(^p1 + log^K())^:

The bootstrap lemma would imply together with the distribution lemma that

K()2 +^Cp1 + log^K()

which in turn implies that^K() 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 dene

E

x=^fy201] : (^xy)^2Eg and

E

y=^fx201] : (^xy)^2Eg:

Now we are ready to proceed.

We observe as usual that

jEj=

Z Z

E(^xy)^dxdy

=

Z

jE

x jdx

(

Z

jE

x j

2

dx)¹²

(^{Z Z jEy\Ezj})¹²

0

@ X

j Z

f(

4

3 )

j

jy;zj(

4

3 )

j+1

g jE

y

\E z

j 1

A 1

2

:

Now, from the hypotheses of the theorem, we have the estimate

jE y

\E z

j

2

jy;zj

(19)

by the hypotheses of the bootstrap lemma, we have

jE y

\E z

jjE y

jK()^3: (20)

Dene the constant^C suciently large so that^jClog^K() implies that

4 3

j

K()^500: Then it is immediate from (19) and (20) that

X

jClogK() Z

( 4

3 )

j

jy;zj(

4

3 )

j+1

jE

y

\E z

jClog^K()^: 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^>0 so that whenever

R=^SK()⁵⁰⁰

with^S>1, one has that

Z

3R

2

jy;zjR jE

y

\E z

jCS

;

2

(21) :

Summing the geometric series will prove the theorem.

We now make a trivial remark about the set of pairs (^yz) with 3^R

2 ^jy;zj2^{R :}

We cover 0,1] by disjoint intervals of width^Rin two ways. We dene

D

R=^f0^R]^R 2^R]^:::R 1

R

](^R+ 1) 1

R

]]^g=^fI0I1:::IR¹ ]

g

and

D 0

R=^f;R2 ^R2 ]^:::(^R+ 12)1

R

](^R+ 32)1

R

]]^g=^fJ;1J0:::JR¹ ]

g:

Now, any pair^yzhaving the desired distance with^y<zwill have for some integer

j, either ^y2Ij and^z2Ij+2 or^y2Jj and^z2Jj+2. Thus we obtain

Z

3R

2

jy;zj2R jE

y

\E z

j X

j Z

jE

x

\I

j jjE

x

\I

j+2

jdx+^X

j Z

jE

x

\J

j jjE

x

\J

j+2 jdx:

Thus it suces to show for xed^j that

Z

jE

x

\I

j jjE

x

\I

j+2 jCS

;

R 2

(22) :

This is exactly what we shall do.

We divide up 01] into the set of intervals ^D2

R

which are dual to^DR and we denote these^Kk's. For each^Kk, we choose an ^xk for which^{jExk\IjjjExk\Ij+2j} is at least half as big as the supremum over^x2Kk. It suces to estimate

X

k jE

x

k

\I

j jjE

x

k

\I

j+2 j

2

R

C

2

S

;

(23) R

We consider only^k odd (and separately consider only^keven).] Rescaling respec- tively^Ij and^Ij+2 into 01] and renaming the rescaled^Exk\Ij and^Exk\Ij+2 as

A

k and ^Bk respectively, we see we need only show

X

k jA

k jjB

k jCS

;

(24) :

It is easy to see from the hypotheses of the theorem that the^A's and^B's satisfy all the hypotheses of the jigsaw puzzle lemma except for those regarding the measure of the^Aj's or^Bj's. We do know from the hypotheses of the bootstrapping lemma that these are less than^S1. We divide the^k's into the classes^CAland^CBlby letting

k2C

Al if^jAkj>jBkj and 2^{;lS1 >jAkj}2^;l;1S1 and^k2CBl if^jBkjjAkjand 2^{;lS1 >jBkj}2^;l;1S1. It suces to show

X

k 2CAl jA

k jjB

k jCS

;2^;l: (25)

We let ^N1 = 2^;lS1. We divide^CAl=^CgCbwhere^k2Cb if^{jBkj N11+:}

We claim that

#(^Cb)^CN2log^{N CN2+2:} (26)This is because

1

N

#(^Cb) ^X

j2Cb jA

j j

s

X

j2Cb X

k 2Cb

1

jj;kj :

Thus

X

k 2C

b jA

k jjB

k jCN

2+

2 1

N

1

N 1+

CN

;

2

(27) :

On the other hand,^Cg satises the hypotheses of the jigsaw puzzle lemma, so that applying the lemma we get

#(^Cg)^CN2;

so that

X

j2Cg jA

j jjB

j j

1

N 2

CN 2;

CN

;

(28) :

The inequalities (27) and (28) together imply (25) and hence the theorem.

References

CCW] A. Carbery, M. Christ, and J. Wright,Multidimensional Van der Corput and sublevel set estimates, JAMS, to appear.

S] E. Stein,Harmonic Analysis: Real-variable Methods, Orthogonality, and Oscillatory In- tegrals, Princeton University Press, 1993, MR 95c:42002, Zbl 821.42001.

Department of Mathematics, Statistics, and Computer Science, University of Illi- nois, Chicago, IL, 60607-7045

[email protected] http://math.uic.edu/~nets/

This paper is available via http://nyjm.albany.edu:8000/j/1999/5-10.html.