# A combinatorial proof of the Harrow--Kolla--Schulman theorem

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.

• 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)$. Jun 18, 2018 at 13:38