Uniform estimates for Delannoy numbers and dimension-free estimates for discrete maximal functions over cross-polytopes

1. Problem Statement

The paper addresses two interconnected problems in discrete harmonic analysis and combinatorics:

1. Asymptotic Behavior of Delannoy Numbers: Delannoy numbers $D(d, n)$ count the number of lattice paths from $(0,0)$ to $(d,n)$ using steps North, East, or Northeast. Equivalently, $D(d, n)$ represents the number of integer lattice points in a $d$-dimensional $\ell_1$ ball (cross-polytope) of radius $n$, denoted $|B^d_n \cap \mathbb{Z}^d|$. While asymptotics are known for specific regimes (e.g., $n \approx d$ or $n \gg d$), there was a lack of uniform estimates covering all relationships between dimension $d$ and radius $n$, particularly regarding the transition between "small radius" and "large radius" behaviors.
2. Dimension-Free Maximal Estimates: The authors aim to prove dimension-free $L^p$ bounds for discrete maximal functions defined over these cross-polytopes. Specifically, they seek to establish bounds for the operator:
   $$M^d_R f(x) = \frac{1}{|B^d_R \cap \mathbb{Z}^d|} \sum_{y \in B^d_R \cap \mathbb{Z}^d} f(x-y)$$
   that hold uniformly for all dimensions $d \in \mathbb{N}$ and various ranges of radii $R$. This is a discrete analogue of the continuous Hardy-Littlewood maximal theorem, which is known to be dimension-free for convex bodies, but the discrete case is significantly more difficult.

2. Methodology

The authors employ a multi-faceted approach combining complex analysis, probability theory, and harmonic analysis:

• Complex Analysis (Saddle Point Method):
  To derive uniform estimates for $D(d, n)$, the authors utilize the generating function for the sequence. They express the lattice point count as a complex contour integral:
  $$|B^d_n \cap \mathbb{Z}^d| = \frac{1}{2\pi i} \oint_{\Gamma_s} \frac{(h(z))^d}{1-z} \frac{dz}{z^{n+1}}$$
  where $h(z) = \frac{1+z}{1-z}$. They apply the saddle point method to analyze this integral. A key innovation is the explicit identification of the saddle point $r$ (dependent on the ratio $\alpha = n/d$) and the rigorous control of the error terms to obtain estimates valid for the entire range $n \le d$.

• Probabilistic Arguments (Central Limit Theorem):
  For the large-radius regime ($R \gtrsim d^{3/2}$), the authors partition the cross-polytope based on the number of zero coordinates. They utilize the Central Limit Theorem to show that the discrete lattice points approximate the continuous volume of the ball sufficiently well, allowing them to transfer bounds from the continuous setting to the discrete setting.

• Combinatorial Concentration and Fourier Analysis:
  For small radii ($R \lesssim d^{1-\epsilon}$) and dyadic radii, the proofs rely on:

  • Concentration of Measure: Showing that most lattice points in the cross-polytope have coordinates concentrated in a specific range (e.g., small integers).
  • Comparison with Continuous/Discrete Models: Using a comparison principle to relate the discrete maximal function to known dimension-free bounds for multiparameter combinatorial maximal functions.
  • Multiplier Analysis: Analyzing the Fourier multipliers of the averaging operators to establish decay properties necessary for $L^p$ bounds.

3. Key Contributions and Results

A. Uniform Estimates for Delannoy Numbers

The paper provides a unified asymptotic formula for $D(d, n)$ that is valid for all $d, n$.

• Main Theorem (1.4): For $n \le d$, the number of lattice points is asymptotically equivalent to:
  $$D(d, n) \approx \left( \frac{1+r}{1-r} \right)^d r^{-n} \frac{1}{\sqrt{n}}$$
  where $r = \frac{\sqrt{1+\alpha^2}-1}{\alpha}$ and $\alpha = n/d$.
• Regime Transitions:
  • Small Radius ($n \ll d$): The count is dominated by the boundary of the cross-polytope and behaves like $2^n \binom{d}{n}$.
  • Large Radius ($n \gg d$): The count behaves like the Lebesgue volume of the ball, $\text{Vol}(B^d_n)$, with a specific exponential correction factor.
  • Intermediate: The formula smoothly interpolates between these behaviors.
• Significance: This resolves the ambiguity of "when" the transition occurs and provides a single formula applicable across all scales, which is crucial for the subsequent maximal function estimates.

B. Dimension-Free Maximal Function Estimates

The authors prove dimension-free $L^p(\mathbb{Z}^d)$ bounds for the maximal function $M^d_*$ in three distinct regimes:

1. Large Radii ($R \ge c d^{3/2}$):

   • Result: $\| M^d_{*, [cd^{3/2}, \infty)} f \|_{\ell^p} \le C(p) \|f\|_{\ell^p}$ for $p \in (1, \infty)$.
   • Improvement: Previous results required $R \ge d^2$. The authors improve this to $d^{3/2}$ by leveraging the specific geometry of the $\ell_1$ ball and the Central Limit Theorem. They argue that $d^{3/2}$ is likely the optimal threshold for this method.

2. Small Radii ($R \le d^{1-\epsilon}$):

   • Result: $\| S^d_{*, (0, d^{1-\epsilon}]} f \|_{\ell^p} \le C(\epsilon) \|f\|_{\ell^p}$ for $p \in [2, \infty)$, where $S^d$ denotes the spherical (boundary) maximal function.
   • Method: This relies on the concentration of lattice points near the "corners" of the cross-polytope and comparison with multiparameter maximal functions.

3. Dyadic Radii:

   • Result: $\| M^d_{*, \mathcal{D}} f \|_{\ell^p} \le C \|f\|_{\ell^p}$ for all $p \in [2, \infty)$, where $\mathcal{D} = \{2^k : k \in \mathbb{N}\}$.
   • Method: This extends previous work by the second author, utilizing the uniform estimates of Delannoy numbers to control the "isotropic constant" of the discrete cross-polytope.

4. Significance and Impact

• Unification of Discrete and Continuous Analysis: The paper bridges the gap between the continuous Hardy-Littlewood maximal theorem (which is dimension-free) and the discrete case. It demonstrates that for $\ell_1$ balls, dimension-free estimates are achievable in the discrete setting, provided the radius is either sufficiently large or sufficiently small.
• Refinement of Asymptotic Theory: The uniform estimate for Delannoy numbers is a significant combinatorial result in its own right, providing a precise tool for analyzing lattice points in high-dimensional convex bodies.
• Progress Toward the Full Conjecture: The full dimension-free bound for all radii and all $p \in (1, \infty)$ remains an open conjecture in the discrete setting. This paper provides substantial partial progress by covering the extreme regimes (very small and very large radii) and the dyadic case, narrowing the gap for the intermediate regime.
• Methodological Innovation: The explicit use of the saddle point method to derive uniform bounds for $n \le d$ and the subsequent application of these bounds to maximal operator theory sets a new standard for analyzing discrete maximal functions over non-Euclidean balls.

In summary, the paper successfully establishes that the discrete maximal operator over cross-polytopes behaves dimension-freely in specific regimes, driven by a deep and uniform understanding of the underlying lattice point counting problem (Delannoy numbers).