The Sharp Interpolation Algorithm for $C^m(\mathbb{R}^n)$ (Fefferman's Conjecture 2): computing $(1+\epsilon)$-optimal interpolants of finite data with near-linear work

Given a finite set $E\subset\mathbb{R}^n$ of $N$ points and values $f:E\to\mathbb{R}$, the interpolation problem asks for a function $F\in C^m(\mathbb{R}^n)$ with $F=f$ on $E$ and $\|F\|_{C^m(\mathbb{R}^n)}$ as close as possible to the optimum $\|f\|_{C^m(E)}$. Constant-factor optimal interpolants are computable with $O(N\log N)$ work for all $m,n$ (Fefferman-Klartag), but achieving $(1+\epsilon)$-optimality - the sharp regime - is far harder: the sharp finiteness principle fails already for $C^2(\mathbb{R}^2)$. Fefferman's 'Nearly optimal interpolation of data in $C^2(\mathbb{R}^2)$. Part I' (2012) announces Theorem 1: for $C^2(\mathbb{R}^2)$, a $(1+\epsilon)$-optimal interpolant computable with one-time work $C(\epsilon)N\log N$, query work $C\log(N/\epsilon)$ and storage $C(\epsilon)N$, with $C(\epsilon)$ superexponential in $\epsilon$; and poses Conjecture 2 (the Sharp Interpolation Algorithm): such an algorithm exists for every $C^m(\mathbb{R}^n)$. The announced proof of Theorem 1 is incomplete in the published record - Step II of the main algorithm was deferred to a 'Part II' that has never appeared; and no later work resolves Conjecture 2 for general $m,n$, completes Step II, or improves the $\epsilon$-dependence. The later program literature (Sobolev, nonnegative and range-restricted variants) treats constant-factor or constrained analogues. The problem - to prove or refute Conjecture 2 for general $m,n$, and, independently of that outcome, to supply a complete proof for the base case $C^2(\mathbb{R}^2)$ - remains open.

Background

Fix positive integers $m$ and $n$. Let $C^m(\mathbb{R}^n)$ denote the space of real-valued functions on $\mathbb{R}^n$ all of whose derivatives up to order $m$ are bounded and continuous, normed by $\|F\|_{C^m(\mathbb{R}^n)}=\sup_{x\in\mathbb{R}^n}\max_{|\alpha|\le m}|\partial^\alpha F(x)|$; Part I in fact allows any equivalent norm of jet form $\|F\|_{C^m(\Omega)}=\sup_{x\in\Omega}|J_x(F)|_x$, where $J_x(F)$, the jet of $F$ at $x$, is the Taylor polynomial of $F$ of degree $m$ centered at $x$, and the family of norms $|\cdot|_x$ on the space $\mathcal{P}$ of polynomials of degree at most $m$ satisfies two regularity conditions: the Bounded Distortion Property, namely $c_0\max_{|\alpha|\le m}|\partial^\alpha P(x)|\le|P|_x\le C_0\max_{|\alpha|\le m}|\partial^\alpha P(x)|$ for every $P\in\mathcal{P}$ and every $x$ (each norm is uniformly comparable to the standard jet norm), and the Approximate Translation-Invariance Property, namely $|P|_{x+h}\le\exp(C_1|h|)\,|P|_x$ for every $P\in\mathcal{P}$ and all $x,h\in\mathbb{R}^n$ (norms at nearby points differ by at most an exponential factor), for constants $c_0,C_0,C_1$ depending only on the chosen family. Given a finite set $E\subset\mathbb{R}^n$ of $N$ points and values $f:E\to\mathbb{R}$, an interpolant of $f$ is a function $F\in C^m(\mathbb{R}^n)$ with $F=f$ on $E$. Write

$$\|f\|_{C^m(E)}=\inf\{\|F\|_{C^m(\mathbb{R}^n)}:\ F\in C^m(\mathbb{R}^n),\ F=f\ \text{on}\ E\},$$

and call $F$ an $A$-optimal interpolant if $\|F\|_{C^m(\mathbb{R}^n)}\le A\,\|f\|_{C^m(E)}$. The problem of extending or interpolating smooth data from closed or finite sets goes back to Whitney's 1934 extension theorem, which characterizes extendability through Whitney fields - families of jets $(P_x)_{x\in E}$ obeying pairwise compatibility inequalities - with norm $\|P\|_{\mathrm{Wh}(E)}$, the infimum of $\|F\|_{C^m(\mathbb{R}^n)}$ over all $F$ realizing those jets.

A recurring structural tool is the finiteness principle: for a constant $k^\#(m,n)$, the norm $\|f\|_{C^m(E)}$ is comparable, up to a factor depending only on $m$ and $n$, with the maximum of $\|f|_S\|_{C^m(S)}$ over subsets $S\subset E$ with at most $k^\#$ points (Brudnyi-Shvartsman 1994; sharp forms of Whitney's theorem in Fefferman 2005). In the borderline regularity $C^{1,1}(\mathbb{R}^n)$ - functions whose gradient is Lipschitz continuous, with seminorm $\sup_{x\ne y}|\nabla F(x)-\nabla F(y)|/|x-y|$ - Le Gruyer's two-point theorem reduces the extension test to pairs of points.

Computationally, Part I fixes an idealized machine: a von Neumann computer (standard stored-program architecture) whose registers and memory cells hold exact real numbers, on which elementary arithmetic operations are performed without roundoff error, one unit of work being charged per arithmetic operation or memory access; information about the norm family $|\cdot|_x$ is obtained from an oracle that returns the value $|P|_x$ for a query $(x,P)$, also at unit cost. (Part I later weakens this assumption: in its Section 5, working in $C^2(\mathbb{R}^2)$, the oracle returns a number $N(P,x,\eta)$ with $(1+\eta)^{-1}N(P,x,\eta)\le|P|_x\le(1+\eta)N(P,x,\eta)$, at a charge of $\exp(C_2/\eta)$ units of work per call.) After reading $(E,f,\epsilon)$, an algorithm performs one-time work and then answers queries: a query $x\in\mathbb{R}^n$ triggers a query algorithm that returns the numbers $\partial^\alpha F(x)$ for $|\alpha|\le m$; the function $F$ must be uniquely determined before any query is asked (adaptive algorithms, in which $F$ depends on the queries, are disallowed), and the query algorithm may not call the oracle. Storage is the number of memory cells used.

In this model Fefferman-Klartag ('Fitting a $C^m$-smooth function to data I, II', 2009) gave the foundational constant-factor result (Theorem 2 of Part I): for all $m$ and $n$, an $A$-optimal interpolant is computable with one-time work $CN\log N$, query work $C\log N$ and storage $CN$. The sharp question - replacing the constant factor by $1+\epsilon$ - was first settled for Whitney fields (prescribed jets) by Fefferman ('The $C^m$ norm of a function with prescribed jets II', 2009) with work $\exp(C/\epsilon)\,N\log N$ (Theorem 3 of Part I), and for data with work $\exp(C/\epsilon)\,N^5(\log N)^2$ (Theorem 4 of Part I).

Part I (Fefferman 2012) attacks the sharp data problem for $C^2(\mathbb{R}^2)$. Theorem 1: for $0<\epsilon<1/2$ one computes both a number $|||f|||$ with $(1+\epsilon)^{-1}|||f|||\le\|f\|_{C^2(E)}\le(1+\epsilon)|||f|||$ and a $(1+\epsilon)$-optimal interpolant, with one-time work $C(\epsilon)\,N\log N$, query work $C\log(N/\epsilon)$ and storage $C(\epsilon)\,N$; the $N$-dependence is announced as most likely optimal, but $C(\epsilon)$ is superexponential in $\epsilon$. The finiteness-principle route is provably blocked: the sharp finiteness principle (Conjecture 1 of Part I) fails already for $C^2(\mathbb{R}^2)$, by a counterexample of Fefferman-Klartag (2009). Part I therefore develops, for $C^2(\mathbb{R}^2)$, a Calderon-Zygmund decomposition of the plane into axis-parallel squares $Q_\nu$ on which the data lie along finitely many graphs, and, on a fine net inside each square, a convex polyhedron $K_\nu$ of Whitney fields describing the jets of functions of norm at most $1$ that interpolate the local data. Step I of the main algorithm - computing the $K_\nu$ and the local interpolants - is carried out in Part I. Step II - selecting local interpolants that fit together and patching them, by means of a partition of unity (a family of smooth nonnegative weights summing to 1, used to blend local pieces into one global function), into a global interpolant of norm below $1+C\epsilon$ whose jet on $E$ can be computed - is deferred to a sequel, 'Nearly optimal interpolation of data in $C^2(\mathbb{R}^2)$. Part II', listed as in preparation in Part I's bibliography. That sequel has never appeared, so the published proof of Theorem 1 is incomplete; and Part I's closing Conjecture 2, the Sharp Interpolation Algorithm, asks whether the phenomenon extends to every $C^m(\mathbb{R}^n)$.

Problem Statement

Fix $m,n\ge 1$ and a $C^m(\mathbb{R}^n)$-norm of jet form $\|F\|_{C^m(\Omega)}=\sup_{x\in\Omega}|J_x(F)|_x$, where the norm family $|\cdot|_x$ satisfies the Bounded Distortion Property and Approximate Translation-Invariance as in Part I. All constants below depend on the choice of norm, and $N$ denotes $\#(E)$.

Main question (Conjecture 2 of Fefferman, 'Nearly optimal interpolation of data in $C^2(\mathbb{R}^2)$. Part I' - the Sharp Interpolation Algorithm). Prove or refute: for every $\epsilon>0$ there exists an algorithm which, given $f:E\to\mathbb{R}$ on a finite set $E\subset\mathbb{R}^n$ with $\#(E)=N$, computes a $(1+\epsilon)$-optimal interpolant for $f$ - that is, a function $F\in C^m(\mathbb{R}^n)$ with $F=f$ on $E$ and $\|F\|_{C^m(\mathbb{R}^n)}\le(1+\epsilon)\|f\|_{C^m(E)}$ - on the exact-real von Neumann machine with oracle access to the norm family, subject to

$$\text{one-time work}\ \le\ C(\epsilon)\,N\log N,\qquad \text{query work}\ \le\ C\log(N/\epsilon),\qquad \text{storage}\ \le\ C(\epsilon)\,N,$$

where $C(\epsilon)$ depends only on $\epsilon,m,n$ and the choice of norm, and $C$ only on $m,n$ and the choice of norm. The computed $F$ must be uniquely determined before any query is asked (no adaptivity), and the query algorithm may not call the oracle. The conjecture is posed for every pair $(m,n)$: a positive answer must cover all of them, and each fixed $(m,n)$ is a well-defined instance.

Integral component fixed by the source: the base case $C^2(\mathbb{R}^2)$, i.e. the $m=n=2$ instance of the Main question. Theorem 1 of Part I asserts this conclusion for $m=n=2$ and $0<\epsilon<1/2$ - and, as a strengthening, also computes a number $|||f|||$ with $(1+\epsilon)^{-1}|||f|||\le\|f\|_{C^2(E)}\le(1+\epsilon)|||f|||$ - but the published proof is incomplete - Step II of Part I's main algorithm, i.e. patching the local interpolants furnished by Step I into a global interpolant of $C^2$-norm at most $1+C\epsilon$ and computing its jet on $E$ within the work bound, was deferred to a 'Part II' that has never been published. The resolution boundary is therefore explicit: the Main question is settled either by a proof of Conjecture 2 for all pairs $(m,n)$, or by a refutation at a single pair $(m,n)$; a proof of the base case alone does not settle it. Independently of which branch is taken, a full resolution also requires a complete proof of the base case - the $m=n=2$ instance of the Main question - whether by completing Part I's Step II or by another route, since a refutation of Conjecture 2 at some $(m,n)$ does not by itself settle $C^2(\mathbb{R}^2)$.

Secondary quality questions attached to the same objective by the source, but not part of the truth of the conjecture: improving the superexponential dependence of $C(\epsilon)$ on $\epsilon$ (hoped for by the source, already for $C^2(\mathbb{R}^2)$), and the optimality of the $N$-dependence (one-time work $N\log N$, query work $\log N$), which the source asserts is most likely optimal.

References

1. Charles Fefferman, 'Nearly optimal interpolation of data in $C^2(\mathbb{R}^2)$. Part I', Revista Matemática Iberoamericana 28 (2012), no. 2, 415-533, DOI 10.4171/rmi/683, https://doi.org/10.4171/rmi/683
2. Charles Fefferman and Bo'az Klartag, 'Fitting a $C^m$-smooth function to data I', Annals of Mathematics (2) 169 (2009), no. 1, 315-346, DOI 10.4007/annals.2009.169.315, https://doi.org/10.4007/annals.2009.169.315
3. Charles Fefferman and Bo'az Klartag, 'Fitting a $C^m$-smooth function to data II', Revista Matemática Iberoamericana 25 (2009), no. 1, 49-273, DOI 10.4171/rmi/569, https://doi.org/10.4171/rmi/569
4. Charles Fefferman, 'The $C^m$ norm of a function with prescribed jets II', Revista Matemática Iberoamericana 25 (2009), no. 1, 275-421, DOI 10.4171/rmi/570, https://doi.org/10.4171/rmi/570
5. Charles Fefferman and Bo'az Klartag, 'An example related to Whitney extension with almost minimal $C^m$ norm', Revista Matemática Iberoamericana 25 (2009), no. 2, 423-446, DOI 10.4171/rmi/571, https://doi.org/10.4171/rmi/571
6. Hassler Whitney, 'Analytic extensions of differentiable functions defined in closed sets', Transactions of the American Mathematical Society 36 (1934), no. 1, 63-89, DOI 10.1090/S0002-9947-1934-1501735-3, https://doi.org/10.1090/S0002-9947-1934-1501735-3
7. Yuri Brudnyi and Pavel Shvartsman, 'Generalizations of Whitney's extension theorem', International Mathematics Research Notices 1994 (1994), no. 3, 129-139, DOI 10.1155/S1073792894000140, https://doi.org/10.1155/S1073792894000140
8. Charles Fefferman, 'A sharp form of Whitney's extension theorem', Annals of Mathematics (2) 161 (2005), no. 1, 509-577, DOI 10.4007/annals.2005.161.509, https://doi.org/10.4007/annals.2005.161.509
9. Erwan Le Gruyer, 'Minimal Lipschitz extensions to differentiable functions defined on a Hilbert space', Geometric and Functional Analysis 19 (2009), no. 4, 1101-1118, DOI 10.1007/s00039-009-0027-1, https://doi.org/10.1007/s00039-009-0027-1
10. Charles Fefferman, 'Whitney's extension problems and interpolation of data', Bulletin of the American Mathematical Society (new series) 46 (2009), no. 2, 207-220, DOI 10.1090/S0273-0979-08-01240-8, https://doi.org/10.1090/S0273-0979-08-01240-8
11. Charles Fefferman, Arie Israel and Garving K. Luli, 'Fitting a Sobolev function to data I', Revista Matemática Iberoamericana 32 (2016), no. 1, 275-376, DOI 10.4171/rmi/887, https://doi.org/10.4171/rmi/887
12. Charles Fefferman, Arie Israel and Garving K. Luli, 'Interpolation of data by smooth nonnegative functions', Revista Matemática Iberoamericana 33 (2017), no. 1, 305-324, DOI 10.4171/rmi/938, https://doi.org/10.4171/rmi/938
13. Charles Fefferman and Arie Israel, 'Fitting Smooth Functions to Data', CBMS Regional Conference Series in Mathematics 135, American Mathematical Society, Providence, RI, 2020, DOI 10.1090/cbms/135, ISBN 978-1-4704-6130-0, https://doi.org/10.1090/cbms/135
14. Fushuai Jiang and Garving K. Luli, 'Nonnegative $C^2(\mathbb{R}^2)$ interpolation', Advances in Mathematics 375 (2020), 107364, DOI 10.1016/j.aim.2020.107364, https://doi.org/10.1016/j.aim.2020.107364
15. Fushuai Jiang and Garving K. Luli, 'Algorithms for nonnegative $C^2(\mathbb{R}^2)$ interpolation', Advances in Mathematics 385 (2021), 107756, DOI 10.1016/j.aim.2021.107756, https://doi.org/10.1016/j.aim.2021.107756
16. Charles Fefferman, Fushuai Jiang and Garving K. Luli, '$C^2$ interpolation with range restriction', Revista Matemática Iberoamericana 39 (2023), no. 2, 649-710, DOI 10.4171/rmi/1353, https://doi.org/10.4171/rmi/1353