A Computationally-Efficient Closed-Form $C^{s,1}$-Extension Formula

1 Introduction

• Reconstructing a function from finite samples while matching derivative data and preserving the function’s regularity is substantially harder than interpolation alone.The introduction notes that existing methods for C^{s,1} data can incur first-derivative growth with the number of samples.Source: §1 · pp. 1–2

1.1 Our Contribution

• For s≥2, the paper identifies a closed-form extension formula as an endpoint of its variational family, while its s=0 and s=1 cases recover known formulas.The s=0 case coincides with McShane, and the s=1 case with the C^{1,1} formula of.Source: §1 · p. 2, §1.1 · p. 2

1.1.1 Analytic Properties

• The reconstruction interpolates all prescribed derivatives through order s, has a dimension- and smoothness-dependent C^{s,1} seminorm bound, and is definable in R_exp.For s≥2, it is also real-analytic away from the data points.Source: §1.1.1 · p. 2

1.1.2 Computational Properties

• For fixed d and s≥2, evaluation uses O_{d,s}(N) circuit work and storage with O_{d,s}(1 + log N) parallel depth; assembly takes O_{d,s}(N) work from supplied parameters.The comparison with Fefferman and Klartag [10] is model-dependent, and the assembly bound excludes constructing the required weights.Source: §1.1.2 · p. 3, Table 1 · p. 3

Organization of the Paper

• The paper proceeds from notation and the variational family to analytic and computational results, low-order coincidence results, and proofs.The proofs are collected in Sections 9 and 10, with auxiliary non-analyticity arguments in Appendix B.Source: Organization of the Paper · pp. 3–5

1.2 Related Work

• Prior finite-data Whitney constructions can have sparse, efficient representations, but those representations are not available in closed form.The related-work discussion also contrasts earlier finite-set constructions with the paper’s off-site analyticity result for s≥2.Source: §1.2 · p. 4

Integer and scalar notation

• N denotes the non-negative integers, N+ the positive integers, and [n] the indices from 1 through n.The notation also defines the ceiling and positive-part operations.Source: §2 · p. 5

Norms and regularity

• The paper uses operator norms for multilinear derivatives and defines the C^{s,1} seminorm through the Lipschitz behavior of the s-th derivative.At order zero, the norm is absolute value; the homogeneous class imposes no global boundedness requirement.Source: §2 · p. 5

Probability and weights

• Probability vectors in the simplex represent distributions on finite sets, and the paper defines relative entropy with respect to a reference distribution.A doubling-type condition bounds how much the total weight in a ball can increase when its radius is doubled.Source: §2 · pp. 5–6

3 The Variational Formulation

• Setting 3.1 fixes distinct sites, an unknown C^s,1 function, and degree-at-most-s polynomials; the fill radius measures the worst nearest-site distance over (0,1)^d.The fill radius is defined as the supremum over the domain of the distance to the nearest data site.Source: §3 · p. 6
• For fixed ϑ, the authors define a one-parameter family of variational formulae Fϑ at the measurement sites.The family is presented for all regularity regimes before specializing the closed-form computational results.Source: §3 · p. 6
• For s ≥2, the section's main result gives an identity connecting the closed-form reconstruction Fext to the variational family.The analytic arguments treat the variational formula for all s, while the computational arguments specialize to the closed-form version.Source: §3 · pp. 6–7

4.1 Analytic Results

• For s≥2, the reconstruction is real-analytic away from the data sites and definable in Rexp; multiplying by a plateau function gives global norm control.The plateau equals one on [0,1]^d and vanishes outside a neighborhood of the cube.Source: §4.1 · pp. 7–8
• Theorem 4.1 combines interpolation through order s with a homogeneous seminorm bound to yield full C^s,1 control on [0,1]^d, with the stated bound independent of sample size and separation beyond measured jet values.The cube-wide control follows from interpolation and the homogeneous seminorm bound.Source: §4.1 · p. 7

4.2 Complexity Theoretic Results

• Evaluation is analyzed in a gate model, while uniform circuit compilation is assessed separately in the exact-real word-RAM model.Source: §4.2 · p. 8

4.3 Computational Complexity of Fext

• For fixed d and s≥2, a bounded-fan-in circuit computes Fext away from the data sites with storage and width O_s(Nds) and parallel query time O_s(log(d+N)).The section also reports O_d,s(1+log N) parallel gate-evaluation time and Θ_d,s(N) storage.Source: §4.3 · p. 8

4.4 The Complexity of Assembling Fext

• A uniform exact-real word-RAM compiler builds the circuit from supplied site coordinates, polynomial coefficients, weights, and integer q; its bound excludes finding admissible weights and computing q from D.Source: §4.4 · p. 9, §4.3 · p. 9

5 Coincidence with the Known s = 0, 1 Formulae

• For s = 0, the formula takes the smallest measurement-imposed upper bound, yielding the pointwise largest M-Lipschitz interpolant.Each bound is f(X_n) + M∥x − X_n∥.Source: §5 · p. 9
• For s = 1, the paper recovers the Azagra–Le Gruyer–Mudarra formulae [1, Theorem 3.4; 2].Source: §5 · p. 9
• The s = 1 construction adds a common quadratic before taking the lower-semicontinuous convex envelope, then subtracts it to match values and gradients with Lip(∇F) ≤ M.Here, the envelope is the largest convex function lying below its input.Source: §5 · p. 10

6 Future Work

• A sharpened formula achieving the minimal possible constant remains a future-work goal.Source: §6 · p. 10
• The authors hope the formula will inspire applications to algorithmic foundations of machine learning.Source: §6 · p. 10
• The authors invite others to build on the formula.Source: §6 · p. 10

7 LEAN Certificate

• Theorem 4.1 was certifiably verified in LEAN except for definability in Rexp, which the authors say the model does not currently support.Source: §7 · p. 10
• Theorem 4.4 was certifiably verified in LEAN.Source: §7 · p. 10
• The authors also report certifiable verification of all supporting results and provide the LEAN code and certificate with the arXiv upload.Source: §7 · p. 10

8.1 Thanks

• Charles Fefferman’s remarks reshaped the trajectory of the paper.Source: §8.1 · p. 10
• Carlos Mudarra provided feedback and explanations of ideas behind the C1,1 extension formulae.Source: §8.1 · p. 10

8.2 AI Declaration

• The authors report using Chat GPT 6, Astra to refine the variational formula, proofread and formalize arguments, and compile the LEAN certificate.Source: §8.2 · p. 10

9 Proofs

• For s ≥2, normalized derivative estimates yield exact interpolation and global Lipschitz control of DsFϑ, with ϑ = 1 proving Theorem 4.1 and ϑ = 0 proving Proposition 3.1.The proof subtracts a fixed Taylor polynomial and scales by local distance to control derivatives near sites despite singular inverse-distance factors.Source: §9 · p. 11

9.1 Proof Theorem 4.1 (i): The Jet Interpolation Property

• The construction gives positive geometry weights satisfying (2.4) with doubling certificate D = 246d, independent of the number and distribution of sites.The weights are constructed by transferring controlled weights between successively finer subsets of the sites.Source: §9.1 · pp. 11, 13
• The finite-jet seminorm W_DN vanishes exactly when all prescribed polynomials Pi are the same polynomial.In that case, the passage states that one may take g = P1.Source: §9.1 · p. 16
• For s=0, the construction reduces to the minimum of f(X_i)+M|x−X_i|, interpolates the sites, and is M-Lipschitz; for s=1, it matches values and gradients with M-Lipschitz gradient.Source: §9.1 · pp. 18, 22
• The quadratic envelope is represented as a variance minimization over the simplex, with compactness ensuring that the minimum is attained.Source: §9.1 · pp. 18, 20
• The entropy optimization has unique positive minimizing weights and a unique dual maximizer; the optimizers and value vary smoothly with parameters, and its stationarity Jacobian inverse has norm at most one.Source: §9.1 · pp. 22–24
• For s≥2, subtracting the Taylor polynomial at the evaluation point and rescaling by local distance yields exponential tails controlling weighted powers of distant-site distances uniformly in N.The tail-bound constants are independent of the parameter ϑ.Source: §9.1 · p. 24
• The remaining derivative estimates are organized through nonnegative scalar series that bound Taylor coefficients of the geometric quantities and optimizer.The proof develops majorants for geometric primitives and Gibbs quotient behavior around the optimizer.Source: §9.1 · pp. 26, 30, 33
• Taylor majorization is defined coefficientwise for finite jets, so its truncated estimates require neither convergent Taylor series nor analytic functions.The relation at order n depends only on the order-n Taylor jet.Source: §9.1 · p. 27
• Majorization is preserved by addition, bounded bilinear products, and composition; scalar exponential, reciprocal, and logarithm expressions also admit corresponding majorants.The composition rule assumes zero constant terms for the inner function and its majorant.Source: §9.1 · p. 27
• Off the sites, derivative-order j errors vanish like the fill distance to the power s+1−j, with bounds independent of N, site separation, minimum atomic weight, and ϑ.The estimates apply for derivative orders 0 through s; the off-site reconstruction is smooth, and the stated constant is uniform in ϑ.Source: §9.1 · pp. 40–41
• Derivative-error bounds that decay at least linearly with distance to each site ensure the continuously extended derivative formulas are successive derivatives there.The finite-site argument concludes that G is C^s and that its derivatives through order s agree with the prescribed function’s derivatives at the sites.Source: §9.1 · p. 41
• For every nonnegative integer s, the construction interpolates the function values and derivatives through order s at the data sites.For s ≥ 2, the proof combines off-site smoothness and local error bounds with differentiability through the finite sites; the cases s = 0 and s = 1 are handled separately.Source: §9.1 · p. 42

9.2 Proof Theorem 4.1 (ii): Cs,1-Smoothness

• The degree-at-most-s comparison polynomial contributes no derivative of order s+1, so bounds away from the sites extend to a global Lipschitz estimate for D^sF.Continuity of D^sF and integration along line segments include estimates across measurement sites; the bound is uniform in ϑ.Source: §9.2 · p. 42
• A line segment meets the finite site set in finitely many points, allowing off-site derivative bounds to be applied piecewise across those sites.The proof partitions the segment at its intersections with the sites before applying the across-sites Lipschitz argument.Source: §9.2 · p. 43
• The calibrated reconstruction belongs to ˙C^{s,1}(R^d) with seminorm at most K_{d,s}M, where K_{d,s} has an explicit bound depending only on d and s.The proof treats s=0, s=1, and s≥2 separately.Source: §9.2 · pp. 44–45

9.3 The Fixed-Parameter Family and the Entropy-Only Endpoint

• For every fixed ϑ∈[0,1], Fϑ interpolates the prescribed derivatives through order s and satisfies [Fϑ]s,1≤K_{d,s}M.The seminorm estimate is uniform in the fixed parameter ϑ.Source: §9.3 · pp. 45–46
• At ϑ=0, the entropy-only endpoint is the unique minimizer of its objective and interpolates the prescribed jets with seminorm at most K_{d,s}M.On the off-site domain, eF is real analytic and definable in Rexp; its defining formula uses the site coordinates, polynomial coefficients, M, and weights, not the witness f.Source: §9.3 · pp. 47–48
• For finite jets, W=0 exactly when all polynomials coincide; an extension otherwise achieves [g]s,1≤κd,sW, independently of N, atomic masses, and site separation.When W=0, one may take g=P1.Source: §9.3 · pp. 48, 50

9.4 Proof of Analyticity Away from the Data; Theorem 4.1 (iv)

• The dual representation replaces optimization over mixing weights with optimization over a vector in Rd, and the two optimal values agree.The objective values differ by a squared norm and a relative entropy, both of which vanish for weights recovered from a dual maximizer.Source: §9.4 · p. 50
• The primal minimum and dual maximum are attained and have equal values, and the reconstruction agrees with the prescribed data at every site.The gap identity vanishes at the respective optimizers; the on-site definitions give G(Xn) = F(Xn) = Pn(Xn).Source: §9.4 · pp. 53–54
• For s ≥2, the reconstruction F is real-analytic on Rd \ XN.The proof identifies the unique minimizer through an analytic system and applies the analytic implicit-function argument locally.Source: §9.4 · pp. 54–56

9.5 Proof of Definability in Rexp

• For fixed d, N, and s, the calibrated reconstruction is definable in Rexp using the sites, polynomial coefficients, M, and weights as real parameters.The proof represents the minimum through a first-order definable condition and extends definability to the data sites; it does not require a unique minimizer or definability of f.Source: §9.5 · pp. 56, 58

9.6 Proof of Corollary 4.2

• The estimates in Corollary 4.2 follow by combining Taylor remainders with the global C^{s,1} seminorm bound.The argument covers s = 0, N = 1, and sites on the cube boundary.Source: §9.6 · p. 58

9.6.1 Proof of Lipschitz Regularity

• On an open convex set, a C1 function’s Lipschitz constant equals the supremum norm of its gradient, and both are finite when it is C1 near a compact set.The proof bounds increments by integrating the gradient along each line segment and bounds directional derivatives by the Lipschitz constant.Source: §9.6.1 · pp. 58–59

10.1 Proof of Complexity Theoretic Result Theorem 4.4

• Parallel constructions compute m-ary sums, products, and the Euclidean norm with size and width O(m) and depth O(log m).The absolute value has depth, width, and size O(1).Source: §10.1 · p. 59
• The coordinate functions of θ have size and width O(dN) and depth O(log d + log N), and R has the same asymptotic bounds.The exponential-factor subcircuit also has size and width O(dN) and depth O(log d + log N).Source: §10.1 · pp. 61–62
• For fixed d and s, the master circuit computes Fext on all of R^d with size and width O(N) and depth O(log N).The bounds include the point-indicator subcircuits and input adjustment that ensure the realization domain is all of R^d.Source: §10.1 · p. 65

10.2 Proof of Theorem 4.5

• Theorem 4.5 proves that a fixed program depending only on d and s stores the circuit from supplied data using O_s(Nd^s) one-time work.The program stores operations with their parameters and input indices in a representation compatible with the exact-real word-RAM model.Source: §10.2 · p. 65
• Every edge increases creation order, so the emitted graph is acyclic; all its vertices reach the output, and the underlying graph is connected.The proof identifies the emitted vertices as precisely those with a directed path to the output; since every vertex reaches that output, any two vertices are joined by an undirected path.Source: §10.2 · pp. 68, 72
• On U = R^d \ {X_1, ..., X_N}, the emitted handles evaluate to the extension, while at each data point the corresponding polynomial gives the prescribed value.The proof identifies E_ui(x) = P_i(y(x)), E_ηi(x) = θ_i(y(x)), and E_r(x) = R(y(x)); with y the emitted safe-point map, it concludes the output equals F_ext(x).Source: §10.2 · p. 71
• The ordered adjacency representation is filled in three scans using W_scan ≤ C(3K + 1) = O(K) work and occupies 5K + 2 cells.The labeling is a bijection, and the representation stores four word fields and one real field per vertex, plus two headers.Source: §10.2 · pp. 67, 72, 73
• Each reduction with m ≥ 2 emits fewer than 3m gates, and each polynomial template emits fewer than 8B gates.The reduction bound is G_ρ⋆,m = 2⌈m⌉ − m − 1 < 3m; the polynomial-template bound is G_Poly < 8B.Source: §10.2 · p. 74
• A finite program implements exact emissions and scans with initialization cost Winit ≤ CH0 and scan cost Wscan ≤ CK.The implementation bounds also ensure every intermediate word value is strictly below 2w.Source: §10.2 · pp. 75–76
• The output circuit depth is at most Cs log2(d + N).The constructor depth recurrence is bounded by 42 + 3hs + hB + 2hd + 5hN, which is itself at most Cs log2(d + N).Source: §10.2 · pp. 75, 77
• A parallel schedule evaluates the circuit in Dout ≤ Cs log2(d + N) steps using at most K − d ideal processors.At each time t, at most CsNds gates are scheduled, and induction ensures their operands are available by time t − 1.Source: §10.2 · p. 77

• The complexity framework covers both non-uniform, non-recursive and uniform, recursive algorithms.Source: A Background on Complexity Theory · p. 78
• The appendix reviews the background and conventions used to quantify algorithm complexity.Source: A Background on Complexity Theory · p. 78
• Circuits and the exact-real word-RAM model provide the respective languages for these algorithmic settings.Source: A Background on Complexity Theory · p. 78

A.1 Circuits

• A bounded-fan-in G-circuit is a connected directed acyclic graph with input, computation, and single-output vertices; computation gates have arity at most two.Source: §A.1 · p. 78
• A binary row-stochastic lifting channel assigns each circuit input one external coordinate, allowing coordinates to be reused across inputs.Source: §A.1 · p. 78
• A topological ordering defines computation recursively, with gate compatibility requiring valid arguments for division, logarithm, and power gates.Source: §A.1 · pp. 78–79
• A circuit computes a function on a domain when that domain lies in its realization domain and its output equals the function there.Source: §A.1 · p. 79
• Circuit depth is defined from vertex dependencies, while unit-cost gates make gate count the work measure and permit equal-depth gates to run simultaneously.Source: §A.1 · p. 79

A.2 The Exact-Real Word-RAM Model

• The model provides word and real memory arrays, both addressed by word-sized indices, with exact-real values stored in the real array.Its state includes the program counter and the contents of both arrays.Source: §A.2 · p. 79
• Unit-cost instructions include word arithmetic and comparisons, exact-real addition, subtraction, multiplication, and division, and conditional or unconditional jumps.Division is permitted only when the divisor is nonzero.Source: §A.2 · p. 79
• The model measures exact-real arithmetic work and random-access storage, but excludes bit complexity, finite-precision error, conditioning, and memory-communication cost.It also disallows converting arbitrary exact real numbers into words, including by floor, ceiling, or binary-representation extraction.Source: §A.2 · p. 80

A.3 RAM Implementation of the Circuit Compiler

• The emitter program and three relabelling scans are implementable by a finite exact-real word-RAM program independent of N, q, w, and the real input values when condition (A.5) holds.The program’s fixed instructions and literals depend only on d and s.Source: §A.3 · p. 80
• Each gate parameter and scalar record append costs at most C instructions after the shared safe-point computation, excluding table copies.Three scans have work at most C(3K + 1), and the output representation occupies 5K + 2 cells.Source: §A.3 · pp. 80, 83
• Input, output, and auxiliary storage together use at most 3265H0 word cells and 835H0 real cells.The output representation itself occupies exactly 5K + 2 cells.Source: §A.3 · p. 80
• The gate parameters use fixed rational literals, input reads, arithmetic, sign tests, and the displayed embedding, without evaluating D, powers, exponentials, or logarithms.After computing a, each parameter costs at most C instructions.Source: §A.3 · p. 84

B Non-Analyticity Checks Made In the Introduction

• The section examines whether two other state-of-the-art Whitney extension theorems yield constructions that are real-analytic away from training data.The authors frame the discussion as a comparison of those constructions’ analyticity properties.Source: B Non-Analyticity Checks Made In the… · p. 84
• The comparison concerns analyticity away from the training data, rather than other properties of the extension constructions.This is the specific property the section says it checks.Source: B Non-Analyticity Checks Made In the… · p. 84
• The analysis is limited to the finite-training-dataset setting considered in the paper.No broader dataset setting is included in this stated scope.Source: B Non-Analyticity Checks Made In the… · p. 84

B.1 Non Real-Analyticity of [7]

• For d ≥ 2, exact interpolation and depth0(T) < N imply that some basis function ϕn is not real-analytic on U = R^d \ X.The proposition’s hypotheses require (Tf)|X = f for every f in R^X.Source: §B.1 · p. 84
• The obstruction applies to the finite-depth linear C^s-extension operator in [7] when N > Cdep(s, d), with tolerance σ ≡ 0.The cited construction is also recalled in [10].Source: §B.1 · p. 84
• The proof also establishes that U is path connected by joining points through an intermediate point while avoiding finitely many lines.The construction uses d ≥ 2 so each avoided line has empty interior.Source: §B.1 · pp. 84–85
• The proof uses the identity principle: if every ϕn were analytic, their nonzero sets would be open and dense, yielding a common point that contradicts the depth bound.The identity principle is applied on U, and exact interpolation supplies the contradiction at the chosen point.Source: §B.1 · pp. 84–85
• For the recalled operator, at most Cdep(s, d) basis functions are nonzero at any point, giving depth0(T) ≤ Cdep(s, d) < N.This finite-depth bound supplies the proposition’s depth hypothesis.Source: §B.1 · p. 85

B.2 Non Real-Analyticity of [22]

• For d ≥ 2, the construction extends a nonzero Whitney jet to a compactly supported function that is not real-analytic on U.Here U is the complement of the finite data set X.Source: §B.2 · pp. 85–86
• The recursion preserves support in K by correcting the selected point with a cutoff and recursively extending the residual jet.The cutoff makes the correction vanish near the other points, and the residual jet vanishes outside the remaining auxiliary support set.Source: §B.2 · p. 86
• If the extension were real-analytic on U, its restriction to a line avoiding X would be analytic and vanish outside a bounded interval, forcing it to vanish everywhere.The resulting zero function contradicts interpolation of the prescribed nonzero jet.Source: §B.2 · p. 86