Linear programming bound for Hamming spaces

Consider the Hamming space \(Q^n\) and let \(C \subseteq Q^n\) be a code. Suppose \(\varphi \in H\) is any function where \(H = \mathop{\mathrm{Maps}}(Q^n, \mathbb{C})\) such that

\(\varphi(x) \le 0\) whenever \(w(x) \ge d\),
\(\mathcal{F}(\varphi)(0) = | Q^n| = q^n\),
\(\mathcal{F}(\varphi) \ge 0\),

then \(|C| \le \varphi(0)\), whenever \(C \subset Q^n\) is a code with \(d(C) \ge d\).

Recall the Fourier transform \(\mathcal{F}\). To prove this, we see that whenever \(x-y \in C\), \(x = y\) or \(d(x,y) \ge d \Rightarrow \varphi(x-y) \le 0\). Put \(g= \mathbb{I}_C * \mathbb{I}_{-C}\). Then \[\begin{align} |C| \varphi(0) \ge \sum_{x \in C}^{} \sum_{ y \in C}^{} \varphi(x-y) &= \sum_{z \in Q^n }^{} \#\{ (x,y )\in C \times C \ | \ x-y=z)\} \ \varphi(z) \\ & = \sum_{z \in Q^n}^{} g(z) \varphi(z) \\ & = \langle g , \varphi \rangle_U\\ &= |Q^n|^{-1} \langle \mathcal{F}(g) , \mathcal{F}(\varphi) \rangle_U \\ & \ge q^{-n} \mathcal{F}(g)(0) \mathcal{F}(\varphi)(0) \ge |C|^{2}. \end{align}\]

By averaging over symmetries of the Hamming space \(Q^n\), without loss of generality we can assume \(\varphi\) to be radial.

Kravchuk polynomial version

(LP Bound)

Suppose \(C \subset Q^n\) is a code such \(d(C)\ge d\). Let \(\beta(x) = 1+ \sum_{k=1}^{n} y_k K_k (x)\) be a polynomial such that \(y_k \ge 0\) for every \(k\) but \(\beta(j) \le 0\) for \(j=d, d+1,\dots ,n\). With this setting, we have that \(|C| \le \beta(0)\).

To recover the Kravchuk polynomial version of this theorem, simply put \(\varphi = \mathcal{F}(\alpha)\) and use that \(\mathcal{F}\circ\mathcal{F}(\alpha)(x) = |Q^n| \alpha(-x)\).