Let $Q^n := \{0,1\}^n$ be the Hamming cube with the Hamming metric. (Recall that the Hamming is defined by the distance $d(x,y) := \# \{ i : x_i \neq y_i \}$. For integers $0 \leq k \leq n$, define a sphere $S_k$ (in the Hamming cube) as the set $\{ x \in Q^n : d(x,0) = k \}$. For each $x \in Q^n$ and each $k$, use this to define the corresponding spherical average: $$A_kf(x) := \frac{1}{\#S_k} \sum_{y \in S_k} f(x-y)$$ where $f : Q^n \to \mathbb{R}$ is a real-valued function on the Hamming cube. Moreover for such a function $f$ define the spherical maximal function $$Mf(x) := \sup_{0 \leq k \leq n} |A_kf(x)|.$$

Note that the union bound implies that $M$ is bounded on $\ell^p(Q^n)$ to itself for all $n \in \mathbb{N}$ and $1 \leq p \leq \infty$ since $A_k$ is a contraction on each of these spaces. (One may take the bound to be $n+1$ in all these cases.) Interestingly, Harrow--Kolla--Schulman (HKS) proved that $M$ is bounded on $\ell^2(Q^n) \to \ell^2(Q^n)$ with a bound independent of $n$. Their proof uses the boolean analogue of several standard techniques in harmonic analysis such as smoothing the operators, using a square function to control the difference and comparing to a semigroup for which we know the maximal function bounds.

Question 1: Is there a combinatorial proof of HKS's theorem that avoids the use of Fourier analysis (e.g. Krawtchouk polynomials)?

Question 2: Is there a combinatorial proof or HKS's theorem which uses only the spherical averages and does not introduce a smoothed spherical average?

Remark: This is a similar question to my previous one asking for a combinatorial proof of Bourgain's maximal function along the squares. And like there, I am happy with a such a proof of the restricted $L^2$ inequality.

  • 1
    $\begingroup$ My definition of the sphere $S_k$ is centered at 0, so I believe I stated it correctly. However, one could center the sphere at $x$ and then $f(y)$ would appear in the definition of $A_kf(x)$. $\endgroup$ – K Hughes Jun 18 '18 at 13:38

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.