pith. sign in

arxiv: 2604.01146 · v3 · submitted 2026-04-01 · 🧮 math.NA · cs.NA

A deterministic multiple-shift lattice algorithm for function approximation in Korobov and half-period Cosine spaces

Jiarui Du , Josef Dick This is my paper

Pith reviewed 2026-05-13 22:05 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords deterministic lattice algorithmsKorobov spaceshalf-period cosine spacesfunction approximationChinese Remainder TheoremWeil boundworst-case errortent transformation
0
0 comments X

The pith

A deterministic multiple-shift lattice algorithm achieves optimal worst-case convergence rates for approximation in Korobov and half-period cosine spaces without randomization or pre-computation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a fully deterministic method for approximating multivariate periodic functions in weighted Korobov spaces using rank-1 lattices. Frequency aliasing is handled through a simplified multiple-shift framework combined with an adaptive hybrid construction. This construction applies the Chinese Remainder Theorem and Weil bound to guarantee that the reconstruction matrix has full rank and bounded condition number. The method is shown to preserve the optimal convergence rate in the worst-case setting. The framework is extended via the tent transformation to half-period cosine spaces, where it attains optimal L2 and L_infty orders and resolves an open problem from 2016.

Core claim

The central claim is that the deterministic multiple-shift lattice algorithm, built with an adaptive hybrid construction via the Chinese Remainder Theorem and Weil bound, algebraically guarantees full rank and bounded condition number of the reconstruction matrix for aliased frequency fibers. This yields the optimal worst-case convergence rate in weighted Korobov spaces. Extending the same framework through the tent transformation produces a strict projection equivalence that establishes optimal L2 and L_infty approximation orders in the half-period cosine space.

What carries the argument

The adaptive hybrid construction that applies the Chinese Remainder Theorem and Weil bound to select shifts and algebraically ensure full rank plus bounded condition number of the reconstruction matrix for aliased frequencies.

If this is right

  • The method supplies a deterministic, stable meshless spectral solver for high-dimensional boundary-value problems such as the Poisson equation with Neumann boundary conditions.
  • Optimal approximation orders hold simultaneously in both the periodic Korobov setting and the non-periodic half-period cosine setting.
  • Sampling complexity is reduced by an order of magnitude relative to randomized baselines while preserving absolute deterministic stability.
  • The same algebraic guarantees apply uniformly across dimensions without requiring pre-computation of the shift set.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The algebraic matrix guarantees could be reused to construct deterministic solvers for other linear PDEs whose solutions lie in similar weighted spaces.
  • Numerical verification on concrete high-dimensional test problems with known exact solutions would directly confirm the claimed reduction in sampling cost.
  • The projection equivalence between Korobov and cosine spaces may suggest analogous reductions for other transformations that map periodic to non-periodic domains.

Load-bearing premise

The Chinese Remainder Theorem and Weil bound together always produce a reconstruction matrix with full rank and bounded condition number for the chosen shifts and frequency sets.

What would settle it

A concrete counterexample in which the reconstruction matrix becomes singular or its condition number grows unbounded with increasing dimension for some admissible set of shifts would show that the optimal rate guarantee fails.

Figures

Figures reproduced from arXiv: 2604.01146 by Jiarui Du, Josef Dick.

Figure 1
Figure 1. Figure 1: The total number of shifts S evaluated across different strategies. efficient polynomial strategy (Spoly < 30), the adaptive framework Sadap completely bypasses this massive geometric penalty. High-Dimensional Regime (d = 50): Driven by extreme threshold shrinkage, the single￾lattice strategy mathematically stabilizes at remarkably small primes, maintaining an empirical O((log2 N) 2 ) trajectory even at N … view at source ↗
Figure 2
Figure 2. Figure 2: Sampling complexity and numerical stability comparison again [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Empirical growth of the required number of shifts [PITH_FULL_IMAGE:figures/full_fig_p026_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The L2 and L∞ errors for the periodic test function f1 across dimensions d = 2 and d = 4. 27 [PITH_FULL_IMAGE:figures/full_fig_p027_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The required number of shifts S for the meshless PDE solver across dimensions d = 2 and d = 4. algebraic structure of aliased frequency fibers, we introduced a uniform shift strategy. Coupled with an adaptive hybrid construction algorithm driven by the Chinese Remainder Theorem and the Weil bound, this approach structurally eliminates the reliance on probabilistic oversampling and massive pre-computed base… view at source ↗
Figure 6
Figure 6. Figure 6: The relative L2 convergence of the proposed deterministic multiple-shift spectral solver for the non-periodic Neumann problem (α = 1.5). 30 [PITH_FULL_IMAGE:figures/full_fig_p030_6.png] view at source ↗
read the original abstract

Approximating multivariate periodic functions in weighted Korobov spaces via rank-1 lattices is fundamentally limited by frequency aliasing. Existing optimal-rate methods rely on randomized constructions or large pre-computations. We propose a fully deterministic multiple-shift lattice algorithm without pre-computation. First, we develop a simplified multiple shift framework for aliased frequency fibers that reduces sampling costs. Second, leveraging the Chinese Remainder Theorem and the Weil bound, we introduce an adaptive hybrid construction that algebraically guarantees the full rank and bounded condition number of the reconstruction matrix. We rigorously prove that this deterministic method maintains the optimal convergence rate in the worst-case setting. Furthermore, we extend this framework to non-periodic, half-period cosine spaces via the tent transformation. By establishing a strict projection equivalence, we prove that the algorithm attains optimal $L_2$ and $L_\infty$ approximation orders in the half-period cosine space, successfully resolving an open theoretical problem posed by Suryanarayana et al. (2016). This mathematically also validates the proposed algorithm as a generic meshless spectral solver for high-dimensional boundary value problems, such as the Poisson equation with Neumann conditions. Numerical experiments corroborate the theoretical bounds, demonstrating an order-of-magnitude reduction in sampling complexity over probabilistic baselines while ensuring absolute deterministic stability.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript introduces a deterministic multiple-shift lattice algorithm for approximating multivariate periodic functions in weighted Korobov spaces. It develops a simplified multiple-shift framework for aliased frequency fibers and uses an adaptive hybrid construction based on the Chinese Remainder Theorem and Weil bound to guarantee full rank and bounded condition numbers of the reconstruction matrices without pre-computation. The paper proves that this yields optimal worst-case convergence rates, extends the method to half-period cosine spaces via the tent transformation with a strict projection equivalence, and resolves an open problem from Suryanarayana et al. (2016). Numerical experiments are presented to corroborate the rates and show reduced sampling complexity relative to probabilistic baselines.

Significance. If the conditioning bounds and optimality proofs hold, the work would represent a meaningful advance in deterministic quasi-Monte Carlo approximation by removing reliance on randomization or large pre-computations while preserving optimal rates. The extension to cosine spaces and the claimed validation for meshless spectral methods in high-dimensional PDEs (e.g., Neumann Poisson) would further broaden its impact in numerical analysis.

major comments (1)
  1. [Adaptive hybrid construction (CRT and Weil bound)] In the adaptive hybrid construction section, the argument that the Weil bound on individual character sums (combined via CRT) algebraically guarantees a reconstruction-matrix condition number bounded independently of the number of shifts is not fully substantiated. The Weil estimate controls single sums but does not automatically bound the collective operator norm once cross-shift terms are assembled; an explicit estimate of the inverse norm that remains uniform in the number of shifts is required to support the claimed optimal worst-case error constant.
minor comments (2)
  1. The abstract states an 'order-of-magnitude reduction in sampling complexity'; the numerical section should report the precise observed ratios (with respect to dimension and number of shifts) rather than a qualitative descriptor.
  2. Notation for the aliased frequency fibers and the multiple-shift reconstruction matrix should be introduced with a single consistent definition early in the paper to improve readability of the subsequent proofs.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed and constructive report. We respond to the major comment as follows.

read point-by-point responses

  1. Referee: In the adaptive hybrid construction section, the argument that the Weil bound on individual character sums (combined via CRT) algebraically guarantees a reconstruction-matrix condition number bounded independently of the number of shifts is not fully substantiated. The Weil estimate controls single sums but does not automatically bound the collective operator norm once cross-shift terms are assembled; an explicit estimate of the inverse norm that remains uniform in the number of shifts is required to support the claimed optimal worst-case error constant.

    Authors: We agree with the referee that while the CRT ensures full rank and the Weil bound controls the individual character sums, the manuscript does not provide an explicit derivation of a uniform bound on the inverse operator norm of the assembled reconstruction matrix that is independent of the number of shifts. This observation is correct and strengthens the rigor of the optimality claim. In the revised manuscript we will add a dedicated lemma in the adaptive hybrid construction section that derives this bound explicitly, showing that the condition number remains O(1) with respect to the number of shifts by controlling the cross terms via the algebraic structure of the CRT decomposition. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation uses external CRT and Weil bound without self-referential reduction

full rationale

The paper's core construction applies the Chinese Remainder Theorem and Weil bound as external algebraic tools to guarantee full rank and shift-independent condition number for the hybrid reconstruction matrix on aliased fibers. These steps are presented as direct consequences of standard number-theoretic results rather than parameters fitted or defined inside the paper. The optimality proof in the worst-case setting and the resolution of the Suryanarayana et al. (2016) open problem are claimed via rigorous derivation from these external facts plus the tent transformation projection equivalence for cosine spaces. No equation or claim reduces by construction to a self-defined quantity, fitted input renamed as prediction, or load-bearing self-citation chain. The derivation chain remains independent of the paper's own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard number-theoretic results (Chinese Remainder Theorem and Weil bound) applied to lattice constructions; no free parameters, ad-hoc axioms, or new postulated entities are introduced in the abstract.

axioms (2)
  • standard math Chinese Remainder Theorem applies directly to the adaptive hybrid lattice construction for frequency fibers
    Invoked to guarantee algebraic properties of the reconstruction matrix.
  • standard math Weil bound supplies the necessary estimates for rank and condition number
    Used to prove bounded condition number without pre-computation.

pith-pipeline@v0.9.0 · 5533 in / 1303 out tokens · 38653 ms · 2026-05-13T22:05:40.961336+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    Tight error bounds for rank-1 lattice sampling in spaces of hybrid mixed smoothness

    Glenn Byrenheid, Lutz K¨ ammerer, Tino Ullrich, and Toni Volkmer. Tight error bounds for rank-1 lattice sampling in spaces of hybrid mixed smoothness. Numer. Math., 136(4):993–1034, 2017

    work page 2017

  2. [2]

    A lattice algorithm with mult iple shifts for function approximation in Korobov spaces

    Mou Cai, Josef Dick, and Takashi Goda. A lattice algorithm with mult iple shifts for function approximation in Korobov spaces. arXiv preprint arXiv:2511.09071 , 2025

    work page arXiv 2025

  3. [3]

    A note on approximation in weighted Ko robov spaces via multiple rank-1 lattices

    Mou Cai and Takashi Goda. A note on approximation in weighted Ko robov spaces via multiple rank-1 lattices. arXiv preprint arXiv:2601.20290 , 2026

    work page arXiv 2026

  4. [4]

    L2-approximation using randomized lattice algorithms

    Mou Cai, Takashi Goda, and Yoshihito Kazashi. L2-approximation using randomized lattice algorithms. arXiv preprint arXiv:2409.18757 , 2024

    work page arXiv 2024

  5. [5]

    Kuo, Dirk Nuyens, and Gowri Suryanar ayana

    Ronald Cools, Frances Y. Kuo, Dirk Nuyens, and Gowri Suryanar ayana. Tent-transformed lattice rules for integration and approximation of multivariate non-p eriodic functions. J. Com- plexity, 36:166–181, 2016

    work page 2016

  6. [6]

    Lattice Rules: Numerical Integration, Approximation, and Discrepancy

    Josef Dick, Peter Kritzer, and Friedrich Pillichshammer. Lattice Rules: Numerical Integration, Approximation, and Discrepancy . Springer Nature, 2022

    work page 2022

  7. [7]

    Lattice rule s for nonperiodic smooth integrands

    Josef Dick, Dirk Nuyens, and Friedrich Pillichshammer. Lattice rule s for nonperiodic smooth integrands. Numer. Math. , 126(2):259–291, 2014

    work page 2014

  8. [8]

    Iwen, Lutz K¨ ammerer, and Toni Volkmer

    Craig Gross, Mark A. Iwen, Lutz K¨ ammerer, and Toni Volkmer. A deterministic algorithm for constructing multiple rank-1 lattices of near-optimal size. Adv. Comput. Math. , 47(6):86, 2021

    work page 2021

  9. [9]

    An Introduction to the Theory of Num- bers

    Godfrey Harold Hardy and Edward Maitland Wright. An Introduction to the Theory of Num- bers. Oxford University Press, 1979

    work page 1979

  10. [10]

    Reconstructing hyperbolic cross trigonometric polynomials by sampling along rank-1 lattices

    Lutz K¨ ammerer. Reconstructing hyperbolic cross trigonometric polynomials by sampling along rank-1 lattices. SIAM J. Numer. Anal. , 51(5):2773–2796, 2013

    work page 2013

  11. [11]

    Multiple rank-1 lattices as sampling schemes fo r multivariate trigonometric polynomials

    Lutz K¨ ammerer. Multiple rank-1 lattices as sampling schemes fo r multivariate trigonometric polynomials. J. Fourier Anal. Appl. , 24(1):17–44, 2018

    work page 2018

  12. [12]

    Approximation of multivariate periodic func- tions by trigonometric polynomials based on rank-1 lattice sampling

    Lutz K¨ ammerer, Daniel Potts, and Toni Volkmer. Approximation of multivariate periodic func- tions by trigonometric polynomials based on rank-1 lattice sampling. J. Complexity, 31(4):543– 576, 2015

    work page 2015

  13. [13]

    Approximation of multivariat e periodic functions based on sampling along multiple rank-1 lattices

    Lutz K¨ ammerer and Toni Volkmer. Approximation of multivariat e periodic functions based on sampling along multiple rank-1 lattices. J. Approx. Theory , 246:1–27, 2019

    work page 2019

  14. [14]

    Kuo, Giovanni Migliorati, Fabio Nobile, and Dirk Nuyens

    Frances Y. Kuo, Giovanni Migliorati, Fabio Nobile, and Dirk Nuyens . Function integration, reconstruction and approximation using rank-1 lattices. Math. Comp. , 90(330):1861–1897, 2021

    work page 2021

  15. [15]

    Kuo, Ian H

    Frances Y. Kuo, Ian H. Sloan, and Henryk Wo´ zniakowski. Latt ice rules for multivariate ap- proximation in the worst case setting. In Monte Carlo and Quasi-Monte Carlo Methods 2004 , pages 289–330. Springer, 2006. 31

    work page 2004

  16. [16]

    Hickernell

    Dong Li and Fred J. Hickernell. Trigonometric spectral collocat ion methods on lattices. Con- temp. Math. , 330:121–132, 2003

    work page 2003

  17. [17]

    Multidimensional pseudo-s pectral methods on lattice grids

    Hans Munthe-Kaas and Tor Sørevik. Multidimensional pseudo-s pectral methods on lattice grids. Appl. Numer. Math. , 62(3):155–165, 2012

    work page 2012

  18. [18]

    Fast algorithms for component-b y-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces

    Dirk Nuyens and Ronald Cools. Fast algorithms for component-b y-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces. Math. Comp. , 75(254):903–920, 2006

    work page 2006

  19. [19]

    Universal L2-approximation using median lattice algorithms

    Zexin Pan, Takashi Goda, and Peter Kritzer. Universal L2-approximation using median lattice algorithms. arXiv preprint arXiv:2509.24582 , 2025

    work page arXiv 2025

  20. [20]

    L2-approximation using median lattice algo- rithms

    Zexin Pan, Peter Kritzer, and Takashi Goda. L2-approximation using median lattice algo- rithms. arXiv preprint arXiv:2501.15331 , 2025

    work page arXiv 2025

  21. [21]

    Barkley Rosser and Lowell Schoenfeld

    J. Barkley Rosser and Lowell Schoenfeld. Approximate formula s for some functions of prime numbers. Illinois J. Math. , 6(1):64–94, 1962

    work page 1962

  22. [22]

    Computational Science and Engineering

    Gilbert Strang. Computational Science and Engineering . Wellesley-Cambridge Press, 2007

    work page 2007

  23. [23]

    Recons truction and collocation of a class of non-periodic functions by sampling along tent-transforme d rank-1 lattices

    Gowri Suryanarayana, Dirk Nuyens, and Ronald Cools. Recons truction and collocation of a class of non-periodic functions by sampling along tent-transforme d rank-1 lattices. J. Fourier Anal. Appl. , 22(1):187–214, 2016

    work page 2016

  24. [24]

    Joel A. Tropp. User-friendly tail bounds for sums of random m atrices. Found. Comput. Math. , 12(4):389–434, 2012. 32

    work page 2012