Higher-Order Delsarte Dual LPs:
Lifting, Constructions and Completeness

A central and longstanding open problem in coding theory is the rate-vs-distance tradeoff for binary error-correcting codes. Roughly speaking, it asks for every $\delta \in (0,1/2)$, what is the largest exponent $R_2(\delta )$ such that there is a distance $\delta n$ error-correcting code of size $2^{R_2(\delta )\cdot n}$? Despite many decades of effort, the best upper and lower bounds on the rate $R_2(\delta )$ are still far apart, implying that we do not understand the exponential growth rate of optimal binary codes.

Convex programming is not only fundamental to algorithm design but it can also be employed to study combinatorial and mathematical structures. The best known upper bounds on $R_2(\delta )$ come from the analysis of convex programming relaxations. In a seminal work, Delsarte [11] showed how to set up linear program relaxations for the maximum possible size of an error-correcting code. The Delsarte LPs have unfolded into a far-reaching theory leading, for instance, to the best known upper bounds on $R_2(\delta )$ [21], to breakthroughs in sphere packing [6, 27, 7], and to improved bounds on packings and codes in other types of geometric spaces [18, 1, 2, 3].

The success of convex relaxations is sometimes limited by an integrality gap between their optimum and the true value of the combinatorial problem. For error-correcting codes, it is known that the value of the Delsarte LP is exponentially far from the Gilbert–Varshamov lower bound [24]. If the true size of an optimal binary code is actually near the Gilbert–Varshamov bound (as conjectured by some specialists [15, 14]), then this family of relaxations needs to be substantially strengthened.

Given this context, stronger convex relaxations might be imperative to tighten the upper bounds. In principle, powerful semi-definite programming (SDP) tools such as the Sum-of-Squares hierarchy [16] can be applied to this problem [17]. However, asymptotic analysis of these SDP-based relaxations remains elusive even for the simplest cases [26], and only numerical results are known for small constant values of blocklength [13].

To appreciate the difficulty of asymptotically analyzing convex relaxations, recall that the goal is to construct a feasible dual solution which upper bounds the primal objective value. Typically, this requires an explicit construction and analysis. This is a different goal from typical uses of convex programming in algorithm design, where the starting point of the analysis is a solution returned by a convex programming solver. There, one does not need to know the precise structure of the optimum but only the property that it is (near) optimum.

Recently, hierarchies of linear programs extending the Delsarte LPs were proposed for the important case of linear codes [8, 20]. We refer to them informally as “higher-order Delsarte LPs”. The idea behind them is to strengthen the Delsarte LPs with additional natural constraints which nonetheless might be simple enough to theoretically analyze. In fact, these hierarchies were shown to converge to the true size of the code [8, 9], namely, they are complete. Besides being LPs instead of SDPs, these hierarchies bear strong similarities with Delsarte LPs for which we now have various theoretical analyses and a richer set of techniques [21, 12, 22, 3, 4, 23, 25, 19, 5].

Constructing dual solutions for the higher-order Delsarte LPs can lead to a breakthrough in the rate-versus-distance problem. Nonetheless, the higher-order structure of these LPs may still require substantial effort to be understood and analyzed. In this work, our main goal is to substantially increase our understanding of the structure of the higher-order Delsarte LP hierarchies by establishing three new results about their dual formulations.

Before we present our results, we first recall these LPs with an informal and intuitive description (see Section 3 for more details). The Delsarte LP (used in the first LP bound) has a variable intended to count the number of codewords of each Hamming weight. The higher-order Delsarte LPs form a hierarchy with a level parameter $\mathrm{\ell }\in \mathbb{N}$. There is a variable intended to count the number of $\mathrm{\ell }$-tuples of codewords with every possible Hamming weight configuration of a subspace of dimension $\mathrm{\ell }$. For example, for $\mathrm{\ell }=2$, essentially there is a variable for each $(a,b,c)\in {\{0,1,\mathrm{\dots },n\}}^3$ which is intended to be the number of pairs of codewords $(x,y)$ such that $(|x|,|y|,|x+y|)=(a,b,c)$.

The set of non-negative integers is denoted by $\mathbb{N}$ and the set of positive integers is denoted by ${\mathbb{N}}_{+}\stackrel{\text{def}}{=}\mathbb{N}\setminus \{0\}$. For $n\in \mathbb{N}$, we let $[n]\stackrel{\text{def}}{=}\{1,\mathrm{\dots },n\}$. We also let ${ℝ}_{+}$ be the set of non-negative reals.

For $q,n\in \mathbb{N}$, we denote the $n$th geometric sum of ratio $q$ by

We extend the notation above to when $n\le 0$ in the natural way so that ${\sum }_{j=a}^{a-1}{c}_j=0$ and ${\sum }_{j=a}^b{c}_j=-{\sum }_{j=b+1}^{a-1}{c}_j$.

Given further $k\in \mathbb{Z}$, we denote the $q$-Gaussian falling factorial of $n$ by $k$, the $q$-Gaussian factorial and the $q$-Gaussian binomial of $n$ by $k$ by

respectively. When $k\le 0$, products should be interpreted in the usual fashion so that ${\prod }_{j=a}^{a-1}{c}_j=1$ and ${\prod }_{j=a}^b{c}_j={\prod }_{j=b+1}^{a-1}{c}_j^{-1}$. We will omit $q$ from the notation when $q=1$, so that the above match the usual falling factorial, factorial and binomial, respectively.

For a set $V$ and $k\in \mathbb{Z}$, we denote by $\left(\genfrac{}{}{0pt}{}{V}{k}\right)$ the set of all subsets of $V$ of size $k$ (so $|\left(\genfrac{}{}{0pt}{}{V}{k}\right)|=\left(\genfrac{}{}{0pt}{}{|V|}{k}\right)$ when $V$ is finite).

For a prime power $q\in \mathbb{N}$, we denote by ${𝔽}_q$ the field with $q$ elements and for $x\in {𝔽}_q^n$, we denote by $|x|\stackrel{\text{def}}{=}|\mathrm{supp}(x)|$ the Hamming weight of $x$. For an ${𝔽}_q$-vector space $V$, we denote by $L_{{𝔽}_q}(V)$ the set of all ${𝔽}_q$-linear subspaces of $V$ and we denote by ${\mathrm{GL}}_{\mathrm{\ell }}({𝔽}_q)$ the general linear group of degree $\mathrm{\ell }$ over ${𝔽}_q$ (i.e., the group of non-singular $\mathrm{\ell }\times \mathrm{\ell }$ matrices over ${𝔽}_q$). For a matrix $X$, we denote by $X_i$ the $i$th row of $X$ and by $X_{i_1,\mathrm{\dots },i_t}$ the matrix obtained by restricting $X$ to the rows indexed by $i_1,\mathrm{\dots },i_t$.

A distance-$d$ code is a code $C\subseteq {𝔽}_q^n$ such that $|x-y|\ge d$ for all $x,y\in C$ with $x\ne y$. We denote by $A_q(n,d)$ the size of the largest distance-$d$ code in ${𝔽}_q^n$ and by $A_q^{\mathrm{Lin}}(n,d)$ the size of the largest distance-$d$ code in ${𝔽}_q^n$ that is also a subspace of ${𝔽}_q^n$.

Both hierarchies of [8, 20] can be used to upper bound sizes of linear codes in an arbitrary set of “valid” linear codes ${\mathrm{Valid}}_n\subseteq L_{{𝔽}_q}({𝔽}_q^n)$. In the prototypical cases, ${\mathrm{Valid}}_n$ is the set of all linear codes of distance at least $d$, or the set of all $ϵ$-balanced codes. Once ${\mathrm{Valid}}_n$ is fixed, at level $\mathrm{\ell }\in {\mathbb{N}}_{+}$ the hierarchies make use of the set

The easiest way of stating the hierarchy of [8] at level $\mathrm{\ell }$ is as the Lovász ${\vartheta }^{\prime }$ of the graph $G_{n,\mathrm{\ell }}$ over the vertex set ${𝔽}_q^{\mathrm{\ell }\times n}$ in which $X,Y\in {𝔽}_q^{\mathrm{\ell }\times n}$ are adjacent exactly when $X-Y\notin {\mathrm{Valid}}_{n,\mathrm{\ell }}$. If $C\in {\mathrm{Valid}}_n$, then the set $\{X\in {𝔽}_q^{\mathrm{\ell }\times n}\mid X_1,\mathrm{\dots },X_{\mathrm{\ell }}\in C\}$ is an independent set in $G_{n,\mathrm{\ell }}$ of size exactly ${|C|}^{\mathrm{\ell }}$, which is upper bounded by ${\vartheta }^{\prime }(G_{n,\mathrm{\ell }})$, giving us the first formulation of the hierarchy of (1).

It turns out that the SDP arising in the Lovász ${\vartheta }^{\prime }$ function can be explicitly diagonalized, leading to a linear program. By noting that there is a natural “global translation” action of ${𝔽}_q^n$ on the space ${𝔽}_q^{\mathrm{\ell }\times n}$ given by

and that the program (1) of ${\vartheta }^{\prime }(G_{n,\mathrm{\ell }})$ is ${𝔽}_q^n$-symmetric, every feasible solution can be symmetrized under this action without violating its feasibility or changing its value. Furthermore, ${𝔽}_q^n$-symmetric solutions are simultaneously diagonalizable and the positive semidefinite constraint is then encoded by the Fourier transform given by

This yields the linear program (2) below, whose dual is (3) and that first appeared in [8]. A linear code $C\in {\mathrm{Valid}}_n$ yields a natural solution $f_C$ of (2) given by $f_C(X)\stackrel{\text{def}}{=}\mathrm{𝟙}[X_1,\mathrm{\dots },X_{\mathrm{\ell }}\in C]$, whose value is ${|C|}^{\mathrm{\ell }}$. Note that when $q$ is a power of $2$, due to $X=-X$, the symmetry constraints in the primal are automatically enforced and we can therefore remove $\beta$ from the dual.

Finally, we introduce the Partial Fourier Hierarchy of [20]. This hierarchy follows from the observation that the natural solutions $f_C(X)\stackrel{\text{def}}{=}\mathrm{𝟙}[X_1,\mathrm{\dots },X_{\mathrm{\ell }}\in C]$ to (2) not only have non-negative Fourier transforms, but in fact have non-negative “partial Fourier transforms” defined as follows.

First, we note that ${\mathrm{GL}}_{\mathrm{\ell }}({𝔽}_q)$ also acts on ${𝔽}_q^{\mathrm{\ell }\times n}$ by left-multiplication, which in turn induces a right-action of ${\mathrm{GL}}_{\mathrm{\ell }}({𝔽}_q)$ on the set of functions ${𝔽}_q^{\mathrm{\ell }\times n}\to ℂ$ given by $(f\cdot M)(X)\stackrel{\text{def}}{=}f(M\cdot X)$. Then for $X,Y\in {𝔽}_q^{\mathrm{\ell }\times n}$, $k\in \{0,1,\mathrm{\dots },n\}$ and $M\in {\mathrm{GL}}_{\mathrm{\ell }}({𝔽}_q)$, we let

where ${\chi }_y(x)\stackrel{\text{def}}{=}\exp ({\sum }_{j\in [n]}2\pi i{y}_j{x}_j/q)$ is the usual character and we let

for every $f:{𝔽}_q^{\mathrm{\ell }\times n}\to ℂ$. A straightforward calculation then yields

where $R_k$ is the diagonal matrix whose diagonal consists of $k$ entries $-1$ followed by $\mathrm{\ell }-k$ entries $1$.

Noting that for every $C\in L_{{𝔽}_q}({𝔽}_q^n)$ the function $f_C(X)\stackrel{\text{def}}{=}\mathrm{𝟙}[X_1,\mathrm{\dots },X_{\mathrm{\ell }}\in C]$ satisfies ${ℱ}_{k,M}(f_C)\ge 0$ ($k\in [\mathrm{\ell }]$, $M\in {\mathrm{GL}}_{\mathrm{\ell }}({𝔽}_q)$), it follows that we can add further constraints to (2) to obtain a stronger hierarchy,²²2In fact, [20] only includes partial Fouriers with $M=I$, but explicitly requires solutions to be ${\mathrm{GL}}_{\mathrm{\ell }}({𝔽}_q)$-symmetric; here we opt for this formulation which can be shown to be equivalent straightforwardly. called the partial Fourier hierarchy [20], formulated in (5) and whose rather technical dual (7) is deferred to Section 4. We will show in Lemma 8 that the dual of (5) is further equivalent to the simpler (6) below.

In this section we show that dual solutions lift. That is, from a solution $h$ at a level $k$ of value $V_h$, we can construct a natural solution at any level $\mathrm{\ell }$ divisible by $k$ with value $V_h^{\mathrm{\ell }/k}$. Let us point out that in terms of values, it was already known from [8, Corollary 6.6] that the value of the hierarchy (2) at level $\mathrm{\ell }$ was at most the $\mathrm{\ell }/k$th power of its value at level $k$ (provided $k$ divides $\mathrm{\ell }$); the main contribution of this section is an explicit lift of dual solutions and the analogous result for the partial Fourier hierarchy (5), which does not immediately follow from the results of [8].

We will now give a new proof that the hierarchy is complete, i.e., it recovers the true size of a code at level $\mathrm{\ell }\ge n$. For this proof, we recall yet another formulation of the hierarchy from [9].

Instead of symmetrizing (2) under the action of $S_n$, we recall that ${\mathrm{GL}}_{\mathrm{\ell }}({𝔽}_q)$ also acts on ${𝔽}_q^{\mathrm{\ell }\times n}$ by left-multiplication and observe that (2) is also ${\mathrm{GL}}_{\mathrm{\ell }}({𝔽}_q)$-symmetric. Inspired by terminology from Sum-of-Squares algorithms, given a ${\mathrm{GL}}_{\mathrm{\ell }}({𝔽}_q)$-symmetric solution $f$, for each $S\in L_{{𝔽}_q}({𝔽}_q^n)$, we define the notation

for any $X\in {𝔽}_q^{\mathrm{\ell }\times n}$ with $\mathrm{span}(\{X_1,\mathrm{\dots },X_{\mathrm{\ell }}\})=S$ and interpret this as a pseudo-probability that a pseudo-random variable $\stackrel{\mathbf{~}}{𝑪}$ over $L_{{𝔽}_q}({𝔽}_q^n)$ contains $S$. Computing the pseudo-probabilities $\tilde{\mathbb{P}}[S]\stackrel{\text{def}}{=}\tilde{\mathbb{P}}[S=\stackrel{\mathbf{~}}{𝑪}]$ amounts to a Möbius inversion on the poset $L_{{𝔽}_q}({𝔽}_q^n)$ under the inclusion partial order. At levels $\mathrm{\ell }\ge n$ and when ${\mathrm{Valid}}_n$ is closed under taking subspaces³³3It is possible to make this Möbius inversion at lower levels and without the closure under subspaces assumption, but it yields more complicated constraints. Since our completeness result will only hold for levels $\mathrm{\ell }\ge n$ anyway, we opt for the simpler formulation instead., this yields the formulation in (8), whose dual is (9); a code $C\in {\mathrm{Valid}}_n$ yields a solution ${\tilde{\mathbb{P}}}_C[S]\stackrel{\text{def}}{=}\mathrm{𝟙}[S=C]$ of (8), whose value is ${|C|}^{\mathrm{\ell }}$. The first completeness at levels $\mathrm{\ell }\ge n$ of [9] was based on the primal formulation (8) and crucially relied on the fact that non-negative solutions to (8) are convex combinations of true solutions.

It will also be convenient to define for every $k\in \mathbb{N}$ the set

It is clear that for any ${\mathrm{Valid}}_n\subseteq L_{{𝔽}_q}({𝔽}_q^n)$ non-empty, if $k\stackrel{\text{def}}{=}\max \{{dim}_{{𝔽}_q}(S)\mid S\in {\mathrm{Valid}}_n\}$, then ${\mathrm{Valid}}_n\subseteq {\mathrm{Valid}}_n^{dim\le k}$. We will show completeness of (9) for valid sets of the form ${\mathrm{Valid}}_n^{dim\le k}$ ($k\in \mathbb{N}$) and leverage this to show completeness for arbitrary non-empty valid sets ${\mathrm{Valid}}_n\subseteq L_{{𝔽}_q}({𝔽}_q^n)$ that are closed under taking subspaces. We start with the following key observation.