This paper was converted on www.awesomepapers.org from LaTeX by an anonymous user.
Want to know more? Visit the Converter page.

A stationary set method
for estimating oscillatory integrals

Saugata Basu Department of Mathematics
Purdue University
USA
[email protected]
Shaoming Guo Department of Mathematics
University of Wisconsin Madison
USA
[email protected]
Ruixiang Zhang Department of Mathematics, University of California, Berkeley
USA
[email protected]
 and  Pavel Zorin-Kranich Mathematical Institute
University of Bonn
Germany
[email protected]
Abstract.

We propose a new method of estimating oscillatory integrals, which we call a “stationary set” method. We use it to obtain the sharp convergence exponents of Tarry’s problems in dimension two for every degree k2k\geq 2. As a consequence, we obtain sharp LLpL^{\infty}\to L^{p} Fourier extension estimates for a family of monomial surfaces.

2020 Mathematics Subject Classification:
42B20 (Primary) 03C10 (Secondary)

1. Statement of the main results

Our main result, Theorem 1.1, gives upper bounds on certain oscillatory integrals of bounded complexity.

Theorem 1.1 (“Stationary set” estimate).

Let d,k1d,k\geq 1. Let Q(ξ)Q(\xi) be a bounded semialgebraic function in variables ξ[0,1]d\xi\in[0,1]^{d} with complexity k\leq k. Then

(1.1) |[0,1]de(Q(ξ))𝑑ξ|d,ksupμ|{ξ[0,1]d:μQ(ξ)μ+1}|.\Big{|}\int_{[0,1]^{d}}e(Q(\xi))d\xi\Big{|}\lesssim_{d,k}\sup_{\mu\in\mathbb{R}}\lvert\{\xi\in[0,1]^{d}:\mu\leq Q(\xi)\leq\mu+1\}\rvert.

The implicit constant depends only on dd and kk.

Theorem 1.1 relies mainly on tools from real algebraic geometry and model theory, in particular, o-minimal geometry.

We will apply Theorem 1.1 to obtain new and often sharp results on the convergence exponent of Tarry’s problem in dimension 22 and LLpL^{\infty}\to L^{p} Fourier restriction for two-dimensional Parsell-Vinogradov surfaces. These applications only require Theorem 1.1 with functions QQ being polynomials of bounded degrees, but our proof does not simplify in this special case. The more general setting of semialgebraic functions may also be of independent interest.

1.1. Sharpness of Theorem 1.1 in an average sense.

The argument in this subsection was shared to us by Wright, who further attributed it to Stein in the real setting and to Hua (see [Hua65, page 15]) in the pp-adic setting. A similar form of it was used for instance in [Wri20]. Their argument also works for general valued fields, Archimedean or non-Archimedian. Here we only present this argument in the real setting. It shows that the upper bound (1.1) is tight in an average sense (up to a log factor). Let us be more precise. Denote

(1.2) LQ:=supc|{ξ[0,1]d:cQ(ξ)c+1}|L_{Q}:=\sup_{c\in\mathbb{R}}|\{\xi\in[0,1]^{d}:c\leq Q(\xi)\leq c+1\}|

and

(1.3) I(sQ)=[0,1]de(sQ(ξ))𝑑ξ.I(sQ)=\int_{[0,1]^{d}}e(sQ(\xi))d\xi.

We will prove that

(1.4) 11|I(sQ)|𝑑s11LsQ𝑑s(|logδ|+1)11|I(sQ)|𝑑s,\int_{-1}^{1}|I(sQ)|ds\lesssim\int_{-1}^{1}L_{sQ}ds\lesssim(|\log\delta|+1)\int_{-1}^{1}|I(sQ)|ds,

where QQ is a bounded semialgebraic function of complexity k\leq k, δ:=LQ1\delta:=L_{Q}\leq 1, and the implicit constants are allowed to depend on dd and kk.

The first inequality in (1.4) follows directly from Theorem 1.1. We only need to prove the second inequality. Let g:[0,1]dg:[0,1]^{d}\to\mathbb{R} be a measurable function. Let ψ:\psi:\mathbb{R}\to\mathbb{R} be a Schwartz function satisfying 𝟏[0,1](x)ψ(x)\mathbf{1}_{[0,1]}(x)\leq\psi(x) for every xx\in\mathbb{R} whose Fourier transform is compactly supported. We first show that

(1.5) Lg|ψ^(s)||I(sg)|𝑑s.L_{g}\leq\int_{\mathbb{R}}|\widehat{\psi}(s)||I(sg)|ds.

To see this, we write

(1.6) |{ξ[0,1]d:cg(ξ)c+1}|=[0,1]d𝟏[0,1](g(ξ)c)𝑑ξ.|\{\xi\in[0,1]^{d}:c\leq g(\xi)\leq c+1\}|=\int_{[0,1]^{d}}\mathbf{1}_{[0,1]}(g(\xi)-c)d\xi.

By the definition of ψ\psi, this is bounded by

(1.7) [0,1]dψ(g(ξ)c)𝑑ξ=[0,1]d[ψ^(s)e(s(g(ξ)c))𝑑s]𝑑ξ\begin{split}&\int_{[0,1]^{d}}\psi(g(\xi)-c)d\xi=\int_{[0,1]^{d}}\big{[}\int_{\mathbb{R}}\widehat{\psi}(s)e(s(g(\xi)-c))ds\big{]}d\xi\end{split}

The bound (1.5) now follows from the triangle inequality.

Recall that δ=LQ\delta=L_{Q}. Assume that ψ^(s)\widehat{\psi}(s) is supported on [C,C][-C,C]. For every jj with δ2j1\delta\lesssim 2^{-j}\leq 1, it holds that

(1.8) |s|2jLsQ𝑑s2jL2jQ2jL2jQ/C2jCC|I(2jsQ/C)|𝑑s11|I(sQ)|𝑑s,\int_{|s|\sim 2^{-j}}L_{sQ}ds\sim 2^{-j}L_{2^{-j}Q}\sim 2^{-j}L_{2^{-j}Q/C}\lesssim 2^{-j}\int_{-C}^{C}|I(2^{-j}sQ/C)|ds\lesssim\int_{-1}^{1}|I(sQ)|ds,

where in the second last inequality we applied (1.5). This, combined with the trivial bound

(1.9) |s|δLsQ𝑑s|s|δ1𝑑s2δ11|I(sQ)|𝑑s,\int_{|s|\leq\delta}L_{sQ}ds\leq\int_{|s|\leq\delta}1ds\leq 2\delta\lesssim\int_{-1}^{1}|I(sQ)|ds,

implies the second inequality in (1.4).

1.2. Comparison to previously known tools for estimating oscillatory integrals

A well-known method of estimating oscillatory integrals is through van der Corput estimates, which assume a lower bound for DβQD^{\beta}Q for some multi-index βd\beta\in\mathbb{N}^{d}. This method is very efficient in dimension one, see for instance Stein [Ste93], or Arkhipov, Chubarikov and Karatsuba [AKC79, Section 1.1] for a more quantitative, but perhaps lesser-known, formulation. In [CCW99], Carbery, Christ, and Wright established van der Corput estimates in dimensions greater than one with very mild assumptions on the relevant phase functions. We also refer to Wright [Wri11a], [Wri11b] and [Wri20] for estimating multi-dimensional oscillatory integrals in settings other than d\mathbb{R}^{d} (for instance the pp-adic setting).

The results in the literature that are perhaps closest to ours were obtained by Bruna, Nagel and Wainger [BNW88] (see also Nagel, Seeger and Wainger [NSW93] for a related result). To describe this result, let Sn+1S\subset\mathbb{R}^{n+1} be a smooth, compact hypersurface that is convex and of finite type. Let dσd\sigma be the surface measure on SS. For xSx\in S, let νx\nu_{x} denote the outward unit normal to SS at xx. Bruna, Nagel, and Wainger [BNW88, Theorem B] proved that, for large λ1\lambda\gg 1, we have

(1.10) |Se(y,λνx)𝑑σ(y)|σ{yS:|yx,λνx|<1}.\Bigl{|}\int_{S}e(\langle y,\lambda\nu_{x}\rangle)d\sigma(y)\Bigr{|}\lesssim\sigma\{y\in S:|\langle y-x,\lambda\nu_{x}\rangle|<1\}.

The left-hand side of (1.10) is the Fourier transform of the surface-carried measure ss. The neighborhood of xx on the right-hand side of (1.10) plays a similar role to our stationary sets in Theorem 1.1.

In a slightly different direction, Varchenko [Var76] obtained asymptotic estimates for oscillatory integrals

(1.11) de(λφ(x))χ(x)𝑑x,\int_{\mathbb{R}^{d}}e(\lambda\varphi(x))\chi(x)dx,

where λ\lambda\in\mathbb{R} is a large parameter, φ\varphi is an analytic phase function, and χ\chi is a function supported near one point, say the origin. The asymptotic expansion involves terms in the Newton polyhedron of the phase function. Instead of asking a “global” condition of the form Dβφ1D^{\beta}\varphi\geq 1 as in [CCW99], Varchenko assumed the support of χ\chi to be small enough; he used the resolution of singularities for analytic functions, and his results are more “local”. For further work along this line, we refer to Karpushkin [Kar80] and [Kar83], Phong, Stein and Sturm [PSS99] and Greenblatt [Gre10], and the references therein. Operator-valued oscillatory integrals in a similar spirit have also been extensively studied. It is beyond our capability to give a review of even a small part of it, and therefore we refer interested readers to more classical works including Phong and Stein [PS97] and Seeger, Sogge and Stein [SSS91], and more recent works including Ikromov, Kempe and Müller [IKM10] and Ikromov and Müller [IM16].

1.3. Applications of the stationary set estimate

As an application of our stationary set estimate, we obtain the sharp convergence exponent of Tarry’s problem in dimension two for an arbitrary degree. Let k2k\geq 2 and ξ=(ξ1,,ξd)d\xi=(\xi_{1},\dots,\xi_{d})\in\mathbb{R}^{d} with d1d\geq 1. Set

(1.12) N=Nd,k=(d+kk)1.N=N_{d,k}=\binom{d+k}{k}-1.

For a multi-index β=(β1,,βd)0d\beta=(\beta_{1},\dots,\beta_{d})\in\mathbb{N}_{0}^{d}, denote ξβ=ξ1β1ξdβd\xi^{\beta}=\xi_{1}^{\beta_{1}}\dots\xi_{d}^{\beta_{d}}. Let ϕd,k(ξ)\phi_{d,k}(\xi) denote the vector (ξβ)1|β|kN(\xi^{\beta})_{1\leq|\beta|\leq k}\in\mathbb{R}^{N}. Let Sd,kS_{d,k} denote the dd-dimensional manifold

(1.13) {ϕd,k(ξ):ξ[0,1]d},\{\phi_{d,k}(\xi):\xi\in[0,1]^{d}\},

which is sometimes referred to as a Parsell-Vinogradov manifold. For W[0,1]dW\subset[0,1]^{d}, define the Fourier extension operator associated to WW to be

(1.14) EW(d,k)f(x)=Wf(ξ)e(xϕd,k(ξ))𝑑ξ,xN.E^{(d,k)}_{W}f(x)=\int_{W}f(\xi)e(x\cdot\phi_{d,k}(\xi))d\xi,\ \ x\in\mathbb{R}^{N}.

The convergence exponent of Tarry’s problem is defined to be

(1.15) pd,k:=inf{p:E[0,1]d(d,k)1Lp(N)<}.p_{d,k}:=\inf\{p:\|E_{[0,1]^{d}}^{(d,k)}1\|_{L^{p}(\mathbb{R}^{N})}<\infty\}.

Theorem 1.1 will serve as a main ingredient in the proof of the following theorem, in which we obtain the sharp convergence exponent of Tarry’s problem in dimension two.

Theorem 1.2.

For every k2k\geq 2, we have

(1.16) p2,k=16k(k+1)(k+2)+2.p_{2,k}=\frac{1}{6}k(k+1)(k+2)+2.

The quantity E[0,1](1,k)1Lp(N)\|E_{[0,1]}^{(1,k)}1\|_{L^{p}(\mathbb{R}^{N})} appears in the leading coefficient of the asymptotic expansion of Vinogradov’s mean value, as was first shown by Hua for large exponents pp [Hua47, Chapter 10.3], and in the full range of pp in [Woo19, Corollary 1.3]. The problem of determining the convergence exponent (1.15) goes back to Hua’s works [Hua52, Hua59]. In our notation, Hua proved that p1,kk2/2+kp_{1,k}\leq k^{2}/2+k, and posed the problem of determining p1,kp_{1,k}. This problem was resolved by Arkhipov, Chubarikov and Karatsuba [AKC79] (see also [ACK04, Theorem 1.3] in their book), where they proved that

(1.17) p1,k=(k2+k)/2+1p_{1,k}=(k^{2}+k)/2+1

for every kk. For the connection to the original Tarry problem, we refer to [Woo19, Section 13].

In the same paper [AKC79], the authors also studied Tarry’s problem in higher dimensions, and obtained that

(1.18) pd,kd(k+dd+1)+d,p_{d,k}\leq d\binom{k+d}{d+1}+d,

for every d,k2d,k\geq 2. At the end of their paper, they also stated as an open problem to find the exact value of pd,kp_{d,k} in higher dimensions. Later, Ikromov [Ikr97] obtained the lower bound

(1.19) pd,k(k+dd+1)+1.p_{d,k}\geq\binom{k+d}{d+1}+1.

In the quadratic case, that is, the case k=2k=2, the problem was resolved by Mockenhaupt [Moc96], who proved that pd,2=2(d+1)p_{d,2}=2(d+1) for every d2d\geq 2.

For more partial results and for results on other systems of monomials, we refer to Chakhkiev [Cha03], Ikromov and Safarov [IS13], Safarov [Saf19], and Dzhabbarov [Dzh19, Dzh20].

Remark 1.3.

In [Dzh20], Dzhabbarov considered the case d=2,k=3d=2,k=3 and claimed that p2,312.p_{2,3}\leq 12. The strategy in that paper is to show that E[0,1]2(2,3)1L12(9)E_{[0,1]^{2}}^{(2,3)}1\in L^{12}(\mathbb{R}^{9}). To bound the L12L^{12} norm, the author there expanded the 12-th power of E[0,1]2(2,3)1E_{[0,1]^{2}}^{(2,3)}1 and applied some delicate change of variables, which further required some careful computations of Jacobians. Although this approach looks very natural, our results below (see Section 5, in particular, Remark 5.3) indicates that E[0,1]2(2,3)1E_{[0,1]^{2}}^{(2,3)}1 narrowly misses being L12L^{12} integrable. Indeed,

(1.20) BR|E[0,1]2(2,3)1|12logR,\int_{B_{R}}|E_{[0,1]^{2}}^{(2,3)}1|^{12}\gtrsim\log R,

for every large RR where BR9B_{R}\subset\mathbb{R}^{9} is the ball of radius RR centered at the origin.

As a consequence of Theorem 1.2, we obtain the following Fourier restriction estimates.

Corollary 1.4.

Let d=2d=2. For k2k\geq 2, let p¯d,k\bar{p}_{d,k} denote the smallest even number that is greater than or equal to pd,kp_{d,k}. Then

(1.21) E[0,1]d(d,k)fpk,pf,\|E_{[0,1]^{d}}^{(d,k)}f\|_{p}\lesssim_{k,p}\|f\|_{\infty},

for every p>p¯d,kp>\bar{p}_{d,k}. Moreover, when pd,kp_{d,k} is even, which is the same as saying k1mod4k\not\equiv 1\mod 4, the above estimate is sharp in the sense that it fails for every pp¯d,kp\leq\bar{p}_{d,k}.

When k3mod4k\equiv 3\mod 4, it is reasonable to believe that (1.21) also holds for every p>p2,kp>p_{2,k}. Here our result covers the range p>p2,k+1p>p_{2,k}+1.

Recall that Theorem 1.2 states that (1.21) holds with f=1f=1 whenever p>p2,kp>p_{2,k}. That such an estimate implies (1.21) for a general fLf\in L^{\infty} for an even pp is standard, and is exactly how Mockenhaupt [Moc96] proved (1.21) for every p>pd,2p>p_{d,2} and every d2d\geq 2. In the case of Mockenhaupt, the exponent pd,2=2(d+1)p_{d,2}=2(d+1) is always even, which allows him to obtain sharp estimates in pp. In our case, our exponent p2,kp_{2,k} may be odd, and by doing this reduction we may be off the sharp exponent of pp by 1.

Because of its applications to areas like partial differential equations, analytic number theory, and combinatorics, the Fourier restriction theory has received significant amount of attentions in the past few decades. A number of methods, including the bilinear method (see for instance Tao, Vargas and Vega [TVV98], Wolff [Wol01] and Tao [Tao03]), the multilinear method (see for instance Bennett, Carbery and Tao [BCT06] and Guth [Gut10]), the broad-narrow analysis of Bourgain and Guth [BG11] and the polynomial method (see for instance Guth [Gut16]), have been introduced to study the Fourier restriction phenomenon. Perhaps it is not exaggerating to say that each of the above mentioned papers generated an area of active research. Our method in the current paper seems to be disjoint from the above mentioned ones, and it would be very interesting to see how they can be connected.

1.4. A few remarks on Theorem 1.2 and Corollary 1.4

Let us first remark on the methods of proof of Theorem 1.2, and compare with those in the literature.

First of all, in the quadratic case k=2k=2 in [Moc96], in order to bound the LpL^{p} norm of E[0,1]d(d,2)1E_{[0,1]^{d}}^{(d,2)}1, Mockenhaupt computed the function E[0,1]d(d,2)1E_{[0,1]^{d}}^{(d,2)}1 directly. To be more precise, he first smoothed out the function 𝟏[0,1]d\mathbf{1}_{[0,1]^{d}} to e|ξ|2/2e^{-|\xi|^{2}/2}, took the advantage of having a quadratic phase function and computed a Fourier transform directly (roughly speaking via completing squares). It seems difficult to generalize this approach to surfaces of cubic degree or higher. The result of Mockenhaupt [Moc96] has recently been recovered in [GOZZK20] via the broad-narrow analysis of Bourgain and Guth and decoupling inequalities for quadratic forms, and the approach there does not work either for degrees k3k\geq 3.

Next, we turn to the upper bound (1.18) established in [AKC79]. The authors of [AKC79] first derived an accurate pointwise bound for a dd-dimensional oscillatory integral, and then applied this bound to obtain a good pointwise bound for |E[0,1]d(d,k)1(x)||E_{[0,1]^{d}}^{(d,k)}1(x)| in terms of xx. Their pointwise bound is sharp for some, but not all, xNx\in\mathbb{R}^{N}, resulting in an integrability exponent that is not sharp.

In our paper, we propose an entirely different approach, which we call a stationary set method. This method, combined with a careful study of the geometry of stationary sets in our problem (see Subsection 4.2), and certain rigidity properties of stationary sets (see Subsection 4.3), allows us to prove sharp LpL^{p} integribility of |E[0,1]d(d,k)1(x)||E_{[0,1]^{d}}^{(d,k)}1(x)| for d=2d=2 and every k2k\geq 2.

Remark 1.5.

We expect our stationary set method to be useful in obtaining the sharp convergence exponents of Fourier extension operators for more general semialgebraic sets. In a follow up paper, we are planning to show that the stationary set approach is often “tight” in the following sense. Let ϕ:dN\phi:\mathbb{R}^{d}\to\mathbb{R}^{N} be a semialgebraic function and

L(x):=supμ|{ξ[0,1]d:μxϕ(ξ)μ+1}|,xN,L(x):=\sup_{\mu\in\mathbb{R}}|\{\xi\in[0,1]^{d}:\mu\leq x\cdot\phi(\xi)\leq\mu+1\}|,\quad x\in\mathbb{R}^{N},

be the size of the stationary set associated to xϕx\cdot\phi. Define the convergence exponent and the stationary exponent by

pc\displaystyle p_{c} :=inf{p:[0,1]de(xϕ(ξ))𝑑ξLxp(N)<},\displaystyle:=\inf\Big{\{}p:\Big{\|}\int_{[0,1]^{d}}e(x\cdot\phi(\xi))d\xi\Big{\|}_{L^{p}_{x}(\mathbb{R}^{N})}<\infty\Big{\}},
ps\displaystyle p_{s} :=inf{p:L(x)Lxp(N)<}.\displaystyle:=\inf\Big{\{}p:\|L(x)\|_{L^{p}_{x}(\mathbb{R}^{N})}<\infty\Big{\}}.

We will show that ps=max{pc,N}p_{s}=\max\{p_{c},N\}. The same principle also applies to Fourier transforms of surface measures of semialgebraic sets.

Moreover, via the method of the current paper, we will also show that, for a semialgebraic set SNS\subset\mathbb{R}^{N} of dimension dd, it holds that pc<p_{c}<\infty if and only if the intersection of SS with every hyperplane of N\mathbb{R}^{N} has dimension <d<d.

Although the problem of finding pcp_{c} can be reduced to finding psp_{s} whenever pc>Np_{c}>N, we remark that already for three dimensional Parsell-Vinogradov surfaces (for which the condition pc>Np_{c}>N holds), we encountered significant technical difficulties when estimating the relevant stationary sets. We refer to Remark 4.11 for a more detailed discussion.

In the end, we comment on Corollary 1.4. The estimate (1.21) with a sharp range of pp when d=1d=1 was proven by Drury [Dru85]; indeed, he proved a stronger result with f\|f\|_{\infty} replaced by fq\|f\|_{q} for an optimal range of qq as well. As a consequence, Drury [Dru85] recovered the result of Arkhipov, Chubarikov and Karatsuba [AKC79] and gave an alternative proof for (1.17). It is worth mentioning that Drury’s result can be partially recovered via the broad-narrow analysis of Bourgain and Guth [BG11] and the multi-linear restriction estimates of Bennett, Carbery and Tao [BCT06]; to be more precise, via these more recent tools, one can prove (1.21) for an optimal range of pp, and therefore obtain another proof of (1.17). Moreover, as was shown in [GOZZK20], if one combines the broad-narrow analysis of Bourgain and Guth, with the multi-linear Fourier restriction estimates of Bennett, Bez, Flock and Lee [BBFL18] and the decoupling inequalities for quadratic Parsell-Vinogradov surfaces in Guo and Zhang [GZ19], then one can also recover the result of Mockenhaupt [Moc96] (i.e. the case where d2d\geq 2 and k=2k=2). We tried to prove Corollary 1.4 by this approach, but did not succeed. For d=2d=2 and k=3k=3, we encountered problems in the narrow part of the analysis; while for k4k\geq 4, we encountered significant difficulties in both the broad and the narrow part.

Acknowledgements. S.B. was supported in part by the NSF grant CCF-1910441. S.G. was supported in part by the NSF grant DMS-1800274. R.Z. was supported by the NSF grant DMS-1856541, DMS-1926686 and by the Ky Fan and Yu-Fen Fan Endowment Fund at the Institute for Advanced Study. P.Z. was supported in part by DFG (German Research Foundation) – EXC-2047/1 – 390685813. The authors would like to thank Xianghong Chen, Ziyang Gao, Phil Gressman, Jonathan Pila, Chieu-Minh Tran, Shaozhen Xu, Trevor Wooley and James Wright for valuable discussions at various stages of this project.

2. Bounding oscillatory integrals by the size of stationary sets

In this section, we prove Theorem 1.1, which says that we can bound the oscillatory integral

(2.1) I(Q)=[0,1]de(Q(ξ))𝑑ξI(Q)=\int_{[0,1]^{d}}e(Q(\xi))d\xi

by a constant times the measure of the largest “stationary set”

ϵ:=supμ|{ξ[0,1]d:μQ(ξ)μ+1}|\epsilon:=\sup_{\mu\in\mathbb{R}}\lvert\{\xi\in[0,1]^{d}:\mu\leq Q(\xi)\leq\mu+1\}\rvert

if the real phase function QQ is semialgebraic with bounded complexity.

In order to prove the main theorem, we will change the integral I(Q)I(Q) to a one-dimensional integral of the form

(2.2) S(β)e(β)𝑑β.\int_{\mathbb{R}}S(\beta)\cdot e(\beta)d\beta.

Then we will see that the conclusion follows once we prove that SS changes monotonicity finitely many times.

To prove the latter property, we have to use some tools from real algebraic, and more generally, o-minimal geometry. Recall that a semi-algebraic subset SnS\subset\mathbb{R}^{n} is, by definition, a finite union of subsets, each of which is defined by a formula of the form P=0,Q1,,Q>0P=0,Q_{1},\ldots,Q_{\ell}>0, where each P,Q1,,Q[X1,,Xn]P,Q_{1},\ldots,Q_{\ell}\in\mathbb{R}[X_{1},\ldots,X_{n}]. If the total number of polynomials occurring in the above formulas is bounded by ss, and the maximum degree of these polynomials is bounded by DD, we will say that the complexity of SS (as well as that of the formula) is bounded by k=sDk=sD. A semi-algebraic function ff is a function whose graph is a semi-algebraic set. We will say that the complexity of ff is bounded by kk if the complexity of the semi-algebraic set graph(f)\mathrm{graph}(f) is bounded by kk.

We will need to define generalizations of the notion of semi-algebraic sets and functions. For this purpose, it is convenient to introduce some basic terminology from model theory, where these concepts originated.

2.1. A detour into model theory

In this subsection, we introduce some terminologies and tools in model theory. They will be useful when we prove Lemma 2.9, which is a crucial ingredient in the proof of Theorem 1.1.

A language LL is a triple of tuples

((ci)iI,(fj(mj))jJ,(Rk(nk))kK),((c_{i})_{i\in I},(f_{j}^{(m_{j})})_{j\in J},(R_{k}^{(n_{k})})_{k\in K}),

where each ci,iI,c_{i},i\in I, is a constant symbol, each fj(mj),jJ,f_{j}^{(m_{j})},j\in J, is a function symbol of arity mjm_{j}, and each Rk(nk),kK,R_{k}^{(n_{k})},k\in K, is a relation symbol of arity nkn_{k}.

An LL-structure \mathcal{M} is a tuple

(M,(ci)iI,(fj(mj),)jJ,(Rk(nk),)kK),\left(M,(c_{i}^{\mathcal{M}})_{i\in I},(f_{j}^{(m_{j}),\mathcal{M}})_{j\in J},(R_{k}^{(n_{k}),\mathcal{M}})_{k\in K}\right),

where MM is a set, for each iIi\in I, ciMc_{i}^{\mathcal{M}}\in M, for each jJj\in J, fj(mj),f_{j}^{(m_{j}),\mathcal{M}} is a function MmjMM^{m_{j}}\rightarrow M, and for each kKk\in K, Rk(nk),MnkR_{k}^{(n_{k}),\mathcal{M}}\subset M^{n_{k}} is a nkn_{k}-ary relation on MM. We call

(ci)iI,(fj(mj),)jJ,(Rk(nk),)kK(c_{i}^{\mathcal{M}})_{i\in I},(f_{j}^{(m_{j}),\mathcal{M}})_{j\in J},(R_{k}^{(n_{k}),\mathcal{M}})_{k\in K}

interpretations in \mathcal{M} of the corresponding symbols in LL. It is a common abuse of notation to denote the structure \mathcal{M} by the underlying set MM, and we will take this liberty.

An LL-formula, is obtained using the logic connectives ,,¬\vee,\wedge,\neg (denoting disjunction, conjunction and negation, respectively), and the quantifiers ,\exists,\forall, from atomic formulas. An atomic formula is a formula either of the form t1=t2t_{1}=t_{2}, where t1,t2t_{1},t_{2} are terms built out of the function and constant symbols and variables, or of the form R(n)(t1,,tn)R^{(n)}(t_{1},\ldots,t_{n}) where R(n)R^{(n)} is an nn-ary relation symbol and t1,,tnt_{1},\ldots,t_{n} are terms. A variable XX occurring in an LL-formula ϕ\phi is called a bound variable of the formula, if it appears as X\exists X or X\forall X in ϕ\phi. Otherwise, XX is called a free variable of ϕ\phi. If X1,,XnX_{1},\ldots,X_{n} are the free variables of a formula ϕ\phi, we will denote this by writing ϕ\phi as ϕ(X1,,Xn)\phi(X_{1},\ldots,X_{n}).

Given an LL-formula ϕ(X1,,Xn)\phi(X_{1},\ldots,X_{n}), an LL-structure =(M,)\mathcal{M}=(M,\ldots), and a¯Mn\bar{a}\in M^{n}, one can define in the obvious way (using induction on the structure of the formula ϕ\phi) whether ϕ(a¯)\phi(\bar{a}) is true in the structure MM (denoted Mϕ(a¯)M\models\phi(\bar{a})). Thus, every LL-formula ϕ(X1,,Xn)\phi(X_{1},\ldots,X_{n}) defines a subset, ϕ(M)\phi(M), of MnM^{n}, defined by

ϕ(M)={(a1,,an)Mn:Mϕ(a1,,an)}.\phi(M)=\{(a_{1},\ldots,a_{n})\in M^{n}:M\models\phi(a_{1},\ldots,a_{n})\}.
Example 2.1.

If L=((0,1),(+,),())L=((0,1),(+,\cdot),(\leq)) denotes the language of ordered fields, where 0,10,1 are constant symbols, +,+,\cdot are binary function symbols, and \leq is a binary relation symbol, then X1,X2,X3X_{1},X_{2},X_{3} are variables, 0,X12+(1+1)X2X1+X30,X_{1}^{2}+(1+1)\cdot X_{2}\cdot X_{1}+X_{3} are terms, and

(2.3) ϕ(X2,X3):=(X1)(0X12+(1+1)X2X1+X3)\phi(X_{2},X_{3}):=(\forall X_{1})(0\leq X_{1}^{2}+(1+1)\cdot X_{2}\cdot X_{1}+X_{3})

is a formula with free variables X2,X3X_{2},X_{3}, and a bound variable X1X_{1}.

Denoting by \mathbb{R} the LL-structure whose underlying set is the real numbers, and with 0,1,+,,0,1,+,\cdot,\leq interpreted in the usual way, we have

ϕ()={(x2,x3)2:(x1)0x12+2x2x1+x3}.\phi(\mathbb{R})=\{(x_{2},x_{3})\in\mathbb{R}^{2}:(\forall x_{1}\in\mathbb{R})0\leq x_{1}^{2}+2x_{2}x_{1}+x_{3}\}.

Given an LL-structure MM, a formula ϕ(Y1,,Ym,X1,,Xn)\phi(Y_{1},\ldots,Y_{m},X_{1},\ldots,X_{n}) with free variables

Y1,,Ym,X1,,Xn,Y_{1},\ldots,Y_{m},X_{1},\ldots,X_{n},

and a tuple a¯=(a1,,am)Mm\bar{a}=(a_{1},\ldots,a_{m})\in M^{m}, we call ϕ(a¯,X1,,Xn)\phi(\bar{a},X_{1},\ldots,X_{n}) an L(M)L(M)-formula (LL-formula with parameters in MM) with free variables X1,,XnX_{1},\ldots,X_{n}.

An LL-theory TT is a set of of LL-formulas without free variables (also called LL-sentences). An LL-structure MM is a model of TT (denoted MTM\models T), if MϕM\models\phi for each ϕT\phi\in T. An LL-theory TT admits quantifier elimination if for every LL-formula ϕ(X1,,Xn)\phi(X_{1},\ldots,X_{n}) there exists a quantifier-free LL-formula ψ\psi such that for every model MM of TT, M(ϕ(X1,,Xn)ψ(X1,,Xn))M\models(\phi(X_{1},\ldots,X_{n})\leftrightarrow\psi(X_{1},\ldots,X_{n}){\color[rgb]{0,0,1})} (here and elsewhere, ϕψ\phi\leftrightarrow\psi is the standard abbreviation for the formula (¬ϕψ)(¬ψϕ)(\neg\phi\vee\psi)\wedge(\neg\psi\vee\phi)).

The theory of the LL-structure MM, denoted Th(M)\mathrm{Th}(M), is the set of LL-sentences which are true in MM. Two L(M)L(M)-formulas ϕ(a¯,X1,,Xn)\phi(\bar{a},X_{1},\ldots,X_{n}) and ψ(b¯,X1,,Xn)\psi(\bar{b},X_{1},\ldots,X_{n}) are said to be equivalent modulo Th(M)\mathrm{Th}(M), if M(X1)(Xn)(ϕ(a¯,X1,,Xn)ψ(b¯,X1,,Xn))M\models(\forall X_{1})\cdots(\forall X_{n})(\phi(\bar{a},X_{1},\ldots,X_{n})\leftrightarrow\psi(\bar{b},X_{1},\ldots,X_{n})). The definable sets of an LL-structure MM are sets of the form

{(x1,,xn)Mn:Mϕ(x1,,xn)},\{(x_{1},\ldots,x_{n})\in M^{n}:M\models\phi(x_{1},\ldots,x_{n})\},

where ϕ\phi is an L(M)L(M)-formula. The definable functions are those whose graphs are definable sets.

For the rest of the article, we will denote by L=((0,1),(+,),())L=((0,1),(+,\cdot),(\leq)) the language of ordered fields.

The set \mathbb{R} with the usual interpretations of 0,1,+,,0,1,+,\cdot,\leq is an LL-structure. Notice that, by definition, semi-algebraic sets are definable sets in the LL-structure \mathbb{R}. The Tarski-Seidenberg theorem [Tar51] states that the the LL-theory, RCOF\mathrm{RCOF}, of real closed ordered fields admits quantifier elimination. Here, RCOF\mathrm{RCOF} is the set of LL-sentences axiomatizing ordered fields, in which every non-negative element is a square and every polynomial having odd degree has a root. By definition, we see that the field \mathbb{R} (with the usual interpretations of 0,1,+,,0,1,+,\cdots,\leq) is a model of RCOF\mathrm{RCOF}. As a consequence of the Tarski-Seidenberg theorem [Tar51], one immediately obtains that every definable set of the LL-structure \mathbb{R} is semi-algebraic.

As an illustration of Tarski-Seidenberg theorem, observe that the LL-formula ϕ\phi in (2.3) (which has quantifiers) is equivalent modulo the theory RCOF\mathrm{RCOF} to the quantifier-free LL-formula

ψ(X2,X3):=X2X2X3.\psi(X_{2},X_{3}):=X_{2}\cdot X_{2}\leq X_{3}.

As a consequence,

ϕ()=ψ()={(x2,x3)2:x2x3}.\phi(\mathbb{R})=\psi(\mathbb{R})=\{(x_{2},x_{3})\in\mathbb{R}^{2}:x^{2}\leq x_{3}\}.

Another simple geometric consequence of the Tarski-Seidenberg theorem is that if S1S_{1} and S2S_{2} are a semialgebraic sets in \mathbb{R}, then the set {x:yS1 s.t. x+yS2}\{x\in\mathbb{R}:\exists y\in S_{1}\text{ s.t. }x+y\in S_{2}\} is also semialgebraic.

While the Tarski-Seidenberg theorem is not quantitative as stated above, there are effective versions with complexity estimates. In particular, given any LL-formula ϕ\phi, there exists a quantifier-free LL-formula ψ\psi equivalent to ϕ\phi modulo RCOF\mathrm{RCOF}, such that the number and degrees of the polynomials appearing in ψ\psi is bounded by a function of the number and degrees of the polynomials appearing in ϕ\phi, as well as the number of quantified and free variables. This is in fact a consequence of the original proof of Tarski [Tar51] of the Tarski-Seidenberg theorem, and we omit detailed explanation here. We remark that the above mentioned function can be made explicit, see for instance [BPR06, Theorem 14.16].

2.1.1. o-minimal structures

Let LL^{\prime} be any language containing the binary relation \leq, and let MM be an LL^{\prime}-structure such that the relation \leq defines a total order on MM. The structure MM is called o-minimal if the set of definable subsets of MM is the smallest possible – namely, the set whose elements are finite unions of points and intervals (such subsets are clearly definable by quantifier-free L(M)L^{\prime}(M)-formulas).

Example 2.2.

Recall that LL is the language of ordered fields. The LL-structure \mathbb{R} is an example of an o-minimal structure.

Suppose that L+L_{+} is a language containing LL (we call L+L_{+} an expansion of LL). An L+L_{+}-structure is called an o-minimal expansion of \mathbb{R} if the underlying set of the structure is \mathbb{R}, and the structure is o-minimal (i.e., the definable subsets of \mathbb{R} are precisely the semi-algebraic subsets of \mathbb{R}).

Let us look at an example to better digest this notion. In the following example, we expand the language LL with one additional function symbol.

Example 2.3.

Let L+L_{+} be the expansion of LL by an additional 11-ary function symbol ff, and consider the L+L_{+}-structure sin\mathbb{R}_{\sin} whose underlying set is \mathbb{R}, with the symbols of LL interpreted as before, and the 11-ary function symbol ff interpreted by the trigonometric function sin:\sin:\mathbb{R}\rightarrow\mathbb{R}. Then, sin\mathbb{R}_{\sin} is not an o-minimal expansion of \mathbb{R}, since the definable subset of \mathbb{R} defined by the formula f(X)=0f(X)=0 is the set {nπ:n}\{n\pi:n\in\mathbb{Z}\}, which cannot be expressed as a finite union of points and intervals of \mathbb{R}.

2.1.2. The o-minimal structures an\mathbb{R}_{\mathrm{an}} and an,exp\mathbb{R}_{\mathrm{an},\exp}

The above example shows that the real analytic functions cannot all be definable functions in any o-minimal expansion of \mathbb{R}. For instance, the function sin(x)\sin(x) is never definable in any o-minimal expansion of \mathbb{R}.

However, notice that if we consider a function ff, which is equal to sin(x)\sin(x) on [1,1][-1,1]\subset\mathbb{R}, and defined to be 0 outside of the [1,1][-1,1], then the set of zeros of ff is a semi-algebraic set and hence definable in every o-minimal expansion of \mathbb{R}.

Motivated by this example, we call f:nf:\mathbb{R}^{n}\rightarrow\mathbb{R} a restricted analytic function, if there is an open subset UU containing [1,1]n[-1,1]^{n} in n\mathbb{R}^{n}, and an analytic function g:Ug:U\rightarrow\mathbb{R}, such that

(2.4) f(x)={g(x) for x[1,1]n,0 otherwise.f(x)=\begin{cases}g(x)&\mbox{ for }x\in[-1,1]^{n},\\ 0&\mbox{ otherwise}.\end{cases}

Let LanL_{\mathrm{an}} denote the expansion of LL obtained by including a function symbol (of appropriate arity) for each restricted analytic function. We denote by an\mathbb{R}_{\mathrm{an}} the LanL_{\mathrm{an}} structure with underlying set \mathbb{R}, with the usual interpretations of the symbols of LL, and where we interpret the new symbols by the corresponding restricted analytic functions. It is a theorem of Gabrielov [Gab68] that the LanL_{\mathrm{an}}-structure an\mathbb{R}_{\mathrm{an}} is an o-minimal expansion of \mathbb{R}.

The (unrestricted) exponential function is not a restricted analytic function. We expand the language LanL_{\mathrm{an}} further and include a symbol exp\exp for the exponential function and denote the new language by Lan,expL_{\mathrm{an},\exp}. Denote by an,exp\mathbb{R}_{\mathrm{an},\exp} the Lan,expL_{\mathrm{an},\exp}-structure obtained by interpreting the new symbol exp\exp by the exponential function, and interpreting the symbols of LanL_{\mathrm{an}} as before. It is a theorem of van den Dries, Macintyre, and Marker that:

Theorem 2.4 ([vdDMM94]).

The Lan,expL_{\mathrm{an},\exp}-structure an,exp\mathbb{R}_{\mathrm{an},\exp} is an o-minimal expansion of \mathbb{R}.

Remark 2.5.

Notice that the logarithm function log:(0,)\log:(0,\infty)\rightarrow\mathbb{R} is definable in an,exp\mathbb{R}_{\mathrm{an},\mathrm{exp}}, since its graph

graph(log)={(x,y)2x>0,x=exp(y)}\mathrm{graph}(\log)=\{(x,y)\in\mathbb{R}^{2}\mid x>0,x=\mathrm{exp}(y)\}

is definable in an,exp\mathbb{R}_{\mathrm{an},\mathrm{exp}}.

Let 𝒮\mathcal{S} denote an o-minimal expansion of \mathbb{R}. If we denote by 𝒮n\mathcal{S}_{n} for each n0n\geq 0 the set of subsets of n\mathbb{R}^{n} which are definable in 𝒮\mathcal{S}, then the tuple (𝒮n)n0(\mathcal{S}_{n})_{n\geq 0} satisfy the following properties, which follow directly from the definition of an o-minimal expansion.

  1. (a)

    If n0n\geq 0 and A,B𝒮nA,B\in\mathcal{S}_{n}, then AB,AB,nA𝒮nA\cup B,A\cap B,\mathbb{R}^{n}-A\in\mathcal{S}_{n}. If n,m0n,m\geq 0 and A𝒮m,B𝒮nA\in\mathcal{S}_{m},B\in\mathcal{S}_{n}, then A×B𝒮m+nA\times B\in\mathcal{S}_{m+n}.

  2. (b)

    If π:m×nm\pi:\mathbb{R}^{m}\times\mathbb{R}^{n}\to\mathbb{R}^{m} is the projection map and A𝒮m+nA\in\mathcal{S}_{m+n}, then π(A)𝒮m\pi(A)\in\mathcal{S}_{m}.

  3. (c)

    Elements of 𝒮1\mathcal{S}_{1} are precisely the finite unions of points and open intervals.

Remark 2.6.

While the set of definable sets in an o-minimal expansion of \mathbb{R} is stable under finite set operations and projections (Properties (a) and (b) above), the set of definable functions is not necessarily closed under taking parametric integrals. More precisely, if f:m×nf:\mathbb{R}^{m}\times\mathbb{R}^{n}\rightarrow\mathbb{R} is a definable function in 𝒮\mathcal{S}, then the function

(2.5) g(x)={mf(y,x)𝑑y if m|f(y,x)|𝑑y<,0, otherwise g(x)=\begin{cases}\int_{\mathbb{R}^{m}}f(y,x)dy&\mbox{ if }\int_{\mathbb{R}^{m}}|f(y,x)|dy<\infty,\\ 0,&\mbox{ otherwise }\end{cases}

is not necessarily definable in 𝒮\mathcal{S}. It suffices to take the example of the function

(2.6) f(y,x)={1/y if x>0,1<y<x,0 otherwise,f(y,x)=\begin{cases}1/y&\text{ if }x>0,1<y<x,\\ 0&\text{ otherwise,}\end{cases}

whose graph is a semi-algebraic set and so is clearly definable in the o-minimal structure \mathbb{R}. However, the parametric integral is the logarithm function whose graph is not a semi-algebraic and hence is not definable in \mathbb{R}. On the other hand, notice that g(x)g(x) is definable in the o-minimal expansion an,exp\mathbb{R}_{\mathrm{an},\exp} (cf. Remark 2.5).

In fact, it is proved in [CM11, Theorem 1.3], that if f:m×nf:\mathbb{R}^{m}\times\mathbb{R}^{n}\to\mathbb{R} is a constructible function, then the function defined in (2.5) is constructible (cf. Definition 1.2 in [CM11]). We omit the definition of constructible functions in the sense of [CM11], but list two of their properties, which are the only facts that we will need in this paper.

  1. (1)

    Constructible functions are definable in the o-minimal expansion an,exp\mathbb{R}_{\mathrm{an},\exp} of \mathbb{R}. This follows easily from the definition of constructible functions and the fact that the logarithm function is definable in an,exp\mathbb{R}_{\mathrm{an},\exp}.

  2. (2)

    Semi-algebraic functions are constructible.

An important consequence of the properties (a), (b) and (c) is the topological tameness of definable sets in an o-minimal expansion of \mathbb{R}. Let 𝒮\mathcal{S} be a L𝒮L_{\mathcal{S}}-structure which is an o-minimal expansion of \mathbb{R}. Then the definable sets of 𝒮\mathcal{S} can only have a finite number of connected components (this is a consequence of [vdD98, Theorem 2.9]).

Another important property of the definable sets is that of topological tameness in families.

Proposition 2.7 ([vdD98, Chapter 9, Section 2]).

Let 𝒮\mathcal{S} be a L𝒮L_{\mathcal{S}}-structure which is an o-minimal expansion of \mathbb{R}. Let XX and YY be definable sets and let f:XYf:X\to Y be a definable function. Then, there are finitely many homeomorphism types amongst the fibers Xy=Xf1(y),yYX_{y}=X\cap f^{-1}(y),y\in Y. In particular, there exists a constant Nf0N_{f}\geq 0, such that the number of connected components of Xy,yYX_{y},y\in Y is bounded by NfN_{f}.

As an application of Proposition 2.7, we have:

Proposition 2.8.

Let 𝒮\mathcal{S} be a L𝒮L_{\mathcal{S}}-structure which is an o-minimal expansion of \mathbb{R}. Let h:D×h:\mathbb{R}^{D}\times\mathbb{R}\rightarrow\mathbb{R} be a definable function, and for xDx\in\mathbb{R}^{D}, let N(x)N(x) denote the number of times the function h(x,):h(x,\cdot):\mathbb{R}\rightarrow\mathbb{R} changes monotonicity. Then, supxDN(x)<\sup_{x\in\mathbb{R}^{D}}N(x)<\infty.

Proof.

First observe that for each xDx\in\mathbb{R}^{D}, the function h(x,)h(x,\cdot) is a definable function. Using the monotonicity theorem for definable functions [vdD98, Theorem 1.2, Chapter 3], for each xDx\in\mathbb{R}^{D}, there exists a finite partition of \mathbb{R} into points and open intervals, such that over each open interval the function h(x,)h(x,\cdot) is either constant, strictly increasing, or strictly decreasing. Hence, the set of points at which the function h(x,)h(x,\cdot) changes monotonicity is contained in the set of end points of these intervals, and in particular is a finite subset of \mathbb{R}.

Now, let S={(x,t)D×h(x,) changes monotonicity at t}S=\{(x,t)\in\mathbb{R}^{D}\times\mathbb{R}\mid h(x,\cdot)\mbox{ changes monotonicity at }t\}. Since changing monotonicity of a function is expressible using a first-order formula (involving quantifiers) in the language L𝒮L_{\mathcal{S}}, it follows that the set SS is definable in o-minimal structure 𝒮\mathcal{S}.

Now, applying Proposition 2.7, we get that there are finitely many homeomorphism types amongst the fibers of the map (x,t)x(x,t)\mapsto x restricted to SS, noting that this map is clearly definable in 𝒮\mathcal{S}. Moreover, each fiber has finitely many points using the observation in the first paragraph of the proof. The proposition follows. ∎

2.2. Proof of Theorem 1.1

With the preparation above, let us prove a lemma that will play a crucial role in the proof of Theorem 1.1.

Lemma 2.9.

Let d1d\geq 1 and let UU be a semialgebraic set in d+1\mathbb{R}^{d+1} with complexity k\leq k. Assume further that UU is bounded. For each β\beta\in\mathbb{R}, we define

(2.7) AU(β)=d𝟏U(ξ,β)𝑑ξ.A_{U}(\beta)=\int_{\mathbb{R}^{d}}\mathbf{1}_{U}(\xi,\beta)d\xi.

Then the function AUA_{U} changes monotonicity Od,k(1)O_{d,k}(1) times.

Proof of Lemma 2.9.

First observe that for each k,d0k,d\geq 0 there exists D=D(k,d),N=N(k,d)D=D(k,d),N=N(k,d), and a finite set

Φk,d={ϕ1(Y1,,YD,X1,,Xd+1),,ϕN(Y1,,YD,X1,,Xd+1)}\Phi_{k,d}=\{\phi_{1}(Y_{1},\ldots,Y_{D},X_{1},\ldots,X_{d+1}),\ldots,\phi_{N}(Y_{1},\ldots,Y_{D},X_{1},\ldots,X_{d+1})\}

where each ϕi\phi_{i} is a quantifier-free LL-formula, such that if Ud+1U\subset\mathbb{R}^{d+1} is a semi-algebraic set of complexity bounded by kk, then there exists 1iN1\leq i\leq N and ηD\eta\in\mathbb{R}^{D} such that

U={(x1,,xd+1)d+1ϕi(η,X1,,Xd+1)}.U=\{(x_{1},\ldots,x_{d+1})\in\mathbb{R}^{d+1}\mid\mathbb{R}\models\phi_{i}(\eta,X_{1},\ldots,X_{d+1})\}.

Intuitively, the above property holds because by definition, our set UU can be described by an L()L(\mathbb{R})-formula involving Ok,d(1)O_{k,d}(1) many polynomials of degree Ok,d(1)O_{k,d}(1), parameters in \mathbb{R}, logic connectives and constant symbols.

For each i,1iNi,1\leq i\leq N, let ViD×d+1V_{i}\subset\mathbb{R}^{D}\times\mathbb{R}^{d+1} be the set defined by ϕi\phi_{i}, and let π:D×d+1D\pi:\mathbb{R}^{D}\times\mathbb{R}^{d+1}\rightarrow\mathbb{R}^{D} be the projection map to the first factor.

For 1iN1\leq i\leq N, consider the functions AiA_{i} on D+1=D×\mathbb{R}^{D+1}=\mathbb{R}^{D}\times\mathbb{R} defined as follows: For ηD\eta\in\mathbb{R}^{D} and β\beta\in\mathbb{R}, we set

(2.8) Ai(η,β):=d𝟏Vi(η,ξ,β)𝑑ξA_{i}(\eta,\beta):=\int_{\mathbb{R}^{d}}\mathbf{1}_{V_{i}}(\eta,\xi,\beta)d\xi

whenever the above integral is finite, and A(η,β)=0A(\eta,\beta)=0 otherwise.

The functions 𝟏Vi\mathbf{1}_{V_{i}} are semialgebraic and thus definable in an\mathbb{R}_{\mathrm{an}}. By Theorem 1.3 in [CM11] (as mentioned in Remark 2.6), Ai(η,β)A_{i}(\eta,\beta) is a constructible function on D+1\mathbb{R}^{D+1}. Using the properties of constructible functions listed in Remark 2.6, we obtain that Ai(η,β)A_{i}(\eta,\beta) is definable in an,exp\mathbb{R}_{\mathrm{an},\exp}.

It now follows from Proposition 2.8 that there exists Mi=Mi(k,d)>0M_{i}=M_{i}(k,d)>0, such that the number of times the function Ai(η,),ηDA_{i}(\eta,\cdot),\eta\in\mathbb{R}^{D} changes monotonicity is bounded by MiM_{i}. Let M(k,d)=max1iNMiM(k,d)=\max_{1\leq i\leq N}M_{i}. It follows that the number of times the function AUA_{U} changes monotonicity is bounded by M(k,d)M(k,d), observing that there exists i,1ini,1\leq i\leq n, ηD\eta\in\mathbb{R}^{D}, such that AU(β)=Ai(η,β)A_{U}(\beta)=A_{i}(\eta,\beta) for β\beta\in\mathbb{R}. ∎

With Lemma 2.9 in mind, we now prove Theorem 1.1.

Proof of Theorem 1.1.

Fix a constant 0<δ0<120<\delta_{0}<\frac{1}{2} (in our proof δ0=0.1\delta_{0}=0.1 will work). In the proof we will suppress the dependence on the constant δ0\delta_{0}. By a change of variables, we have

(δ0δ0e(α)𝑑α)([0,1]de(Q(ξ))𝑑ξ)=[0,1]dδ0δ0e(Q(ξ)+α)𝑑α𝑑ξ=[0,1]dQ(ξ)δ0Q(ξ)+δ0e(β)𝑑β𝑑ξ=|{ξ[0,1]d:Q(ξ)[βδ0,β+δ0]}|e(β)𝑑β.\Big{(}\int_{-\delta_{0}}^{\delta_{0}}e(\alpha)d\alpha\Big{)}\Big{(}\int_{[0,1]^{d}}e(Q(\xi))d\xi\Big{)}=\int_{[0,1]^{d}}\int_{-\delta_{0}}^{\delta_{0}}e(Q(\xi)+\alpha)d\alpha d\xi\\ =\int_{[0,1]^{d}}\int_{Q(\xi)-\delta_{0}}^{Q(\xi)+\delta_{0}}e(\beta)d\beta d\xi=\int_{\mathbb{R}}|\{\xi\in[0,1]^{d}:Q(\xi)\in[\beta-\delta_{0},\beta+\delta_{0}]\}|\cdot e(\beta)d\beta.

Here, |||\cdot| denotes the Lebesgue measure. Note that δ0δ0e(α)𝑑α\int_{-\delta_{0}}^{\delta_{0}}e(\alpha)d\alpha is a nonzero constant (depending only on δ0\delta_{0}) as 0<δ0<120<\delta_{0}<\frac{1}{2}. Hence, if we define a stationary set to be

(2.9) SQ;δ0(β)={ξ[0,1]d:Q(ξ)[βδ0,β+δ0]},S_{Q;\delta_{0}}(\beta)=\{\xi\in[0,1]^{d}:Q(\xi)\in[\beta-\delta_{0},\beta+\delta_{0}]\},

then we have

(2.10) |[0,1]de(Q(ξ))𝑑ξ|||SQ;δ0(β)|e(β)dβ|.\Big{|}\int_{[0,1]^{d}}e(Q(\xi))d\xi\Big{|}\sim\Big{|}\int_{\mathbb{R}}|S_{Q;\delta_{0}}(\beta)|e(\beta)d\beta\Big{|}.

Since QQ is bounded, the function |SQ;δ0()||S_{Q;\delta_{0}}(\cdot)| is compactly supported. We claim that it is piecewise monotonic and that it only changes monotonicity Od,k(1)O_{d,k}(1) many times. This claim follows from Lemma 2.9 in a straightforward way, and we postpone its justification to the end of this proof.

We now explain how to get the desired conclusion from the above claim. We decompose \mathbb{R} into a union of Od,k(1)O_{d,k}(1) many closed intervals jIj\bigcup_{j}I_{j} such that the interiors of IjI_{j} are disjoint and that the function |SQ;δ0()||S_{Q;\delta_{0}}(\cdot)| is compactly supported and monotonic on each IjI_{j}. For each IjI_{j}, the total variation of |SQ;δ0()||S_{Q;\delta_{0}}(\cdot)| on IjI_{j} is bounded by 2supβ|SQ;δ0(β)|2\sup_{\beta\in\mathbb{R}}|S_{Q;\delta_{0}}(\beta)|, uniformly in jj. By integration by parts, we see

(2.11) |Ij|SQ;δ0(β)|e(β)dβ|supβ|SQ;δ0(β)|,\Big{|}\int_{I_{j}}|S_{Q;\delta_{0}}(\beta)|e(\beta)d\beta\Big{|}\lesssim\sup_{\beta\in\mathbb{R}}|S_{Q;\delta_{0}}(\beta)|,

uniformly in jj. Hence, we get

(2.12) ||SQ;δ0(β)|e(β)dβ|j|Ij|SQ;δ0(β)|e(β)dβ|d,ksupβ|SQ;δ0(β)|d,kϵ\Big{|}\int_{\mathbb{R}}|S_{Q;\delta_{0}}(\beta)|e(\beta)d\beta\Big{|}\leq\sum_{j}\Big{|}\int_{I_{j}}|S_{Q;\delta_{0}}(\beta)|e(\beta)d\beta\Big{|}\lesssim_{d,k}\sup_{\beta\in\mathbb{R}}|S_{Q;\delta_{0}}(\beta)|\lesssim_{d,k}\epsilon

by assumption. This is the desired conclusion.

Finally, we justify our claim that |SQ;δ0||S_{Q;\delta_{0}}| is piecewise monotonic and that it only changes monotonicity Od,k(1)O_{d,k}(1) many times. Consider the set

(2.13) Γ(Q):={(ξ,β)d×:βδ0Q(ξ)β+δ0,ξ[0,1]d}.\Gamma(Q):=\{(\xi,\beta)\in\mathbb{R}^{d}\times\mathbb{R}:\beta-\delta_{0}\leq Q(\xi)\leq\beta+\delta_{0},\xi\in[0,1]^{d}\}.

The set Γ(Q)\Gamma(Q) is bounded and can be described as a “vertical” neighborhood of the graph of QQ.

Observe that since QQ is a semi-algebraic function, graph(Q)\mathrm{graph}(Q) is a semi-algebraic subset of d+1\mathbb{R}^{d+1} and so defined by a L()L(\mathbb{R})-formula ϕ(X1,,Xd+1)\phi(X_{1},\ldots,X_{d+1}). Then Γ(Q)\Gamma(Q) is defined by the formula

ψ(X1,,Xd+1):=(Y)ϕ(X1,,Xd,Y)(Xd+1Y+δ0)(YXk+1+δ0).\psi(X_{1},\ldots,X_{d+1}):=(\exists Y)\phi(X_{1},\ldots,X_{d},Y)\wedge(X_{d+1}\leq Y+\delta_{0})\wedge(Y\leq X_{k+1}+\delta_{0}).

Using an effective version of Tarski-Seidenberg theorem (that was mentioned in Subsection 2.1; see e.g. [BPR06, Theorem 14.16] for a reference), we obtain that ψ\psi is equivalent to a quantifier-free formula ψ~\widetilde{\psi} such that the number of polynomials and their degrees that occur in ψ~\widetilde{\psi} is Od,k(1)O_{d,k}(1). And so Γ(Q)\Gamma(Q) is semialgebraic with complexity Od,k(1)O_{d,k}(1). Now we apply Lemma 2.9 to the set Γ(Q)\Gamma(Q), and note that SQ;δ0(β)=AΓ(Q)(β)S_{Q;\delta_{0}}(\beta)=A_{\Gamma(Q)}(\beta) in the notation of that lemma. By the conclusion of Lemma 2.9, we deduce the claim in the beginning of this paragraph. ∎

Remark 2.10.

In Theorem 1.1, the amplitude function of the oscillatory integral is taken to be the sharp cut-off 𝟏[0,1]d\mathbf{1}_{[0,1]^{d}}. For a compactly supported smooth amplitude function, one can apply a Fourier series expansion and then apply Theorem 1.1. In applications, due to the rapid decay of Fourier coefficients, the extra summation that is brought in by Fourier series expansion usually will not cause any problem. For example, in Tarry’s problem, one can insert a compactly supported smooth amplitude function in (1.14), and ask what the convergence exponent is. It is elementary to see that it coincides with the one of sharp cut-off, that is, p2,kp_{2,k}.

3. Theorem 1.2: Reduction to a spread out case

Sections 3 and 4 are devoted to the proof of Theorem 1.2. From now on, we will fix d=2d=2 and abbreviate p2,kp_{2,k} to pkp_{k}. To simplify notation, we denote

(3.1) qk=16k(k+1)(k+2)+2.q_{k}=\frac{1}{6}k(k+1)(k+2)+2.

Under this notation, to prove Theorem 1.2, it is equivalent to prove that pk=qkp_{k}=q_{k} for every k2k\geq 2.

We will use Ek1(x)E_{k}1(x) to denote the function E[0,1]d(d,k)1(x)E_{[0,1]^{d}}^{(d,k)}1(x). Our goal is to show that

(3.2) |{xN:|Ek1|(x)[δ,2δ]}|k|log+δ|k1δqk|\{x\in\mathbb{R}^{N}:|E_{k}1|(x)\in[\delta,2\delta]\}|\lesssim_{k}\lvert\log_{+}\delta\rvert^{k-1}\delta^{-q_{k}}

for every δ1\delta\leq 1, where

(3.3) log+δ:=log(1+1δ).\log_{+}\delta:=\log\big{(}1+\frac{1}{\delta}\big{)}.

This will imply the upper bound of pkp_{k} that pkqkp_{k}\leq q_{k}. We will use P(ξ;x)P(\xi;x) to denote the polynomial xϕk(ξ)x\cdot\phi_{k}(\xi). For a polynomial P:[0,1]2P:[0,1]^{2}\to\mathbb{R} and real numbers c>0c>0 and μ\mu, define

(3.4) Zc(P,μ):={ξ[0,1]2:μP(ξ)μ+c}.Z_{c}(P,\mu):=\{\xi\in[0,1]^{2}:\mu\leq P(\xi)\leq\mu+c\}.

For a given xx, since the measure of Z1(P(;x),μ)Z_{1}(P(\cdot\ ;x),\mu) depends continuously on μ\mu, we can choose μx\mu_{x} such that

(3.5) |Z1(P(;x),μx)|=supμ|Z1(P(;x),μ)|.|Z_{1}(P(\cdot\ ;x),\mu_{x})|=\sup_{\mu\in\mathbb{R}}|Z_{1}(P(\cdot\ ;x),\mu)|.

To simplify notation, we denote

(3.6) Zx:=Z1(P(;x),μx).Z_{x}:=Z_{1}(P(\cdot\ ;x),\mu_{x}).

From Theorem 1.1, we immediately obtain that there exists Ck>0C_{k}>0 such that for every δ1\delta\leq 1, it holds that

(3.7) {xN:|Ek1|(x)[δ,2δ]}Lδ/Ck,\{x\in\mathbb{R}^{N}:|E_{k}1|(x)\in[\delta,2\delta]\}\subseteq L_{\delta/C_{k}},

where

Lδ:={xN:|Zx|>δ}.L_{\delta}:=\{x\in\mathbb{R}^{N}:|Z_{x}|>\delta\}.

We will show that there exists Ck<C_{k}<\infty such that

(3.8) |Lδ|Ck|log+δ|k1δqk,|L_{\delta}|\leq C_{k}\lvert\log_{+}\delta\rvert^{k-1}\delta^{-q_{k}},

for every δ(0,1]\delta\in(0,1]. This will be proven via an inductive argument. More precisely, we will show that there exists Ck,1>0C_{k,1}>0 such that for every sufficiently large dyadic number K1K\geq 1 (picking K210kK\geq 2^{10k} will be enough), we can find another constant Ck,KC_{k,K} such that

(3.9) |Lδ|KKk(k+1)(k+2)/6|LδK/Ck,1|+Ck,K|log+δ|k1δk(k+1)(k+2)/62.\lvert L_{\delta}\rvert\leq K\cdot K^{k(k+1)(k+2)/6}\lvert L_{\delta K/C_{k,1}}\rvert+C_{k,K}\lvert\log_{+}\delta\rvert^{k-1}\delta^{-k(k+1)(k+2)/6-2}.

Since L1=L_{1}=\emptyset, this implies our claim (3.8) after choosing KK so large that

Kk(k+1)(k+2)/6+1<(K/Ck,1)k(k+1)(k+2)/6+2K^{k(k+1)(k+2)/6+1}<(K/C_{k,1})^{k(k+1)(k+2)/6+2}

and unrolling the recursion (3.9).

Remark 3.1.

The main contribution in the recursive estimate (3.9) comes from the second summand on the right-hand side. This is due to the fact that the power of KK in the first summand is strictly smaller than pkp_{k}. It is this fact that allows us to use a fixed value of KK and leads to only a logarithmic loss in (3.8).

Remark 3.2.

The choice of Ck,1C_{k,1} will be made in Lemma 4.7.

Let K1K\gg 1 be large dyadic number to be determined. Let 𝒮K\mathcal{S}_{K} be the collection of all (vertical) dyadic rectangles SK[0,1]2S_{K}\subset[0,1]^{2} of size 1×1/K1\times 1/K. We have |𝒮K|=K|\mathcal{S}_{K}|=K. Let Ck,1>1C_{k,1}>1 be a large constant to be determined. We write LδL_{\delta} as a disjoint union

(3.10) Lδ=Lδ,conLδ,sprd,L_{\delta}=L_{\delta,\mathrm{con}}\cup L_{\delta,\mathrm{sprd}},

where

(3.11) Lδ(SK):={xLδ:|ZxSK|>δ/Ck,1}.\begin{split}\quad L_{\delta}(S_{K}):=\{x\in L_{\delta}:|Z_{x}\cap S_{K}|>\delta/C_{k,1}\}.\end{split}
Lδ,con:=SK𝒮KLδ(SK),L_{\delta,\mathrm{con}}:=\bigcup_{S_{K}\in\mathcal{S}_{K}}L_{\delta}(S_{K}),

We will control the sizes of Lδ,conL_{\delta,\mathrm{con}} and Lδ,sprdL_{\delta,\mathrm{sprd}} separately. For xLδx\in L_{\delta}, we say that it is in the concentrated case if xLδ,conx\in L_{\delta,\mathrm{con}} and that it is in the spread out case if xLδ,sprdx\in L_{\delta,\mathrm{sprd}}.

Remark 3.3.

The concentrated/spread out dichotomy here is inspired by the broad-narrow dichotomy of Bourgain-Guth in [BG11]. We leave the comparison to the interested readers.

In the remaining part of this section we will control Lδ,conL_{\delta,\mathrm{con}}. Let us start with estimating |Lδ(SK)||L_{\delta}(S_{K})| for a fixed SKS_{K}. Without loss of generality, take SK=[0,1/K]×[0,1]S_{K}=[0,1/K]\times[0,1]. For an xNx\in\mathbb{R}^{N}, define

(3.12) x¯:=(xβ/Kβ1)1|β|k,\bar{x}:=(x_{\beta}/K^{\beta_{1}})_{1\leq|\beta|\leq k},

with β=(β1,β2)2\beta=(\beta_{1},\beta_{2})\in\mathbb{N}^{2}, so that P((ξ1,ξ2);x)=P((Kξ1,ξ2);x¯)P((\xi_{1},\xi_{2});x)=P((K\xi_{1},\xi_{2});\bar{x}). Then, for xLδ(SK)x\in L_{\delta}(S_{K}), we have

(3.13) |Z1(P(;x¯),μx)|=K|ZxSK|>Kδ/Ck,1.|Z_{1}(P(\cdot\ ;\bar{x}),\mu_{x})|=K|Z_{x}\cap S_{K}|>K\delta/C_{k,1}.

By definition of LL_{\cdot}, we have

(3.14) {x¯N:|Zx¯|>Kδ/Ck,1}=LKδ/Ck,1.\{\bar{x}\in\mathbb{R}^{N}:|Z_{\bar{x}}|>K\delta/C_{k,1}\}=L_{K\delta/C_{k,1}}.

By scaling, this implies

(3.15) |Lδ(SK)||LKδ/Ck,1||β|kKβ1=Kk(k+1)(k+2)/6|LKδ/Ck,1|.|L_{\delta}(S_{K})|\leq\lvert L_{K\delta/C_{k,1}}\rvert\prod_{\lvert\beta\rvert\leq k}K^{\beta_{1}}=K^{k(k+1)(k+2)/6}\lvert L_{K\delta/C_{k,1}}\rvert.

We sum over SKS_{K} and obtain

(3.16) |Lδ,con|KKk(k+1)(k+2)/6|LKδ/Ck,1|.|L_{\delta,\mathrm{con}}|\leq K\cdot K^{k(k+1)(k+2)/6}\lvert L_{K\delta/C_{k,1}}\rvert.

This finishes the argument for the concentrated case.

4. Theorem 1.2: The spread out case

In this section, we will show that

(4.1) |Lδ,sprd|Ck,K|log+δ|k1δk(k+1)(k+2)/62,\lvert L_{\delta,\mathrm{sprd}}\rvert\leq C_{k,K}\lvert\log_{+}\delta\rvert^{k-1}\delta^{-k(k+1)(k+2)/6-2},

thus finishing the proof of the desired estimate (3.9). Next we sketch the proof ideas before working out the details,

For xLδ,sprdLδx\in L_{\delta,\mathrm{sprd}}\subset L_{\delta}, recall that the stationary set Zx={ξ[0,1]2:μxP(ξ;x)μx+1}Z_{x}=\{\xi\in[0,1]^{2}:\mu_{x}\leq P(\xi;x)\leq\mu_{x}+1\} has measure at least δ\delta. Let us think about what such a ZxZ_{x} may look like. Note that ZxZ_{x} has bounded complexity. In the second subsection, we will prove that a semialgebraic set of bounded complexity in [0,1]d[0,1]^{d} that has measure at least δ>0\delta>0 is “not far from” a union of δ\delta-cubes. This is essentially Lemma 4.9 in two dimensions.111There is a higher dimensional version that can be proved in an identical way. We omit that more general version here since it is irrelevant to our current problem. Before proving such a lemma we will need some preparations (done in the first subsection) using elementary real algebraic geometry.

Since ZxZ_{x} has bounded complexity, the (quantitative) Tarski-Seidenberg theorem shows that its projection to the ξ1\xi_{1}-axis is a union of boundedly many points and intervals. If we pretend that ZxZ_{x} is a union of δ\delta-squares, by the fact that it is spread out in the ξ1\xi_{1} direction (thus hitting many vertical 1/K1/K-strips), we see that the projection of ZxZ_{x} to the ξ1\xi_{1}-axis has to contain a “long interval” (with constant length) if we choose Ck,1C_{k,1} large enough. This means we can find an interval I[0,1]I\subset[0,1] on the ξ1\xi_{1}-axis of constant length such that for all dyadic interval I~\tilde{I} of length δ\delta in II, there is a δ\delta-square ΔI~\Delta_{\tilde{I}} in ZxZ_{x} whose projection to the ξ1\xi_{1}-axis is I~\tilde{I}. In real life, ZxZ_{x} is not honestly a union of δ\delta-squares but we still have something very similar to the conclusion above thanks to Lemma 4.7.

Finally, we fix a constant (k+1k+1, to be more accurate) many evenly-spaced I~\tilde{I} and look at all possible tuples (ΔI~)I~(\Delta_{\tilde{I}})_{\tilde{I}}. For each tuple, if every δ\delta-square in it is essentially contained in ZxZ_{x}, we will see that xx has to be contained in a very specific rectangular box (depending on the particular tuple (ΔI~)I~(\Delta_{\tilde{I}})_{\tilde{I}}). Geometrically, this is the dual box to the convex hull of all caps corresponding to all ΔI~\Delta_{\tilde{I}} in that tuple. Therefore the union of all such rectangular boxes will contain Lδ,sprdL_{\delta,\mathrm{sprd}}. Simply by adding up the volume of all the rectangular boxes we get the desired upper bound of |Lδ,sprd|\lvert L_{\delta,\mathrm{sprd}}\rvert and finish the proof. This is carried out in the last subsection.

Remark 4.1.

For general Sd,kS_{d,k} when d3d\geq 3, we expect this proof framework to continue working but also expect a lot more new technical difficulties and hence do not pursue the more general problem here. See Remark 4.11 for a discussion.

4.1. Shifts of semialgebraic sets

Lemma 4.2 (Finite boundary).

For every κ\kappa\in\mathbb{N} there exists Bκ<B_{\kappa}<\infty such that every semialgebraic subset Γ\Gamma\subseteq\mathbb{R} of complexity κ\leq\kappa has at most BκB_{\kappa} boundary points.

Proof of Lemma 4.2.

By definition, Γ\Gamma is a union of Oκ(1)O_{\kappa}(1) many subsets Γj\Gamma_{j} where each Γj\Gamma_{j} is a set defined by Oκ(1)O_{\kappa}(1) many polynomial equations or inequalities of degree Oκ(1)O_{\kappa}(1). This implies that each Γj\Gamma_{j} is an intersection of Oκ(1)O_{\kappa}(1) many larger sets, each larger set being a union of Oκ(1)O_{\kappa}(1) many points or intervals. Hence each Γj\Gamma_{j} is a union of Oκ(1)O_{\kappa}(1) many points or intervals. Taking the union, we deduce that Γ\Gamma is also a union of Oκ(1)O_{\kappa}(1) many points or intervals and the conclusion follows. ∎

Corollary 4.3 (Shifts of a bounded complexity set).

Let Γ[0,1]\Gamma\subseteq[0,1] be a semialgebraic set of complexity κ\leq\kappa. Then, for every δ>0\delta>0, we have

|(Γ+[δ,δ])Γ|κδ.\lvert(\Gamma+[-\delta,\delta])\setminus\Gamma\rvert\lesssim_{\kappa}\delta.
Proof of Corollary 4.3.

By Lemma 4.2, Γ\Gamma is the union of Oκ(1)O_{\kappa}(1) many intervals, which immediately implies the desired bound. ∎

Lemma 4.4.

For every k,κk,\kappa\in\mathbb{N}, there exists a small constant ck,κ>0c_{k,\kappa}>0 such that, for every δ>0\delta>0 and every semialgebraic set Γ[0,1]2\Gamma\subseteq[0,1]^{2} with complexity κ\leq\kappa and measure |Γ|>δ\lvert\Gamma\rvert>\delta, we have

|a{0,,k}2(Γck,κδa)|>δ/2.\Big{\lvert}\bigcap_{a\in\{0,\dotsc,k\}^{2}}(\Gamma-c_{k,\kappa}\delta a)\Big{\rvert}>\delta/2.
Proof of Lemma 4.4.

Let e1=(1,0)e_{1}=(1,0) and e2=(0,1)e_{2}=(0,1) be the unit vectors. Let c=ck,κ>0c=c_{k,\kappa}>0 be a small number that is to be chosen. For any δ>0\delta>0, the set

a1{0,,k}(Γcδa1e1)\bigcap_{a_{1}\in\{0,\dotsc,k\}}(\Gamma-c\delta a_{1}e_{1})

will be a semialgebraic set of complexity at most κ=κ(k,κ)\kappa^{\prime}=\kappa^{\prime}(k,\kappa). Using Corollary 4.3 in the first variable and integrating, we see that

|a1{0,,k}(Γcδa1e1)|δCκcδk,\big{\lvert}\bigcap_{a_{1}\in\{0,\dotsc,k\}}(\Gamma-c\delta a_{1}e_{1})\big{\rvert}\geq\delta-C_{\kappa}c\delta k,

for some large constant CκC_{\kappa} depending only on κ\kappa. If c1/(4kCκ)c\leq 1/(4kC_{\kappa}), this will be 3δ/4\geq 3\delta/4. Using Corollary 4.3 in the second variable and integrating, we see that

|a{0,,k}2(Γcδa)|=|a2{0,,k}(a1{0,,k}2(Γcδa1e1))cδa2e2|3δ/4Cκcδk,\big{\lvert}\bigcap_{a\in\{0,\dotsc,k\}^{2}}(\Gamma-c\delta a)\big{\rvert}=\big{\lvert}\bigcap_{a_{2}\in\{0,\dotsc,k\}}\bigl{(}\bigcap_{a_{1}\in\{0,\dotsc,k\}^{2}}(\Gamma-c\delta a_{1}e_{1})\bigr{)}-c\delta a_{2}e_{2}\big{\rvert}\geq 3\delta/4-C_{\kappa^{\prime}}c\delta k,

for some large constant CκC_{\kappa^{\prime}} depending only on κ\kappa^{\prime}. If c1/(4kCκ)c\leq 1/(4kC_{\kappa^{\prime}}), then this is δ/2\geq\delta/2. Summarizing, it suffices to take ck,κ:=1/max(4kCκ,4kCκ)c_{k,\kappa}:=1/\max(4kC_{\kappa},4kC_{\kappa^{\prime}}). ∎

Remark 4.5.

Lemma 4.4 is also true when the dimension 22 is replaced by an arbitrary dd. One just needs to repeat the procedure in the proof dd times. We do not need that more general result in this paper but record it here as it may be of independent interest.

4.2. Large projections of stationary sets

In this subsection, we fix xLδ,sprdx\in L_{\delta,\mathrm{sprd}}, and discuss some geometry of a particular stationary set ZxZ_{x}.

We apply Lemma 4.4 to the set ZxZ_{x}. Its complexity is bounded by a constant depending on kk. Therefore, we can find a small constant ck>0c_{k}>0 such that for the set

(4.2) Z~x:=a{0,,k}2(Zxckδa),\tilde{Z}_{x}:=\bigcap_{a\in\{0,\dotsc,k\}^{2}}\bigl{(}Z_{x}-c_{k}\delta a\bigr{)},

we have |Z~x|>δ/2\lvert\tilde{Z}_{x}\rvert>\delta/2. If we also know that xLδ,sprdx\in L_{\delta,\mathrm{sprd}}, then we will see that the set Z~x\tilde{Z}_{x} has a “large” projection in the horizontal axis.

Lemma 4.6.

For every xLδ,sprdx\in L_{\delta,\mathrm{sprd}}, it holds that

(4.3) |{SK𝒮K\nonscript|\nonscriptZ~xSK}|Ck,1/2.\lvert\{S_{K}\in\mathcal{S}_{K}\nonscript\>|\allowbreak\nonscript\>\mathopen{}\tilde{Z}_{x}\cap S_{K}\neq\emptyset\}\rvert\geq C_{k,1}/2.
Proof of Lemma 4.6.

Let 𝒮~K𝒮K\tilde{\mathcal{S}}_{K}\subseteq\mathcal{S}_{K} be the set consisting of those strips that have non-empty intersection with Z~x\tilde{Z}_{x}. Using that xLδ(SK)x\not\in L_{\delta}(S_{K}) for any SK𝒮KS_{K}\in\mathcal{S}_{K}, we obtain

δ/2<|Z~x|=SK𝒮~K|Z~xSK|SK𝒮~K|ZxSK|SK𝒮~Kδ/Ck,1=δ|𝒮~K|/Ck,1.\delta/2<\lvert\tilde{Z}_{x}\rvert=\sum_{S_{K}\in\tilde{\mathcal{S}}_{K}}\lvert\tilde{Z}_{x}\cap S_{K}\rvert\leq\sum_{S_{K}\in\tilde{\mathcal{S}}_{K}}\lvert Z_{x}\cap S_{K}\rvert\leq\sum_{S_{K}\in\tilde{\mathcal{S}}_{K}}\delta/C_{k,1}=\delta\lvert\tilde{\mathcal{S}}_{K}\rvert/C_{k,1}.

Rearranging the terms gives the claim. ∎

Lemma 4.7.

If Ck,1C_{k,1} is large enough depending on kk, then, for every xLδ,sprdx\in L_{\delta,\mathrm{sprd}}, the projection π1Z~x\pi_{1}\tilde{Z}_{x} contains a dyadic interval of length 1/K1/K. Here π1:2\pi_{1}:\mathbb{R}^{2}\to\mathbb{R} denote the projection to the first variable.

Proof of Lemma 4.7.

Using an effective version of quantifier-elimination in the theory of real closed fields (that was mentioned in Subsection 2.1; see e.g. [BPR06, Theorem 14.16] for a reference) π1Z~x\pi_{1}\tilde{Z}_{x} is semialgebraic set having bounded complexity depending only on kk. By Lemma 4.2, it is the union of at most C~k\tilde{C}_{k} intervals, where C~k\tilde{C}_{k} depends only on kk. If Ck,1>4C~kC_{k,1}>4\tilde{C}_{k}, then it follows from Lemma 4.6 that π1Z~x\pi_{1}\tilde{Z}_{x} contains at least one full dyadic interval of length 1/K1/K. ∎

Remark 4.8.

From this point on, all estimates are allowed to depend implicitly on both kk and KK; these implicit constants will accumulate to the constant Ck,KC_{k,K} in (3.9). To simplify notation, the dependence on KK and kk will often be dropped.

By Lemma 4.7 and a standard pigeonholing argument, we can find a subset L~δ,sprdLδ,sprd\widetilde{L}_{\delta,\mathrm{sprd}}\subset L_{\delta,\mathrm{sprd}} and an interval I[0,1]I\subset[0,1] of length 1/K1/K such that

|L~δ,sprd||Lδ,sprd|/K|\widetilde{L}_{\delta,\mathrm{sprd}}|\geq|L_{\delta,\mathrm{sprd}}|/K

and for every xL~δ,sprdx\in\widetilde{L}_{\delta,\mathrm{sprd}} we have Iπ1Z~xI\subseteq\pi_{1}\tilde{Z}_{x}. Let

(4.4) t0,t1,,tkIt_{0},t_{1},\dots,t_{k}\in I

be a 1/(kK)1/(kK)-separated set.

Let 𝒫(δ)\mathcal{P}(\delta) be the partition of [0,1]2[0,1]^{2} into dyadic squares Δ\Delta of side length δ\delta. Next, for each xLδ,sprdx\in L_{\delta,\mathrm{sprd}}, we will construct a sub-collection 𝒫x(δ)𝒫(δ)\mathcal{P}_{x}(\delta)\subset\mathcal{P}(\delta).

Roughly speaking, the purpose of this construction is that we want ZxZ_{x} to be approximated by a union of certain lattice dyadic δ\delta-squares. To this end, we choose sufficiently many Δ𝒫x(δ)\Delta\in\mathcal{P}_{x}(\delta) such that the union of all Δ𝒫x(δ)\Delta\in\mathcal{P}_{x}(\delta) approximates ZxZ_{x} well. Moreover when Δ𝒫x(δ)\Delta\in\mathcal{P}_{x}(\delta), we want to have |P(ξ;x)μx|1\lvert P(\xi;x)-\mu_{x}\rvert\lesssim 1 for every ξΔ\xi\in\Delta so that Δ𝒫x(δ)Δ\bigcup_{\Delta\in\mathcal{P}_{x}(\delta)}\Delta is in a slightly thickened stationary set. This is guaranteed by the following Lemma whose proof uses the Lagrange interpolation.

Lemma 4.9.

Let 𝒫x(δ):={Δ𝒫(δ)\nonscript|\nonscriptΔZ~x}\mathcal{P}_{x}(\delta):=\{\Delta\in\mathcal{P}(\delta)\nonscript\>|\allowbreak\nonscript\>\mathopen{}\Delta\cap\tilde{Z}_{x}\neq\emptyset\}. Then, for each Δ𝒫x(δ)\Delta\in\mathcal{P}_{x}(\delta) and ξΔ\xi\in\Delta, we have

(4.5) |P(ξ;x)μx|k,K1.\lvert P(\xi;x)-\mu_{x}\rvert\lesssim_{k,K}1.
Proof of Lemma 4.9.

In the proof of this lemma we will see the motivation of introducing (4.2). We take one Δ𝒫x(δ)\Delta\in\mathcal{P}_{x}(\delta). By definition, we can find ξ0Δ\xi_{0}\in\Delta such that ξ0Z~x\xi_{0}\in\tilde{Z}_{x}. By the definition of Z~x\tilde{Z}_{x} as in (4.2), we know that

(4.6) ξ0+ckδaZx for every a{0,1,,k}2.\xi_{0}+c_{k}\delta a\in Z_{x}\text{ for every }a\in\{0,1,\dots,k\}^{2}.

As a consequence, we obtain that

(4.7) μxP(ξ0+ckδa;x)μx+1.\mu_{x}\leq P(\xi_{0}+c_{k}\delta a;x)\leq\mu_{x}+1.

The desired bound (4.5) follows from applying the interpolation polynomials in the Lagrange form. ∎

In particular,

(4.8) tkπ1Δ for some Δ𝒫x(δ),t_{k^{\prime}}\in\pi_{1}\Delta\text{ for some }\Delta\in\mathcal{P}_{x}(\delta),

for every xL~δ,sprdx\in\widetilde{L}_{\delta,\mathrm{sprd}} and every 0kk0\leq k^{\prime}\leq k.

4.3. Rigidity of stationary sets

For ΞN\Xi\subset\mathbb{R}^{N}, let Con(Ξ)\mathrm{Con}(\Xi) be the closure of the convex hull of Ξ\Xi. By John’s ellipsoid lemma, we know that there exists a rectangular box Ξ\Box_{\Xi} such that

(4.9) ΞCon(Ξ)CNΞ,\Box_{\Xi}\subset\mathrm{Con}(\Xi)\subset C_{N}\Box_{\Xi},

where CNC_{N} is a large constant that depends only on NN. Let c(Ξ)c(\Xi) denote the center of Ξ\Box_{\Xi}. Let Dual(Ξ)\mathrm{Dual}(\Xi) denote

(4.10) {xN:|ξ¯c(Ξ),x|2Ck,K for every ξ¯Ξ},\{x\in\mathbb{R}^{N}:|\langle\bar{\xi}-c(\Xi),x\rangle|\leq 2C_{k,K}\text{ for every }\bar{\xi}\in\Box_{\Xi}\},

where Ck,KC_{k,K} is the same as the one in Lemma 4.9. Notice that |Ξ||Dual(Ξ)|1|\Box_{\Xi}||\mathrm{Dual}(\Xi)|\sim 1.

Recall from (4.5) that, for every ξΔ𝒫x(δ)\xi\in\Delta\in\mathcal{P}_{x}(\delta), we have

(4.11) μxCk,KP(ξ;x)=xϕk(ξ)μx+Ck,K.\mu_{x}-C_{k,K}\leq P(\xi;x)=x\cdot\phi_{k}(\xi)\leq\mu_{x}+C_{k,K}.

Denote

(4.12) Ξx:={ϕk(ξ):ξΔ𝒫x(δ)}.\Xi_{x}:=\{\phi_{k}(\xi):\xi\in\Delta\in\mathcal{P}_{x}(\delta)\}.

We obtain that

(4.13) μxCk,Kxξ¯μx+Ck,K,\mu_{x}-C_{k,K}\leq x\cdot\bar{\xi}\leq\mu_{x}+C_{k,K},

for every ξ¯Con(Ξx)\bar{\xi}\in\mathrm{Con}(\Xi_{x}), and therefore

(4.14) |x(ξ¯c(Ξx))|2Ck,K,|x\cdot(\bar{\xi}-c(\Xi_{x}))|\leq 2C_{k,K},

for every ξ¯Con(Ξx)\bar{\xi}\in\mathrm{Con}(\Xi_{x}), which further means xDual(Ξx)x\in\mathrm{Dual}(\Xi_{x}).

4.4. Estimating dual boxes

In this section, we will bound L~δ,sprd\widetilde{L}_{\delta,\mathrm{sprd}}. Recall the choice of t0,t1,,tkt_{0},t_{1},\dots,t_{k} from previous subsections. Let 𝒫k(δ)\mathcal{P}_{k^{\prime}}(\delta) denote

(4.15) {Δ𝒫(δ):(tk,s)Δ for some s[0,1]}.\{\Delta\in\mathcal{P}(\delta):(t_{k^{\prime}},s)\in\Delta\text{ for some }s\in[0,1]\}.

For a fixed tuple

(4.16) 𝚫=(Δ0,,Δk)𝒫0(δ)××𝒫k(δ),{\bf\Delta}=(\Delta_{0},\dots,\Delta_{k})\in\mathcal{P}_{0}(\delta)\times\dots\times\mathcal{P}_{k}(\delta),

denote

(4.17) L~δ,sprd(𝚫):={xL~δ,sprd:Δk𝒫x(δ) for every k}.\widetilde{L}_{\delta,\mathrm{sprd}}({\bf\Delta}):=\{x\in\widetilde{L}_{\delta,\mathrm{sprd}}:\Delta_{k^{\prime}}\in\mathcal{P}_{x}(\delta)\text{ for every }k^{\prime}\}.

Therefore we can write

(4.18) L~δ,sprd=𝚫𝒫0(δ)××𝒫k(δ)L~δ,sprd(𝚫).\widetilde{L}_{\delta,\mathrm{sprd}}=\bigcup_{{\bf\Delta}\in\mathcal{P}_{0}(\delta)\times\dots\times\mathcal{P}_{k}(\delta)}\widetilde{L}_{\delta,\mathrm{sprd}}({\bf\Delta}).

Let us focus on estimating L~δ,sprd(𝚫)\widetilde{L}_{\delta,\mathrm{sprd}}({\bf\Delta}). Recall the discussion in Subsection 4.3. Let us use ϕk(𝚫)\phi_{k}({\bf\Delta}) to denote {ϕk(ξ):ξΔk for some k}\{\phi_{k}(\xi):\xi\in\Delta_{k^{\prime}}\text{ for some }k^{\prime}\}. We have

(4.19) |L~δ,sprd(𝚫)||Dual(ϕk(𝚫))||Con(ϕk(𝚫))|1|\widetilde{L}_{\delta,\mathrm{sprd}}({\bf\Delta})|\leq|\mathrm{Dual}(\phi_{k}({\bf\Delta}))|\sim\lvert\mathrm{Con}(\phi_{k}({\bf\Delta}))\rvert^{-1}

We will get a good lower bound on |Con(ϕk(𝚫))|\lvert\mathrm{Con}(\phi_{k}({\bf\Delta}))\rvert by choosing a transverse set of line segments inside this convex set. A standard geometric observation is that each set Con(ϕk(Δ))\mathrm{Con}(\phi_{k}(\Delta)) contains line segments of length δl\sim\delta^{-l} in the direction of ll-th derivatives of ϕk\phi_{k}:

Lemma 4.10.

For every Δ𝒫(δ)\Delta\in\mathcal{P}(\delta), every ξΔ\xi\in\Delta, and every multiindex β\beta with 1|β|k1\leq\lvert\beta\rvert\leq k, the convex hull Con(ϕk(Δ))\mathrm{Con}(\phi_{k}(\Delta)) contains a line segment of length δ|β|\sim\delta^{\lvert\beta\rvert} in the direction βϕk(ξ)\partial^{\beta}\phi_{k}(\xi).

From now on, we order the monomials in ϕ\phi in the increasing lexicographic order and write

(4.20) ϕk(ξ)=(t,t2,,tk,s,st,,stk1,s2,),ξ=(s,t).\phi_{k}(\xi)=(t,t^{2},\dots,t^{k},s,st,\dots,st^{k-1},s^{2},\dots),\quad\xi=(s,t).

We also order the tjt_{j}’s in a convenient way. By the Vandermonde determinant formula, we know that

det(1t0,t02,t0l1t1,t12,t1l1tl,tl2,tll)1.\det\begin{pmatrix}1&t_{0},&t_{0}^{2},&\dots&t_{0}^{l}\\ 1&t_{1},&t_{1}^{2},&\dots&t_{1}^{l}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&t_{l},&t_{l}^{2},&\dots&t_{l}^{l}\end{pmatrix}\sim 1.

Let vll+1v_{l}\in\mathbb{R}^{l+1} be the vector whose Hodge dual is

vl=(111)(t0t1tl)(t0l1t1l1tll1).\star v_{l}=\begin{pmatrix}1\\ 1\\ \vdots\\ 1\end{pmatrix}\wedge\begin{pmatrix}t_{0}\\ t_{1}\\ \vdots\\ t_{l}\end{pmatrix}\wedge\dotsb\wedge\begin{pmatrix}t_{0}^{l-1}\\ t_{1}^{l-1}\\ \vdots\\ t_{l}^{l-1}\end{pmatrix}.

It follows that vl1\lVert v_{l}\rVert\sim 1. By rearranging t0,,tlt_{0},\dotsc,t_{l} if necessary, we may assume that the last entry of vlv_{l} is 1\sim 1. Doing this in the reverse order of l=k,,1l=k,\dotsc,1, we may assume that this holds for every ll.

With this order of tjt_{j}’s, we will use the following lower bound:

|Con(ϕk(𝚫))|\displaystyle\lvert\mathrm{Con}(\phi_{k}({\bf\Delta}))\rvert
|j=1k(ϕ(ξj)ϕ(ξ0))j=0kδsϕ(ξj)k=2k1j=1k+1kδk(skϕ(ξj)skϕ(ξ0))|\displaystyle\geq\Big{\lvert}\bigwedge_{j=1}^{k}(\phi(\xi_{j})-\phi(\xi_{0}))\wedge\bigwedge_{j=0}^{k}\delta\partial_{s}\phi(\xi_{j})\wedge\bigwedge_{k^{\prime}=2}^{k-1}\bigwedge_{j=1}^{k+1-k^{\prime}}\delta^{k^{\prime}}(\partial_{s}^{k^{\prime}}\phi(\xi_{j})-\partial_{s}^{k^{\prime}}\phi(\xi_{0}))\Big{\rvert}
=δk(k+1)(k+2)/6k+1|j=1k(ϕ(ξj)ϕ(ξ0))j=0ksϕ(ξj)k=2k1j=1k+1k(skϕ(ξj)skϕ(ξ0))|.\displaystyle=\delta^{k(k+1)(k+2)/6-k+1}\Big{\lvert}\bigwedge_{j=1}^{k}(\phi(\xi_{j})-\phi(\xi_{0}))\wedge\bigwedge_{j=0}^{k}\partial_{s}\phi(\xi_{j})\wedge\bigwedge_{k^{\prime}=2}^{k-1}\bigwedge_{j=1}^{k+1-k^{\prime}}(\partial_{s}^{k^{\prime}}\phi(\xi_{j})-\partial_{s}^{k^{\prime}}\phi(\xi_{0}))\Big{\rvert}.

Here, we have chosen a total of

k+(k+1)+(k1)++2=k+k(k+1)/2=Nk+(k+1)+(k-1)+\dotsb+2=k+k(k+1)/2=N

vectors in the difference set of the convex set Con(ϕk(𝚫))\mathrm{Con}(\phi_{k}({\bf\Delta})), of which the first kk come from differences between Δ0\Delta_{0} and Δ1,,Δk\Delta_{1},\dotsc,\Delta_{k}, while the remaining ones come from individual Δj\Delta_{j}’s via Lemma 4.10.

Writing these vectors as rows of a matrix, we see that, up to a (k,l)(k,l)-dependent constant, the latter wedge product is the determinant of the block upper triangular matrix

(Ak0A~k100A¯k200A¯1)\begin{pmatrix}A_{k}&*&\dots&\dots&*\\ 0&\tilde{A}_{k-1}&*&&\vdots\\ 0&0&\bar{A}_{k-2}&\ddots&\vdots\\ \vdots&&\ddots&\ddots&*\\ 0&\dots&\dots&0&\bar{A}_{1}\end{pmatrix}

with

Ak=[t1t0,t12t02,t1kt0kt2t0,t22t02,t2kt0ktkt0,tk2t02,tkkt0k]A_{k}=\begin{bmatrix}t_{1}-t_{0},&t_{1}^{2}-t_{0}^{2},&\dots&t_{1}^{k}-t_{0}^{k}\\ t_{2}-t_{0},&t_{2}^{2}-t_{0}^{2},&\dots&t_{2}^{k}-t_{0}^{k}\\ \vdots&\vdots&\ddots&\vdots\\ t_{k}-t_{0},&t_{k}^{2}-t_{0}^{2},&\dots&t_{k}^{k}-t_{0}^{k}\end{bmatrix}
A~l:=[1t0,t02,t0ls01t1,t12,t1ls11tl+1,tl+12,tl+1lsl+1]\tilde{A}_{l}:=\begin{bmatrix}1&t_{0},&t_{0}^{2},&\dots&t_{0}^{l}&s_{0}\\ 1&t_{1},&t_{1}^{2},&\dots&t_{1}^{l}&s_{1}\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 1&t_{l+1},&t_{l+1}^{2},&\dots&t_{l+1}^{l}&s_{l+1}\end{bmatrix}
A¯l:=[t1t0,t1lt0l(s1s0)tl+1t0,tl+1lt0l(sl+1s0)]\bar{A}_{l}:=\begin{bmatrix}t_{1}-t_{0},&\dots&t_{1}^{l}-t_{0}^{l}&(s_{1}-s_{0})\\ \vdots&\ddots&\vdots&\vdots\\ t_{l+1}-t_{0},&\dots&t_{l+1}^{l}-t_{0}^{l}&(s_{l+1}-s_{0})\end{bmatrix}

Since AkA_{k} is a Vandermonde matrix, its determinant is 1\sim 1. Consider next

(4.21) detA¯l=detA~l=vl+1(s0,,sl+1).\det\bar{A}_{l}=\det\tilde{A}_{l}=v_{l+1}\cdot(s_{0},\dotsc,s_{l+1}).

We fix some s0,s1s_{0},s_{1} with

(4.22) (ti,si)Δi(t_{i},s_{i})\in\Delta_{i}

and select sl+1s_{l+1} for l=1,,k1l=1,\dotsc,k-1 recursively in such a way that (4.22) holds and the absolute value of (4.21) is maximized. By our arrangement of tjt_{j}’s, the last entry of vl+1v_{l+1} is 1\sim 1. Therefore, given s0,,sls_{0},\dotsc,s_{l}, the set of sl+1s_{l+1}’s for which |detA¯l|δl\lvert\det\bar{A}_{l}\rvert\sim\delta_{l} is the union of at most two intervals of length δl\sim\delta_{l}. It follows that, given Δ0,,Δl\Delta_{0},\dotsc,\Delta_{l} and δl[δ,1]\delta_{l}\in[\delta,1], there are δl/δ\sim\delta_{l}/\delta many Δl+1\Delta_{l+1} for which |detA¯l|δl\lvert\det\bar{A}_{l}\rvert\sim\delta_{l}, and there are no other possibilities.

Therefore,

𝚫𝒫0(δ)××𝒫k(δ)|Con(ϕk(𝚫))|1\displaystyle\sum_{{\bf\Delta}\in\mathcal{P}_{0}(\delta)\times\dots\times\mathcal{P}_{k}(\delta)}\lvert\mathrm{Con}(\phi_{k}({\bf\Delta}))\rvert^{-1}
δ1,,δk1[δ,1]dyadicΔ0,Δ1Δ2|detA¯2|δ1Δk|detA¯k|δk1|Con(ϕk(𝚫))|1\displaystyle\leq\sum_{\begin{subarray}{c}\delta_{1},\dots,\delta_{k-1}\in[\delta,1]\\ \text{dyadic}\end{subarray}}\sum_{\Delta_{0},\Delta_{1}}\sum_{\begin{subarray}{c}\Delta_{2}\\ \lvert\det\bar{A}_{2}\rvert\sim\delta_{1}\end{subarray}}\dots\sum_{\begin{subarray}{c}\Delta_{k}\\ \lvert\det\bar{A}_{k}\rvert\sim\delta_{k-1}\end{subarray}}\lvert\mathrm{Con}(\phi_{k}({\bf\Delta}))\rvert^{-1}
(δk(k+1)(k+2)/6k+1)1δ1,,δk1[δ,1]dyadicΔ0,Δ1Δ2|detA¯1|δ1Δk|detA¯k1|δk1(detAkj=1k1detA¯j)1\displaystyle\lesssim(\delta^{k(k+1)(k+2)/6-k+1})^{-1}\sum_{\begin{subarray}{c}\delta_{1},\dots,\delta_{k-1}\in[\delta,1]\\ \text{dyadic}\end{subarray}}\sum_{\Delta_{0},\Delta_{1}}\sum_{\begin{subarray}{c}\Delta_{2}\\ \lvert\det\bar{A}_{1}\rvert\sim\delta_{1}\end{subarray}}\dots\sum_{\begin{subarray}{c}\Delta_{k}\\ \lvert\det\bar{A}_{k-1}\rvert\sim\delta_{k-1}\end{subarray}}\bigl{(}\det A_{k}\prod_{j=1}^{k-1}\det\bar{A}_{j}\bigr{)}^{-1}
(δk(k+1)(k+2)/6k+1)1δ1,,δk1[δ,1]dyadicΔ0,Δ1Δ2|detA¯1|δ1Δk|detA¯k1|δk1(j=1k1δj)1\displaystyle\lesssim(\delta^{k(k+1)(k+2)/6-k+1})^{-1}\sum_{\begin{subarray}{c}\delta_{1},\dots,\delta_{k-1}\in[\delta,1]\\ \text{dyadic}\end{subarray}}\sum_{\Delta_{0},\Delta_{1}}\sum_{\begin{subarray}{c}\Delta_{2}\\ \lvert\det\bar{A}_{1}\rvert\sim\delta_{1}\end{subarray}}\dots\sum_{\begin{subarray}{c}\Delta_{k}\\ \lvert\det\bar{A}_{k-1}\rvert\sim\delta_{k-1}\end{subarray}}\bigl{(}\prod_{j=1}^{k-1}\delta_{j}\bigr{)}^{-1}
(δk(k+1)(k+2)/6k+1)1δ1,,δk1[δ,1]dyadicδk1\displaystyle\lesssim(\delta^{k(k+1)(k+2)/6-k+1})^{-1}\sum_{\begin{subarray}{c}\delta_{1},\dots,\delta_{k-1}\in[\delta,1]\\ \text{dyadic}\end{subarray}}\delta^{-k-1}
|log+δ|k1δk(k+1)(k+2)/62.\displaystyle\lesssim\lvert\log_{+}\delta\rvert^{k-1}\delta^{-k(k+1)(k+2)/6-2}.

This finishes the estimate for (4.18) and the proof of Theorem 1.2.

Remark 4.11.

If we follow the proof of Theorem 1.2 in higher dimensions d3d\geq 3, the problem of estimating the spread out set becomes much more difficult. In dimension d=2d=2, we greatly benefited from a factorization of the upper bound (4.19) into linear factors given by (4.21). Unless a similar upper bound with good factorization can be found in higher dimensions, we would face complicated quantitative real algebraic problems. We feel it may be difficult to find such an upper bound at this moment, and hence do not pursue the problem for Sd,kS_{d,k}, d3d\geq 3, in the current paper.

5. Lower bounds

In this section, we prove lower bounds for p2,kp_{2,k}. The idea is not difficult to explain. We will show that the function Ek1E_{k}1 is “large” (see Lemma 5.2) on a disjoint union of rectangular boxes (see Lemma 5.1). This idea has already been used by Arkhipov, Chubarikov and Karatsuba [AKC79, ACK04] and by Ikromov [Ikr97]. The lower bound in Lemma 5.2 is essentially the same as in the above mentioned papers; the key difference is that we are able to find more rectangular boxes where such a lower bounds holds. Roughly speaking, this is achieved via applying the “rotation symmetry” of Parsell-Vinogradov surfaces.

Let λ>0\lambda>0 be a large number. Let θr=r/(100λ)\theta_{r}=r/(100\lambda), r=0,1,,λr=0,1,\dots,\lambda. Let wr=1/4+r/(2λ)w_{r}=1/4+r/(2\lambda), r=0,1,,λr=0,1,\dots,\lambda. The choice of θr\theta_{r} and wrw_{r} is such that

(5.1) |θr|1100,14wr34,|\theta_{r}|\leq\frac{1}{100},\ \ \frac{1}{4}\leq w_{r}\leq\frac{3}{4},

and what we will need is that θr\theta_{r} is close to 0, and wrw_{r} is away from both 0 and 1.

Recall that xNx\in\mathbb{R}^{N}. Let us write

(5.2) P(ξ;x)=x1ξ1k+.P(\xi;x)=x_{1}\xi_{1}^{k}+\cdots.

For given θr\theta_{r} and wrw_{r^{\prime}}, we let 𝐫=(r,r)\mathbf{r}=(r,r^{\prime}) and write

(5.3) P(ξ;x)=0kkγ𝐫,k(ξ2;x)(ξ1+θrξ2wr)k,P(\xi;x)=\sum_{0\leq k^{\prime}\leq k}\gamma_{\mathbf{r},k^{\prime}}(\xi_{2};x)(\xi_{1}+\theta_{r}\xi_{2}-w_{r^{\prime}})^{k^{\prime}},

where for each 𝐫\mathbf{r}, kk^{\prime} and xNx\in\mathbb{R}^{N}, the function γ𝐫,k(ξ2;x)\gamma_{\mathbf{r},k^{\prime}}(\xi_{2};x) is a polynomial of degree kkk-k^{\prime} in ξ2\xi_{2}. In particular, γ𝐫,k(ξ2;x)\gamma_{\mathbf{r},k}(\xi_{2};x) is a constant function that is independent of 𝐫\mathbf{r} and ξ2\xi_{2}; indeed, γ𝐫,k(ξ2;x)=x1\gamma_{\mathbf{r},k}(\xi_{2};x)=x_{1}, which follows from the normalization in (5.2). Define

(5.4) Ω𝐫:={xN:λkx1(2λ)k,γ𝐫,k(;x)ϵλk,k=1,2,,k1,γ𝐫,0(;x)γ𝐫,0(0;x)ϵ}.\Omega_{\mathbf{r}}:=\{x\in\mathbb{R}^{N}:\lambda^{k}\leq x_{1}\leq(2\lambda)^{k},\|\gamma_{\mathbf{r},k^{\prime}}(\cdot;x)\|\leq\epsilon\lambda^{k^{\prime}},k^{\prime}=1,2,\dots,k-1,\\ \|\gamma_{\mathbf{r},0}(\cdot;x)-\gamma_{\mathbf{r},0}(0;x)\|\leq\epsilon\}.

Here ϵ>0\epsilon>0 is a sufficiently small parameter that will be picked later, and for a polynomial γ:[0,1]\gamma:[0,1]\to\mathbb{R}, we use γ\|\gamma\| to denote the 1\ell^{1} sum of all its coefficients.

Lemma 5.1.

If ϵ\epsilon (depending only on kk) is chosen to be sufficiently small, then for each 𝐫\mathbf{r}, it holds that

(5.5) |Ω𝐫|kλk(k+1)(k+2)/6,|\Omega_{\mathbf{r}}|\gtrsim_{k}\lambda^{k(k+1)(k+2)/6},

and for 𝐫1𝐫2\mathbf{r}_{1}\neq\mathbf{r}_{2}, we have Ω𝐫1Ω𝐫2=\Omega_{\mathbf{r}_{1}}\cap\Omega_{\mathbf{r}_{2}}=\emptyset.

Lemma 5.2.

For each 𝐫\mathbf{r} and each xΩ𝐫x\in\Omega_{\mathbf{r}}, it holds that

(5.6) |[0,1]2e(P(ξ;x))𝑑ξ|λ1,\Big{|}\int_{[0,1]^{2}}e(P(\xi;x))d\xi\Big{|}\gtrsim\lambda^{-1},

provided that ϵ\epsilon is chosen to be sufficiently small, depending only on kk.

The desired lower bound follows immediately from these two lemmas.

Remark 5.3.

Lemma 5.1 and Lemma 5.2 also immediately lead to the sharpness of Corollary 1.4. Indeed, they imply that the bound (1.21) also fails whenever ppd,kp\leq p_{d,k}; in particular, the endpoint case p=pd,kp=p_{d,k} is also included.

In the end, we will prove Lemma 5.1 and Lemma 5.2. We will start with the latter one. Its proof relies on the following lemma in Ikromov [Ikr97], a slightly different form of which also already appeared in Arkhipov, Chubarikov and Karatsuba [AKC79, ACK04].

Lemma 5.4 ([Ikr97]).

Let a<102a<-10^{-2} and b>102b>10^{-2}. Suppose that the polynomial q(x)=αkxk++α1xq(x)=\alpha_{k}x^{k}+\dots+\alpha_{1}x satisfies

(5.7) Akαk(2A)k,|αk1|ϵAk1,,|α1|ϵA,A^{k}\leq\alpha_{k}\leq(2A)^{k},\ |\alpha_{k-1}|\leq\epsilon A^{k-1},\dots,|\alpha_{1}|\leq\epsilon A,

for some large AA and small ϵ\epsilon. Then we have the following asymptotic representation

(5.8) abe2πiq(x)𝑑x=c(α)αk1/k+O(A1k) as A,\int_{a}^{b}e^{2\pi iq(x)}dx=\frac{c(\alpha)}{\alpha_{k}^{1/k}}+O(A^{1-k})\text{ as }A\to\infty,

where c(α)c(\alpha) is a constant depending on αk,,α1\alpha_{k},\dotsc,\alpha_{1} satisfying

(5.9) c(α)=c+o(ϵ) as ϵ0,c(\alpha)=c+o(\epsilon)\text{ as }\epsilon\to 0,

with c0c\neq 0 depending only on kk.

Proof of Lemma 5.2.

Let us write our integral as

(5.10) [0,1]2e(0kkγ𝐫,k(ξ2;x)(ξ1+θrξ2wr)k)𝑑ξ.\int_{[0,1]^{2}}e\Big{(}\sum_{0\leq k^{\prime}\leq k}\gamma_{\mathbf{r},k^{\prime}}(\xi_{2};x)(\xi_{1}+\theta_{r}\xi_{2}-w_{r^{\prime}})^{k^{\prime}}\Big{)}d\xi.

After the change of variable

(5.11) ξ1+θrξ2wrξ~1\xi_{1}+\theta_{r}\xi_{2}-w_{r^{\prime}}\mapsto\tilde{\xi}_{1}

for each fixed ξ2\xi_{2}, the integral becomes

(5.12) e(γ𝐫,0(0;x))01e(γ𝐫,0(ξ2;x)γ𝐫,0(0;x))θrξ2wr1+θrξ2wre(0<kkγ𝐫,k(ξ2;x)ξ~1k)𝑑ξ~1𝑑ξ2.e(\gamma_{\mathbf{r},0}(0;x))\int_{0}^{1}e(\gamma_{\mathbf{r},0}(\xi_{2};x)-\gamma_{\mathbf{r},0}(0;x))\int_{\theta_{r}\xi_{2}-w_{r^{\prime}}}^{1+\theta_{r}\xi_{2}-w_{r^{\prime}}}e\Big{(}\sum_{0<k^{\prime}\leq k}\gamma_{\mathbf{r},k^{\prime}}(\xi_{2};x)\tilde{\xi}_{1}^{k^{\prime}}\Big{)}d\tilde{\xi}_{1}d\xi_{2}.

In the case k3k\geq 3, since γ𝐫,k(ξ2;x)=x1\gamma_{\mathbf{r},k}(\xi_{2};x)=x_{1}, Lemma 5.4 gives a uniform lower bound for the inner integral, provided that ϵ\epsilon is chosen to be sufficiently small. In the case k=2k=2, we complete squares in the phase and use the fact that the Fresnel integral 0ucos(ξ2)𝑑ξ\int_{0}^{u}\cos(\xi^{2})d\xi is bounded below by a positive constant as soon as u>0u>0 is bounded away from 0, while the Fresnel integral 0usin(ξ2)𝑑ξ\int_{0}^{u}\sin(\xi^{2})d\xi is bounded above.

In both cases, the value of the inner integral is contained in a cone in \mathbb{C} with angle <π<\pi and bounded away from 0. Using the upper bound |γ𝐫,0(ξ2;x)γ𝐫,0(0;x)|ϵ\lvert\gamma_{\mathbf{r},0}(\xi_{2};x)-\gamma_{\mathbf{r},0}(0;x)\rvert\lesssim\epsilon, we can complete the proof of (5.6). ∎

Proof of Lemma 5.1.

Regarding the (elementary) lower bound (5.5), we first mention that this has also been observed by Ikromov in the case θr=0\theta_{r}=0, see [Ikr97, page 183]. To show (5.5), note that the coefficient of ξ2l\xi_{2}^{l} in γ𝐫,k(ξ2,x)\gamma_{\mathbf{r},k^{\prime}}(\xi_{2},x) equals xk,lx_{k^{\prime},l} plus some function of θ,w\theta,w and the components xk′′,lx_{k^{\prime\prime},l} with k<k′′kk^{\prime}<k^{\prime\prime}\leq k.

Hence, for each k=k,,0k^{\prime}=k,\dotsc,0, once xk′′,lx_{k^{\prime\prime},l} have been chosen for all k′′>kk^{\prime\prime}>k^{\prime} and all ll, we can choose each xk,lx_{k^{\prime},l} with l{0,,kk}l\in\{0,\dotsc,k-k^{\prime}\} in an interval of length λk\sim\lambda^{k^{\prime}}. The measure of the set of all xx that we can choose is then proportional to λ\lambda to the power

k=0kk(kk+1)=16k(k+1)(k+2).\sum_{k^{\prime}=0}^{k}k^{\prime}(k-k^{\prime}+1)=\frac{1}{6}k(k+1)(k+2).

In the end, we show that Ω𝐫1Ω𝐫2=\Omega_{\mathbf{r}_{1}}\cap\Omega_{\mathbf{r}_{2}}=\emptyset whenever 𝐫1𝐫2\mathbf{r}_{1}\neq\mathbf{r}_{2}. We argue by contradiction. Let 𝐫1𝐫2\mathbf{r}_{1}\neq\mathbf{r}_{2} and assume that there exists an xΩ𝐫1Ω𝐫2x\in\Omega_{\mathbf{r}_{1}}\cap\Omega_{\mathbf{r}_{2}}. We now expand P(ξ;x)P(\xi;x) in the form of (5.3) with (θr1,wr1)(\theta_{r_{1}},w_{r^{\prime}_{1}}) and (θr2,wr2)(\theta_{r_{2}},w_{r^{\prime}_{2}}) separately. By only considering the first term in these two expansions, we obtain

(5.13) x1(ξ1+θr1ξ2wr1)k+x1(ξ1+θr2ξ2wr2)k+x_{1}(\xi_{1}+\theta_{r_{1}}\xi_{2}-w_{r^{\prime}_{1}})^{k}+\dots\equiv x_{1}(\xi_{1}+\theta_{r_{2}}\xi_{2}-w_{r^{\prime}_{2}})^{k}+\dots

as functions depending on ξ1\xi_{1} and ξ2\xi_{2}. Recall the definition (5.4). We will arrive at a contradiction if we can show that the following polynomial in ξ1\xi_{1} and ξ2\xi_{2}

(5.14) x1(ξ1+θr1ξ2wr1)kx1(ξ1+θr2ξ2wr2)kx_{1}(\xi_{1}+\theta_{r_{1}}\xi_{2}-w_{r^{\prime}_{1}})^{k}-x_{1}(\xi_{1}+\theta_{r_{2}}\xi_{2}-w_{r^{\prime}_{2}})^{k}

has a coefficient of a non-constant term with absolute value λk1\gtrsim\lambda^{k-1}.

The monomial ξ1k1ξ2\xi_{1}^{k-1}\xi_{2} has the coefficient kx1(θr1θr2)kx_{1}(\theta_{r_{1}}-\theta_{r_{2}}), and the monomial ξ1k1\xi_{1}^{k-1} has the coefficient kx1(wr1wr2)kx_{1}(w_{r_{1}^{\prime}}-w_{r_{2}^{\prime}}). At least one of these coefficients has absolute value |x1|/λλk1\gtrsim|x_{1}|/\lambda\sim\lambda^{k-1}. ∎

6. Proof of Corollary 1.4

Fix d=2d=2, k2k\geq 2 and ff with f=1\|f\|_{\infty}=1. We abbreviate p¯2,k\bar{p}_{2,k} to p¯k\bar{p}_{k}. Let μ\mu be the measure supported on the surface S2,kS_{2,k} whose projection to 2\mathbb{R}^{2} is given by f(ξ)dξf(\xi)d\xi, and let μ0\mu_{0} be that given by 𝟏[0,1]2(ξ)dξ\mathbf{1}_{[0,1]^{2}}(\xi)d\xi. We can therefore write

(6.1) E[0,1]2(2,k)f=μ^ and E[0,1]2(2,k)1=μ0^.E^{(2,k)}_{[0,1]^{2}}f=\widehat{\mu}\text{ and }E^{(2,k)}_{[0,1]^{2}}1=\widehat{\mu_{0}}.

Let χ:N\chi:\mathbb{R}^{N}\to\mathbb{R} be a non-negative smooth bump function supported on [1,1]N[-1,1]^{N} satisfying that χ^\widehat{\chi} is non-negative and χ^(x)N1\widehat{\chi}(x)\gtrsim_{N}1 for every |x|1|x|\leq 1. Define χR(ξ):=RNχ(Rξ)\chi_{R}(\xi):=R^{N}\chi(R\xi). Recall that p¯k\bar{p}_{k} is the smallest even number p2,k\geq p_{2,k}. As a consequence of Theorem 1.2 and Hölder’s inequality, we obtain that for every ϵ>0\epsilon>0 and R1R\geq 1, it holds that

(6.2) μ0^Lp¯k(BR)ϵRϵ,\|\widehat{\mu_{0}}\|_{L^{\bar{p}_{k}}(B_{R})}\lesssim_{\epsilon}R^{\epsilon},

where BRNB_{R}\subset\mathbb{R}^{N} is an arbitrary ball of radius RR. We will show that

(6.3) μ^Lp¯k(BR)ϵRϵ.\|\widehat{\mu}\|_{L^{\bar{p}_{k}}(B_{R})}\lesssim_{\epsilon}R^{\epsilon}.

To prove this estimate, we first observe that, by modulating the function ff, which does not change its LL^{\infty} norm, it suffices to consider the case that BRB_{R} is centered at the origin. In this case, we have

(6.4) μ^Lp¯k(BR)p¯k/2μ^χR^Lp¯k(N)p¯k/2=(μ^χR^)p¯k/22.\|\widehat{\mu}\|_{L^{\bar{p}_{k}}(B_{R})}^{\bar{p}_{k}/2}\lesssim\|\widehat{\mu}\cdot\widehat{\chi_{R}}\|_{L^{\bar{p}_{k}}(\mathbb{R}^{N})}^{\bar{p}_{k}/2}=\big{\|}(\widehat{\mu}\cdot\widehat{\chi_{R}})^{\bar{p}_{k}/2}\big{\|}_{2}.

We apply Plancherel’s theorem to the last term and obtain

(6.5) =(μχR)(μχR)2(μ0χR)(μ0χR)2.=\big{\|}(\mu*\chi_{R})*\dots*(\mu*\chi_{R})\big{\|}_{2}\leq\big{\|}(\mu_{0}*\chi_{R})*\dots*(\mu_{0}*\chi_{R})\big{\|}_{2}.

We apply Plancherel’s theorem back and obtain (6.3). In the end, to pass from the local estimate (6.3) to the desired global estimate in the corollary, one can follow Tao’s epsilon-removal lemma in [Tao99] and its variants in Bourgain and Guth [BG11] and Kim [Kim17].

References

  • [ACK04] G. I. Arkhipov, V. N. Chubarikov, and A. A. Karatsuba. Trigonometric sums in number theory and analysis, volume 39 of De Gruyter Expositions in Mathematics. Walter de Gruyter GmbH & Co. KG, Berlin, 2004. Translated from the 1987 Russian original.
  • [AKC79] G. I. Arhipov, A. A. Karacuba, and V. N. Chubarikov. Trigonometric integrals. Izv. Akad. Nauk SSSR Ser. Mat., 43(5):971–1003, 1197, 1979.
  • [BBFL18] Jonathan Bennett, Neal Bez, Taryn C. Flock, and Sanghyuk Lee. Stability of the Brascamp-Lieb constant and applications. Amer. J. Math., 140(2):543–569, 2018.
  • [BCT06] Jonathan Bennett, Anthony Carbery, and Terence Tao. On the multilinear restriction and kakeya conjectures. Acta Math., 196(2):261–302, 2006.
  • [BG11] Jean Bourgain and Larry Guth. Bounds on oscillatory integral operators based on multilinear estimates. Geom. Funct. Anal., 21(6):1239–1295, 2011.
  • [BNW88] Joaquim Bruna, Alexander Nagel, and Stephen Wainger. Convex hypersurfaces and Fourier transforms. Ann. of Math. (2), 127(2):333–365, 1988.
  • [BPR06] Saugata Basu, Richard Pollack, and Marie-Françoise Roy. Algorithms in real algebraic geometry, volume 10 of Algorithms and Computation in Mathematics. Springer-Verlag, Berlin, second edition, 2006.
  • [CCW99] Anthony Carbery, Michael Christ, and James Wright. Multidimensional van der Corput and sublevel set estimates. J. Amer. Math. Soc., 12(4):981–1015, 1999.
  • [Cha03] M. A. Chakhkiev. On the exponent of convergence of a special integral of a multidimensional analogue of Tarry’s problem. Izv. Ross. Akad. Nauk Ser. Mat., 67(2):211–224, 2003.
  • [CM11] Raf Cluckers and Daniel J. Miller. Stability under integration of sums of products of real globally subanalytic functions and their logarithms. Duke Math. J., 156(2):311–348, 2011.
  • [Dru85] Stephen W. Drury. Restrictions of Fourier transforms to curves. Ann. Inst. Fourier (Grenoble), 35(1):117–123, 1985.
  • [Dzh19] I. Sh. Dzhabbarov. Convergence exponent of a special integral in the two-dimensional Tarry problem with a homogeneous polynomial of degree 2. Mat. Zametki, 105(3):375–382, 2019.
  • [Dzh20] I. Sh. Dzhabbarov. On the Multidimensional Tarry Problem for a Cubic Polynomial. Mat. Zametki, 107(5):657–673, 2020.
  • [Gab68] A. M. Gabrièlov. Projections of semianalytic sets. Funkcional. Anal. i Priložen., 2(4):18–30, 1968.
  • [GOZZK20] Shaoming Guo, Changkeun Oh, Ruixiang Zhang, and Pavel Zorin-Kranich. Decoupling inequalities for quadratic forms, 2020.
  • [Gre10] Michael Greenblatt. Oscillatory integral decay, sublevel set growth, and the Newton polyhedron. Math. Ann., 346(4):857–895, 2010.
  • [Gut10] Larry Guth. The endpoint case of the Bennett-Carbery-Tao multilinear Kakeya conjecture. Acta Math., 205(2):263–286, 2010.
  • [Gut16] Larry Guth. A restriction estimate using polynomial partitioning. J. Amer. Math. Soc., 29(2):371–413, 2016.
  • [GZ19] Shaoming Guo and Ruixiang Zhang. On integer solutions of Parsell-Vinogradov systems. Invent. Math., 218(1):1–81, 2019.
  • [Hua47] Loo-Keng Hua. The additive prime number theory. Trav. Inst. Math. Stekloff, 22:179, 1947.
  • [Hua52] Loo-Keng Hua. On the number of solutions of Tarry’s problem. Acta Sci. Sinica, 1:1–76, 1952.
  • [Hua59] Loo-Keng Hua. On the tarry problem. Proc. Third All-Union Math. Congr. (Moscow, 1956). Vol. IV: Survey Reports, Izdat. Akad. Nauk SSSR, Moscow, pages 140–143, 1959.
  • [Hua65] L. K. Hua. Additive theory of prime numbers. Translations of Mathematical Monographs, Vol. 13. American Mathematical Society, Providence, R.I., 1965.
  • [IKM10] Isroil A. Ikromov, Michael Kempe, and Detlef Müller. Estimates for maximal functions associated with hypersurfaces in 3\mathbb{R}^{3} and related problems of harmonic analysis. Acta Math., 204(2):151–271, 2010.
  • [Ikr97] I. A. Ikromov. On the convergence exponent of trigonometric integrals. Tr. Mat. Inst. Steklova, 218(Anal. Teor. Chisel i Prilozh.):179–189, 1997.
  • [IM16] Isroil A. Ikromov and Detlef Müller. Fourier restriction for hypersurfaces in three dimensions and Newton polyhedra, volume 194 of Annals of Mathematics Studies. Princeton University Press, Princeton, NJ, 2016.
  • [IS13] I. A. Ikromov and A. R. Safarov. On estimates for double trigonometric integrals. Uzbek. Mat. Zh., (4):7–15, 2013.
  • [Kar80] V. N. Karpushkin. Uniform estimates of oscillating integrals in 𝐑2{\bf R}^{2}. Dokl. Akad. Nauk SSSR, 254(1):28–31, 1980.
  • [Kar83] V. N. Karpushkin. Uniform estimates of oscillating integrals with a parabolic or a hyperbolic phase. Trudy Sem. Petrovsk., (9):3–39, 1983.
  • [Kim17] Jongchon Kim. Some remarks on fourier restriction estimates, 2017.
  • [Moc96] Gerd Mockenhaupt. Bounds in Lebesgue spaces of oscillatory integral operators, 1996.
  • [NSW93] Alexander Nagel, Andreas Seeger, and Stephen Wainger. Averages over convex hypersurfaces. Amer. J. Math., 115(4):903–927, 1993.
  • [PS97] D. H. Phong and E. M. Stein. The Newton polyhedron and oscillatory integral operators. Acta Math., 179(1):105–152, 1997.
  • [PSS99] D. H. Phong, E. M. Stein, and J. A. Sturm. On the growth and stability of real-analytic functions. Amer. J. Math., 121(3):519–554, 1999.
  • [Saf19] A. R. Safarov. On the LpL^{p}-bound for trigonometric integrals. Anal. Math., 45(1):153–176, 2019.
  • [SSS91] Andreas Seeger, Christopher D. Sogge, and Elias M. Stein. Regularity properties of Fourier integral operators. Ann. of Math. (2), 134(2):231–251, 1991.
  • [Ste93] Elias M. Stein. Harmonic analysis: real-variable methods, orthogonality, and oscillatory integrals, volume 43 of Princeton Mathematical Series. Princeton University Press, Princeton, NJ, 1993. With the assistance of Timothy S. Murphy, Monographs in Harmonic Analysis, III.
  • [Tao99] Terence Tao. The Bochner-Riesz conjecture implies the restriction conjecture. Duke Math. J., 96(2):363–375, 1999.
  • [Tao03] Terence Tao. A sharp bilinear restrictions estimate for paraboloids. Geom. Funct. Anal., 13(6):1359–1384, 2003.
  • [Tar51] Alfred Tarski. A decision method for elementary algebra and geometry. University of California Press, Berkeley and Los Angeles, Calif., 1951. 2nd ed.
  • [TVV98] Terence Tao, Ana Vargas, and Luis Vega. A bilinear approach to the restriction and Kakeya conjectures. J. Amer. Math. Soc., 11(4):967–1000, 1998.
  • [Var76] A. N. Varčenko. Newton polyhedra and estimates of oscillatory integrals. Funkcional. Anal. i Priložen., 10(3):13–38, 1976.
  • [vdD98] Lou van den Dries. Tame topology and o-minimal structures, volume 248 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 1998.
  • [vdDMM94] Lou van den Dries, Angus Macintyre, and David Marker. The elementary theory of restricted analytic fields with exponentiation. Ann. of Math. (2), 140(1):183–205, 1994.
  • [Wol01] Thomas Wolff. A sharp bilinear cone restriction estimate. Ann. of Math. (2), 153(3):661–698, 2001.
  • [Woo19] Trevor D. Wooley. Nested efficient congruencing and relatives of Vinogradov’s mean value theorem. Proc. Lond. Math. Soc. (3), 118(4):942–1016, 2019.
  • [Wri11a] James Wright. From oscillatory integrals and sublevel sets to polynomial congruences and character sums. J. Geom. Anal., 21(1):224–240, 2011.
  • [Wri11b] James Wright. From oscillatory integrals to complete exponential sums. Math. Res. Lett., 18(2):231–250, 2011.
  • [Wri20] James Wright. The h and j functionals in the theory of complete exponential sums. arXiv preprint arXiv:2012.08211, 2020.