# New LP-based Upper Bounds in the Rate-vs.-Distance Problem for Linear Codes

Elyassaf Loyfer School of Computer Science and Engineering, Hebrew University,
91904 Jerusalem, Israel. Supported in part by grant 659/18 “High-dimensional
combinatorics” of the Israel Science Foundation. Nati Linial11footnotemark: 1

###### Abstract

We develop a new family of linear programs, that yield upper bounds on the
rate of codes of given distance. Our bounds apply only to linear codes.
Delsarte’s LP is the weakest member of this family and our LP yields
increasingly tighter upper bounds on the rate as its control parameter
increases. Numerical experiments show significant improvement compared to
Delsarte. These convincing numerical results, and the large variety of tools
available for asymptotic analysis, give us hope that our work will lead to new
improved asymptotic upper bounds on the possible rate of linear codes.

##  1 Introduction

The rate vs. distance problem is a fundamental question in coding theory.
Namely, we seek the largest possible rate of a code of given minimal distance.
The best lower bound that we have is due to Gilbert [1] (for general codes)
and Varshamov [2] (in the linear case) and is attained by random codes. The
best upper bound that we have is due to MRRW [3], often called the linear
programming bound, since it is based on Delsarte’s linear program [4]. There
is substantial empirical evidence [5] indicating that the MRRW bound may be
asymptotically all that Delsarte’s LP yields.

We propose a new family of linear programs, which greatly strengthen
Delsarte’s LP. We stress that these new LPs apply only to linear codes. They
come with a control parameter, an integer $r$. For $r=1$ our LP coincides with
Delsarte’s, and as $r$ increases the LP yields tighter upper bounds on the
code’s rate, at the cost of higher complexity. Numerical experiments (fig. 1)
show that even with $r=2$ our LP is far stronger than Delsarte’s, surpassing
it in almost all instances. The improved upper bound on the code’s size is up
to $2.5$ times smaller than what Delsarte gives. Moreover, in all instances
where Delsarte’s upper bound is known not to be tight, we improve it.

$15$$20$$25$$30$$0$$0.5$$1$$1.5$Delsarte$\text{{{DelsarteLin}}}(2,n,d)$[6]
with $l=2$

(a) $d=6$

$16$$18$$20$$22$$24$$26$$28$$30$$0$$0.5$$1$$1.5$$2$

(b) $d=8$

$20$$22$$24$$26$$28$$30$$32$$0$$1$$2$

(c) $d=10$

$24$$26$$28$$30$$32$$34$$36$$0$$0.5$$1$$1.5$$2$$2.5$

(d) $d=12$

$28$$30$$32$$34$$36$$38$$0$$0.5$$1$$1.5$$2$$2.5$

(e) $d=14$

$32$$34$$36$$38$$40$$0$$0.5$$1$$1.5$$2$

(f) $d=16$

Figure 1:  Numerical results comparing Delsarte’s LP, DelsarteLin (our LP with
$r=2$), and the currently best known bounds, as reported in [7]. Each line is
the ratio between the optimal value of the corresponding LP and the best known
bound on the size of a linear code of length $n$ and distance $d$, scaled by
$\log_{2}(\cdot)$. The $x$-axis in each plot varies over $n$. Experimental
setup, as well as more detailed results, are given in section 7.2.

Our construction is based on the elementary fact that a linear code is closed
under addition. Combined with Delsarte’s LP this simple fact has considerable
consequences. To actually derive them we use (i) The language of of Boolean
Fourier analysis (ii) Symmetry that is inherent in the problem. In analyzing
Delsarte’s LP, symmetrization reduces the problem size from exponential to
polynomial in $n$, and brings Krawtchouk polynomials to the fore. Also here
does symmetrization yield a dramatic reduction in size and reveals the role of
multivariate Krawtchouk polynomials. There is a large body of work on these
high-dimensional counterparts of univariate Krawtchouks, e.g., [8, 9].

Although we are still unable to reach our main goal and derive better
asymptotic bounds, there is good reason for hope. There are several different
approaches to the proof of the MRRW bound, each using a different set of
tools. These include, properties of Krawtchouk polynomials [3], analysis of
Boolean functions (e.g., [10, 11, 12, 13]), and spectral [14] as well as
functional [15] analysis. We believe that it is a viable and promising
direction to extend proofs of the MRRW bound to our multivariate LP family. We
are hopeful that this will lead to stronger bounds on the rate of linear
codes.

A concurrent work [6] employs closely related ideas to produce a family of
linear programs, which upper bound the size of linear codes. Remarkably, they
prove that the value of their program converges to the tight bound as the
control parameter grows. For a numerical comparison between our LP and that of
[6], see figure 1 and appendix 7.2. These improved bounds stem from several
new conceptual ideas that we introduce here, as explained below.

The rest of the work is organized as follows. Section 2 provides preliminaries
and notation. In section 3 we develop our new LP family, prove its strength,
examine its components, and suggest some variations that may be more
convenient for asymptotic analysis. In section 4 we derive the symmetrized LP.
Section 5 includes properties of a new linear operator that is useful for our
LPs. Section 6 connects our construction to the multivariate Krawtchouk
polynomials. Appendix 7.2 shows results from numerical experiments on a wide
range of parameters.

##  2 Notation and Preliminaries

###  2.1 General

We denote by $\mathbb{N}$ the set non-negative integers. For a positive
integer $r$, $[r]\coloneqq\\{1,2,\dots,r\\}$. Vectors are distinguished from
scalars by boldface letters, e.g.
$\bm{x}=(x_{1},x_{2},\dots,x_{n})\in\mathbb{R}^{n}$.

We consider two linear programs equivalent if their respective optimal values
are equal. Likewise, relations between LPs, e.g. ”$=$”,”$\leq$”, refer to
optimal values. We denote by $\operatorname{val}(\cdot)$ the optimal value of
an LP.

###  2.2 The Boolean Hypercube

The $n$-dimensional Boolean hypercube, or simply _the cube_ is, as usual, the
linear space $\mathbb{F}_{2}^{n}$ or the set $\\{0,1\\}^{n}$. An element, or a
vector, in the cube is denoted in bold, e.g.
$\bm{x}=(x_{1},\dots,x_{n})\in\\{0,1\\}^{n}$. Addition
$\bm{x}+\bm{y}\in\\{0,1\\}^{n}$ is bitwise ”xor”, or element-wise sum modulo
$2$. Inner product between vectors in the cube is done over $\mathbb{F}_{2}$:
$\langle\bm{x},\bm{y}\rangle=\sum_{i=1}^{n}x_{i}y_{i}\bmod 2$.

Let $f,g:\\{0,1\\}^{n}\to\mathbb{R}$ be two real functions on the cube. Their
inner product of is defined as

$\langle f,g\rangle=2^{-n}\sum_{\bm{x}\in\\{0,1\\}^{n}}f(\bm{x})g(\bm{x})$

and their convolution

$(f*g)(\bm{x})=2^{-n}\sum_{\bm{y}\in\\{0,1\\}^{n}}f(\bm{y})g(\bm{x}+\bm{y})$

The tensor product of $f$ and $g$ is a function on $\\{0,1\\}^{2n}$:

$(f\otimes g)(\bm{x},\bm{y})=f(\bm{x})g(\bm{y}).$

The Hamming weight of $\bm{x}$, denoted $|\bm{x}|$, is the number of non-zero
bits, $|\bm{x}|=|\\{1\leq i\leq n:x_{i}\neq 0\\}|$. For $i=0,\dots,n$, the
$i$-th _level-set_ is the set of all Boolean vectors of weight $i$. The
indicator of the $i$-th level-set is called $L_{i}$:

$L_{i}(\bm{x})=\begin{cases}1&|\bm{x}|=i\\\
0&\text{o/w}\end{cases},\quad\bm{x}\in\\{0,1\\}^{n}$

We denote Kronecker’s delta function by $\delta_{\bm{x}}(\bm{y})$.

The _Fourier character_ corresponding to $\bm{x}\in\\{0,1\\}^{n}$, denoted
$\chi_{\bm{x}}$, is defined by

$\chi_{\bm{x}}({\bm{y}})=(-1)^{\langle{\bm{x}},{\bm{y}}\rangle},\quad{\bm{y}}\in\\{0,1\\}^{n}.$

The set of characters $\\{\chi_{\bm{x}}\\}_{{\bm{x}}\in\\{0,1\\}^{n}}$ is an
orthonormal basis for the space of real functions on the cube. The Fourier
transform of a function $f:\\{0,1\\}^{n}\to\mathbb{R}$ is its projection over
the characters, $\hat{f}({\bm{x}})=\langle
f,\chi_{\bm{x}}\rangle=2^{-n}\sum_{\bm{y}}\chi_{\bm{x}}({\bm{y}})f({\bm{y}})$.
In Fourier space, the inner product is not normalized:
$\langle\hat{f},\hat{g}\rangle_{\mathcal{F}}=\sum_{\bm{x}}\hat{f}({\bm{x}})\hat{g}({\bm{x}})$.

We recall Parseval’s identity: $\langle
f,g\rangle=\langle\hat{f},\hat{g}\rangle$; and the convolution theorem:
$(f*g)({\bm{x}})=\hat{f}({\bm{x}})\hat{g}({\bm{x}})$.

The partial Fourier transform, denoted $\mathcal{F}_{S}$ that we introduce
here plays an important role in our work, see section 3 for details.

A comprehensive survey of harmonic analysis of Boolean functions can be found
in [16].

###  2.3 Codes

A _binary code_ of length $n$ is a subset $\mathcal{C}\subset\\{0,1\\}^{n}$.
Its _distance_ is the smallest Hamming distance between pairs of words,
$dist(\mathcal{C})=\min_{{\bm{x}},{\bm{y}}\in\mathcal{C}}|{\bm{x}}+{\bm{y}}|$.
The largest cardinality of a code of length $n$ and distance $d$ is denoted by
$A(n,d)$. The _rate_ of $\mathcal{C}$ is defined as

$R(\mathcal{C})=n^{-1}\log_{2}(|\mathcal{C}|)$

The asymptotic rate-vs.-distance problem is to find, for every
$\delta\in(0,1/2)$,

$\mathcal{R}(\delta)=\limsup_{n\to\infty}\\{R(\mathcal{C}):\mathcal{C}\subset\\{0,1\\}^{n},~{}dist(\mathcal{C})\geq\delta
n\\}$

A linear code is a linear subspace. In the binary case,
$\mathcal{C}\subset\\{0,1\\}^{n}$ is linear if and only if
${\bm{x}},{\bm{y}}\in\mathcal{C}\Rightarrow{\bm{x}}+{\bm{y}}\in\mathcal{C}$,
for every ${\bm{x}},{\bm{y}}\in\\{0,1\\}^{n}$. Consequently, in a linear code
$dist(\mathcal{C})=\min_{{\bm{0}\neq\bm{x}}\in\mathcal{C}}|{\bm{x}}|$.

##  3 New Linear Programs

We start by recalling Delsarte’s LP over the cube.

######  Definition 1.

$\text{{{Delsarte}}}_{cube}(n,d)$ is the following linear program:

$\displaystyle\underset{{f:\\{0,1\\}^{n}\to\mathbb{R}}}{\operatorname{\textup{maximize}}}\quad\sum_{\bm{x}\in\\{0,1\\}^{n}}f(\bm{x})$
($obj$) $\displaystyle\operatorname{\textup{subject~{}to:}}$
$\displaystyle\quad f(0)=1,$ ($d1$) $\displaystyle\quad f\geq 0,~{}\hat{f}\geq
0,$ ($d2$) $\displaystyle\quad f(\bm{x})=0\quad\text{{if} }1\leq|\bm{x}|\leq
d-1$ ($d3$)

It is well known that the optimal value of $\text{{{Delsarte}}}_{cube}(n,d)$
is an upper bound on $A(n,d)$. Let us recall the proof. Let $\mathcal{C}$ be a
code of length $n$ and minimal distance $d$, and let
$\mathbf{1}_{\mathcal{C}}:\\{0,1\\}^{n}\to\\{0,1\\}$ be its indicator
function. Namely, $\mathbf{1}_{\mathcal{C}}(\bm{x})=1$ if
$\bm{x}\in\mathcal{C}$ and $0$ otherwise. Observe that
$f_{\mathcal{C}}=\frac{1}{|\mathcal{C}|}\mathbf{1}_{\mathcal{C}}*\mathbf{1}_{\mathcal{C}}$
is a feasible solution to $\text{{{Delsarte}}}_{cube}(n,d)$ with value
$|\mathcal{C}|$. Hence the optimum of $\text{{{Delsarte}}}_{cube}(n,d)$ is an
upper bound on $|\mathcal{C}|$.

For $\mathcal{C}$ a linear code, there holds, moreover, that
$\mathbf{1}_{\mathcal{C}}(\bm{x})\mathbf{1}_{\mathcal{C}}(\bm{y})=\mathbf{1}_{\mathcal{C}}(\bm{x})\mathbf{1}_{\mathcal{C}}(\bm{x}+\bm{y}),$
and consequently,

$f_{\mathcal{C}}=\frac{1}{|\mathcal{C}|}\mathbf{1}_{\mathcal{C}}*\mathbf{1}_{\mathcal{C}}=\mathbf{1}_{\mathcal{C}}.$

This implies a new set of constraints which hold for linear codes:

$f(\bm{x})f(\bm{y})=f(\bm{x})f(\bm{x}+\bm{y})$

However, these constraints are not linear in $f$, nor even convex.

Therefore, we consider instead tensor products of $f_{\mathcal{C}}$. Let
$r\geq 1$ be an integer and define

$f_{\mathcal{C}^{r}}=f_{\mathcal{C}}\otimes\dots\otimes
f_{\mathcal{C}}:\\{0,1\\}^{rn}\to\mathbb{R}.$

Based on linear properties of $f_{\mathcal{C}^{r}}$, we construct a new linear
program which is stronger than Delsarte’s, and its optimal value is an upper
bound on the size of linear codes. We turn to give the details.

######  Definition 2.

$\text{{{DelsarteLin}}}(r,n,d)$:

$\displaystyle\underset{f:\\{0,1\\}^{rn}\to\mathbb{R}}{\operatorname{\textup{maximize}}}\quad\sum_{\bm{x}\in\\{0,1\\}^{n}}f(\bm{x},0,\dots,0)$
($Obj$) $\displaystyle\operatorname{\textup{subject~{}to:}}$
$\displaystyle\quad f(\mathbf{0})=1$ ($C1$)
$\displaystyle\quad\mathcal{F}_{S}(f)\geq 0\quad\forall S\subset[r]$ ($C2$)
$\displaystyle\quad f(\bm{x}_{1},\dots,\bm{x}_{r})=0\quad\text{if
}1\leq|\bm{x}_{1}|\leq d-1$ ($C3$) $\displaystyle\quad f(X)=f(TX)\quad
T\in\text{{GL}}(r,2),~{}X\in\\{0,1\\}^{r\times n}$ ($C4$)

Here, $\mathcal{F}_{S}(f)$ is the partial Fourier transform that we define
below. Also, $\text{{GL}}(r,2)$ is the general linear group over
$\mathbb{F}_{2}$. Note also the parallels between conditions ($d1$), ($d2$),
($d3$) resp. ($C1$), ($C2$), ($C3$)

The function $f$ is defined on the $rn$-dimensional cube. We will view its
argument as either a concatenation of $r$ vectors in $\\{0,1\\}^{n}$, or an
$r\times n$ matrix obtained by stacking the $r$ vectors. For example, we write
$f(X)=f(\bm{x}_{1},\dots,\bm{x}_{r})$ where
$\bm{x}_{1},\dots,\bm{x}_{r}\in\\{0,1\\}^{n}$ are the rows of the matrix
$X\in\\{0,1\\}^{r\times n}$. This viewpoint becomes even more useful in
section 4, where the columns of $X$, and not just its rows come into play.

We turn to define the partial Fourier transform $\mathcal{F}_{S}(f)$, which is
a linear operator on Boolean functions. Namely, we apply a Fourier Transform
to some of the $r$ components of the product.

######  Definition 3.

Let $S\subset[r]$ and $\bm{x}_{1},\dots,\bm{x}_{r}\in\\{0,1\\}^{n}$. The
partial Fourier character $\Psi^{S}_{(\bm{x}_{1},\dots,\bm{x}_{r})}$ is
defined by

$\Psi^{S}_{(\bm{x}_{1},\dots,\bm{x}_{r})}\coloneqq\psi^{(1)}_{\bm{x}_{1}}\otimes\psi^{(2)}_{\bm{x}_{2}}\otimes\dots\otimes\psi^{(r)}_{\bm{x}_{r}}$

where, given $\bm{x}\in\\{0,1\\}^{n}$,

$\psi^{(i)}_{\bm{x}}\coloneqq\begin{cases}\chi_{\bm{x}}&i\in S\\\
\delta_{\bm{x}}&\text{o/w}\end{cases}$

$\chi_{\bm{x}}$ is a Fourier character in $\\{0,1\\}^{n}$ and
$\delta_{\bm{x}}$ is Kronecker’s delta.

The partial Fourier transform is the linear projection of a function
$g:\\{0,1\\}^{rn}\to\mathbb{R}$ on the partial characters,

$\mathcal{F}_{S}(g)(\bm{x}_{1},\dots,\bm{x}_{r})=2^{(r-|S|)n}\langle
g,\Psi^{S}_{(\bm{x}_{1},\dots,\bm{x}_{r})}\rangle=2^{-|S|n}\sum
g(\bm{y}_{1},\dots,\bm{y}_{r})\times\\\ \quad\times\prod_{i\in
S}\chi_{\bm{x}_{i}}(\bm{y}_{i})\prod_{i\in[r]\setminus
S}\delta_{\bm{x}_{i}}(\bm{y}_{i})$

the sum running over all $\bm{y}_{1},\dots,\bm{y}_{r}\in\\{0,1\\}^{n}$.

Observe that $\mathcal{F}_{\emptyset}(g)=g$, $\mathcal{F}_{[r]}(g)=\hat{g}$,
and
$\mathcal{F}_{\\{i,j\\}}(g)=\mathcal{F}_{\\{i\\}}(\mathcal{F}_{\\{j\\}}(g))$,
for $1\leq i,j\leq r$, $i\neq j$.

######  Theorem 1.

Let $r,n,d$ be positive integers such that $d\leq n/2$.

  1. 1.

For every binary linear code $\mathcal{C}$ with length $n$ and distance $d$,
$|\mathcal{C}|\leq\operatorname{val}\text{{{DelsarteLin}}}(r,n,d)$

  2. 2.

$\operatorname{val}\text{{{DelsarteLin}}}(r+1,n,d)\leq\operatorname{val}\text{{{DelsarteLin}}}(r,n,d)$

  3. 3.

$\operatorname{val}\text{{{DelsarteLin}}}(1,n,d)=\operatorname{val}\text{{{Delsarte}}}_{cube}(n,d)$

We make a few comments before we turn to the proof. Already for $r=2$, and in
most instances, DelsarteLin is significantly stronger than Delsarte’s. For
more on this, see figure 1 and section 7.2. We also note that DelsarteLin
without ($C4$) yields exactly the bounds as Delsarte’s LP.

###### Proof.

  1. 1.

We show that $f_{\mathcal{C}^{r}}=f_{\mathcal{C}}\otimes\dots\otimes
f_{\mathcal{C}}$ is a feasible solution to $\text{{{DelsarteLin}}}(r,n,d)$
with value $|\mathcal{C}|$. We use the fact that $f_{\mathcal{C}}$ is a
feasible solution to $\text{{{Delsarte}}}_{cube}(n,d)$ with value
$|\mathcal{C}|$.

For the objective,

$\sum_{\bm{x}\in\\{0,1\\}^{n}}f(\bm{x},\bm{0},\dots,\bm{0})=\sum_{\bm{x}}f_{\mathcal{C}}(\bm{x})\prod_{i=2}^{r}f_{\mathcal{C}}(\bm{0})=\sum_{\bm{x}}f_{\mathcal{C}}(\bm{x})=|\mathcal{C}|$

For ($C1$),

$f_{\mathcal{C}^{r}}(\bm{0},\dots,\bm{0})=(f_{\mathcal{C}}(\bm{0}))^{r}=1$

because $f_{\mathcal{C}}$ satisfies ($d1$).

For ($C3$),

$f_{\mathcal{C}^{r}}(\bm{x}_{1},\dots,\bm{x}_{r})=\prod_{i=1}^{r}f_{\mathcal{C}}(\bm{x}_{i})$

and if $1\leq|\bm{x}_{1}|\leq d-1$ then $f_{\mathcal{C}}(\bm{x}_{1})=0$.

For ($C2$), observe that

$\mathcal{F}_{S}(f_{\mathcal{C}^{r}})(\bm{x}_{1},\dots,\bm{x}_{r})=\prod_{i\in
S}\hat{f}_{\mathcal{C}}(\bm{x}_{i})\prod_{i\in[r]\setminus
S}f_{\mathcal{C}}(\bm{x}_{i})$

which is non-negative because $f_{\mathcal{C}},\hat{f}_{\mathcal{C}}\geq 0$.
Note that the linearity of $\mathcal{C}$ has not entered the discussion so
far.

For ($C4$), the linearity of $\mathcal{C}$ implies,
$f_{\mathcal{C}}=\frac{1}{|\mathcal{C}|}\mathbf{1}_{\mathcal{C}}*\mathbf{1}_{\mathcal{C}}=\mathbf{1}_{\mathcal{C}}$.
If $\bm{x}_{1},\dots,\bm{x}_{r}\in\mathcal{C}$, then every linear combination
of these vectors is also in $\mathcal{C}$. Hence

$f_{\mathcal{C}^{r}}(X)=\prod_{\bm{x}\in
rowspan(X)}\mathbf{1}_{\mathcal{C}}(\bm{x})$

If $T\in\\{0,1\\}^{r\times r}$ is invertible, the row spaces of $TX$ and $X$
coincide.

  2. 2.

Let $f:\\{0,1\\}^{(r+1)n}\to\mathbb{R}$ be a feasible solution to
$\text{{{DelsarteLin}}}(r+1,n,d)$. We construct a feasible solution to
$\text{{{DelsarteLin}}}(r,n,d)$ with value at least $\operatorname{val}(f)$.

Let

$g:\\{0,1\\}^{rn}\to\mathbb{R},\quad
g(\bm{x}_{1},\dots,\bm{x}_{r})=f(\bm{x}_{1},\dots,\bm{x}_{r},\bm{0})$

It is easy to verify that $g$ is feasible for $\text{{{DelsarteLin}}}(r,n,d)$,
and it is clear that $\operatorname{val}(g)=\operatorname{val}(f)$.

  3. 3.

Obvious, because $\text{{{DelsarteLin}}}(1,n,d)$ and
$\text{{{Delsarte}}}_{cube}(n,d)$ are identical.

∎

In the rest of this section we examine the strength and consequences of some
components of DelsarteLin. A pleasing observation is that DelsarteLin captures
duality, a key feature of linear codes. We also discuss two modifications that
may be helpful in the search for asymptotic results.

###  3.1 On the significance of ($C4$)

An obvious consequence of ($C4$) is that ($C3$) is equivalent to

$f(X)=0~{}\text{if }1\leq|\bm{u}^{\intercal}X|\leq d-1\text{ for some
}\bm{u}\in\\{0,1\\}^{r}$

$\\{\bm{u}^{\intercal}X\\}_{\bm{u}\in\\{0,1\\}^{r}}$ is the row span of $X$.
Similarly, ($C4$) renders the objective ($Obj$) equivalent to

$\operatorname{\textup{maximize}}\quad(2^{r}-1)^{-1}\sum_{0\neq\bm{u}\in\\{0,1\\}^{r}}\sum_{\bm{x}\in\\{0,1\\}^{n}}f(u_{1}\cdot\bm{x},\dots,u_{r}\cdot\bm{x})$

It is less obvious, however, that ($C4$) is equivalent to a constraint that
involves the dual code, which we now derive.

It is well known that for $\mathcal{C}$ linear,
$\hat{\mathbf{1}}_{\mathcal{C}}=\frac{1}{|\mathcal{C}^{\perp}|}\mathbf{1}_{\mathcal{C}^{\perp}}$
(see e.g., [16], proposition 3.11). If
$f_{\mathcal{C}^{r}}=f_{\mathcal{C}}\otimes\dots\otimes f_{\mathcal{C}}$ as we
defined earlier, then

$\mathcal{F}_{S}(f_{\mathcal{C}^{r}})(\bm{x}_{1},\dots,\bm{x}_{r})=\prod_{i\in
S}\frac{1}{|\mathcal{C}^{\perp}|}\mathbf{1}_{\mathcal{C}^{\perp}}(\bm{x}_{i})\prod_{i\notin
S}\mathbf{1}_{\mathcal{C}}(\bm{x}_{i})$

If $\langle\bm{x},\bm{y}\rangle=1\bmod 2$ for some
$\bm{x},\bm{y}\in\\{0,1\\}^{n}$, then a consequence of duality is
$\mathbf{1}_{\mathcal{C}^{\perp}}(\bm{x})\mathbf{1}_{\mathcal{C}}(\bm{y})=0$.
Hence $f_{\mathcal{C}^{r}}$ satisfies the following constraint:

$\mathcal{F}_{S}(f)(\bm{x}_{1},\dots,\bm{x}_{r})=0\text{ if
}\langle\bm{x}_{i},\bm{x}_{j}\rangle=1\bmod 2\\\ \text{ for some }i\in
S,~{}j\notin S$

We prove the equivalence between ($C4$) and (3.1) below, in lemma 1.

To numerically test the significance of ($C4$), we removed it but kept its
immediate consequences. Namely, we replaced ($Obj$) and ($C3$) with (3.1) and
(3.1). A sample from our numerical experiments is shown in figure 2. It
confirms that this change does weaken the LP, though not significantly.
However, we only experimented with $r=2$, and it is possible that for larger
values of $r$ the difference becomes more substantial.

| r | 1 | 2 | 2
---|---|---|---|---
n | d | Delsarte | DelsarteLin | ${\eqref{eq:delsarte_lin:objective_span},\eqref{eq:delsarte_lin:C3_span},\cancel{\eqref{eq:delsarte_lin:C4}}}$
16 | 4 | 2048 | 2048 | 2048
| 6 | 256 | 131.72 | 156.44
| 8 | 32 | 32 | 32
17 | 4 | 3640.89 | 3072.96 | 3075
| 6 | 425.56 | 256 | 264.88
| 8 | 50.72 | 32 | 32.31
Figure 2:  Numerical experiments on the signifcance of ($C4$). The first
column is Delsarte’s LP. The second column is $\text{{{DelsarteLin}}}(2,n,d)$.
The third column is a modification of $\text{{{DelsarteLin}}}(2,n,d)$, where
($C3$) is replaced by (3.1); the objective function is replaced by (3.1); and
($C4$) is removed.

Lastly, ($C4$) implies other symmetries for $\mathcal{F}_{S}(f)$. While these
do not strengthen the LP, they provide an exponential in $r$ reduction in the
number of constraints. For proof, see lemma 1.

$\mathcal{F}_{S}(f)(X)=\mathcal{F}_{S}(f)(T_{1}T_{2}X),$

for every $T_{1},T_{2}\in\text{{GL}}(r,2)$, such that
$T_{1}e_{i}=e_{i}~{}\forall i\in S$ and $T_{2}e_{i}=e_{i}~{}\forall
i\in[r]\setminus S$.

$\mathcal{F}_{S}(f)(\bm{x}_{1},\dots,\bm{x}_{r})=\mathcal{F}_{\pi^{-1}(S)}(f)(\bm{x}_{\pi(1)},\dots,\bm{x}_{\pi(r)}),$

for every $\pi\in\mathfrak{S}_{r}$ – permutation on $r$ elements.

###  3.2 On the significance of ($C2$)

A weaker, simpler LP is obtained from $\text{{{DelsarteLin}}}(r,n,d)$ by
replacing ($C2$) with

$f\geq 0,~{}\hat{f}\geq 0$

The modified LP is still stronger than Delsarte’s LP, and its strength
increases with $r$, as we prove in theorem 2. Its simplicity might make it
more suitable for asymptotic analysis.

We observed empirically that this modification greatly weakens the LP. A small
sample is given here in figure 3, and more can be found in section 7.2.

| r | 1 | 2 | 2 | 3
---|---|---|---|---|---
n | d | Delsarte | ($C2$) | (3.2) | (3.2)
13 | 6 | 40 | 24.26 | 32 | 23.07
30 | 8 | 114816 | 71094.5 | 107044 | -
30 | 10 | 12525.4 | 5928.52 | 11340.4 | -
30 | 12 | 1131.79 | 582.09 | 1026.28 | -
30 | 14 | 129.68 | 80.08 | 112 | -
Figure 3: Comparison between ($C2$), (3.2) and Delsarte. Each column shows the
optimal value a of different LP. The LPs from left to right: Delsarte’s LP;
Our LP with $r=2$; Our modified LP with (3.2) instead of ($C2$), with $r=2$;
and again the modified LP, with $r=3$.

######  Theorem 2.

Let $r,n,d$ be positive integers such that $d\leq n/2$. For every binary
linear code $\mathcal{C}$ with length $n$ and distance $d$,

$|\mathcal{C}|\leq\operatorname{val}\text{{{DL}}}_{\eqref{eq:delsarte_lin:C2_weak}}(r+1,n,d)\leq\operatorname{val}\text{{{DL}}}_{\eqref{eq:delsarte_lin:C2_weak}}(r,n,d)$

where $\text{{{DL}}}_{\eqref{eq:delsarte_lin:C2_weak}}(r,n,d)$ is the variant
of $\text{{{DelsarteLin}}}(r,n,d)$ in which ($C2$) is replaced by (3.2).

###### Proof.

The first inequality follows from theorem 1, by noting that every feasible
solution to $\text{{{DelsarteLin}}}(r,n,d)$ is a feasible solution to the
modified version.

For the second inequality, let $f:\\{0,1\\}^{(r+1)n}\to\mathbb{R}$ be a
feasible solution to
$\text{{{DL}}}_{\eqref{eq:delsarte_lin:C2_weak}}(r+1,n,d)$. Define

$g:\\{0,1\\}^{rn}\to\mathbb{R},\quad
g(\bm{x}_{1},\dots,\bm{x}_{r})=f(\bm{x}_{1},\dots,\bm{x}_{r},\bm{0})$

It is obvious that $g(\bm{0})=1$; $g\geq 0$;
$g(\bm{x}_{1},\dots,\bm{x}_{r})=0$ if $1\leq|\bm{x}_{1}|\leq d-1$; and that
$g(X)=g(TX)$ for every $T\in\text{{GL}}(r,2)$. To prove that $g$ is feasible,
it remains to show that $\hat{g}\geq 0$. Observe that

$\hat{g}(\bm{x}_{1},\dots,\bm{x}_{r})=\mathcal{F}_{\\{1,\dots,r\\}}(f)(\bm{x}_{1},\dots,\bm{x}_{r},\bm{0})=2^{n}\mathcal{F}_{\\{r+1\\}}(\hat{f})(\bm{x}_{1},\dots,\bm{x}_{r},\bm{0})=\sum_{\bm{y}\in\\{0,1\\}^{n}}\chi_{\bm{0}}(\bm{y})\hat{f}(\bm{x}_{1},\dots,\bm{x}_{r},\bm{y})=\sum_{\bm{y}\in\\{0,1\\}^{n}}\hat{f}(\bm{x}_{1},\dots,\bm{x}_{r},\bm{y})$

which is non-negative since $\hat{f}\geq 0$. The value of $f$ equals the value
of $g$, which is at most
$\operatorname{val}\text{{{DL}}}_{\eqref{eq:delsarte_lin:C2_weak}}(r,n,d)$.

∎

###  3.3 On the objective function

We suggest an alternative objective function, which may prove more convenient
for asymptotic analysis:

$\operatorname{\textup{maximize}}\sum_{\bm{x}_{1},\dots,\bm{x}_{r}\in\\{0,1\\}^{n}}f(\bm{x}_{1},\dots,\bm{x}_{r})$

The function $f_{\mathcal{C}^{r}}$ from earlier is a feasible solution, and
with (3.3) its value is $|\mathcal{C}|^{r}$, hence (3.3) bounds
$|\mathcal{C}|^{r}$ instead of $|\mathcal{C}|$.

Our numerical calculations reveal rather minor differences between the two
objectives, with no consistent advantage to one over the other. See detailed
results in section 7.2.

We state:

######  Conjecture 1.

Let $r,n,d$ be positive integers such that $d\leq n/2$. Then

$\displaystyle\left(\operatorname{val}\text{{{DL}}}_{\eqref{eq:delsarte_lin:objective_r}}(r+1,n,d)\right)^{1/(r+1)}\leq\left(\operatorname{val}\text{{{DL}}}_{\eqref{eq:delsarte_lin:objective_r}}(r,n,d)\right)^{1/r}$

Here, $\text{{{DL}}}_{\eqref{eq:delsarte_lin:objective_r}}(r,n,d)$ is obtained
from $\text{{{DelsarteLin}}}(r,n,d)$ by replacing the objective function with
(3.3).

Due to the non-linear relation between the two objective functions we are
presently only able to prove the following. A similar theorem can likewise be
proved for the variant where (3.2) replaces ($C2$).

######  Theorem 3.

Let $r,n,d$ be positive integers such that $d\leq n/2$. Then

$\left(\operatorname{val}\text{{{DL}}}_{\eqref{eq:delsarte_lin:objective_r}}(r+1,n,d)\right)^{1/(r+1)}\leq\max\begin{cases}\left(\operatorname{val}\text{{{DL}}}_{\eqref{eq:delsarte_lin:objective_r}}(r,n,d)\right)^{1/r},\\\
\operatorname{val}\text{{{DelsarteLin}}}(r+1,n,d)\end{cases}$

###### Proof.

Let $f:\\{0,1\\}^{(r+1)n}\to\mathbb{R}$ be a feasible solution to
$\text{{{DL}}}_{\eqref{eq:delsarte_lin:objective_r}}(r+1,n,d)$. Then $f$ is
also a feasible solution to $\text{{{DelsarteLin}}}(r+1,n,d)$. Let

$\displaystyle v_{1}$ $\displaystyle=\left(\sum
f(\bm{x}_{1},\dots,\bm{x}_{r+1})\right)^{1/(r+1)}$ $\displaystyle v_{2}$
$\displaystyle=\sum f(\bm{x},\bm{0},\dots,\bm{0})$

where the sums are over $\bm{x}_{1},\dots,\bm{x}_{r+1}\in\\{0,1\\}^{n}$ and
over $\bm{x}\in\\{0,1\\}^{n}$, respectively.

If $v_{1}\leq v_{2}$ then we are done, because $v_{2}$ is not greater than the
optimum of $\text{{{DelsarteLin}}}(r+1,n,d)$.

Otherwise, $v_{1}>v_{2}$. Define $g:\\{0,1\\}^{rn}\to\mathbb{R}$ as

$g(\bm{x}_{1},\dots,\bm{x}_{r})=\frac{1}{v_{2}}\sum_{\bm{y}\in\\{0,1\\}^{n}}f(\bm{x}_{1},\dots,\bm{x}_{r},\bm{y})$

It is not hard to verify that $g$ is a feasible solution to
$\text{{{DL}}}_{\eqref{eq:delsarte_lin:objective_r}}(r,n,d)$. Now consider its
value:

$\left(\sum
g(\bm{x}_{1},\dots,\bm{x}_{r})\right)^{1/r}=\left(\frac{v_{1}^{r+1}}{v_{2}}\right)^{1/r}\\\
\geq v_{1}$

and the value of $g$ is at most the optimal value of
$\text{{{DL}}}_{\eqref{eq:delsarte_lin:objective_r}}(r,n,d)$. ∎

##  4 Symmetrized Linear Programs

In this section we symmetrize the LPs from section 3. This reduces the problem
size with no loss in the objective function. Here is a brief description of
the symmetrization.

Let the group $G$ act on the variables of a linear program $\mathcal{P}$. A
solution to $\mathcal{P}$ is said to be symmetric  if it is invariant under
the action of $G$, i.e., it is constant on $G$’s orbits. Let
$\mathcal{P}_{/G}$ be the restriction of $\mathcal{P}$ to symmetric solutions.
A solution to $\mathcal{P}_{/G}$ is described by a single variable for each
orbit, hence the saving in size. If $\mathcal{P}$ has a symmetric optimal
solution then we do not lose in terms of the objective function. As we show
below, this is the situation here.

We are inspired by Delsarte’s LP which is the symmetrization of
$\text{{{Delsarte}}}_{cube}(n,d)$ with respect to $\mathfrak{S}_{n}$, the
symmetric group on $n$ elements. It acts by bit permutation, namely,

$\sigma\cdot\bm{x}=(x_{\sigma(1)},\dots,x_{\sigma(n)}),$

for $\sigma\in\mathfrak{S}_{n}$ and $\bm{x}=(x_{i})\in\\{0,1\\}^{n}$.

Our LP $\text{{{DelsarteLin}}}(r,n,d)$ admits two symmetrizations. The first,
w.r.t. $\mathfrak{S}_{n}$ is identical to Delsarte’s when $r=1$. It acts by
column permutation, as we define below. The second is with respect to the
general linear group, $\text{{GL}}(r,2)$, and is not fully exploited herein.

The rest of this section is organized as follows. We first introduce the
$\mathfrak{S}_{n}$-symmetrized LP, then show how it is derived from
DelsarteLin, and finally prove their equivalence.

###  4.1 Introducing $\text{{{DelsarteLin}}}_{/\mathfrak{S}_{n}}$

The variables of $\text{{{DelsarteLin}}}_{/\mathfrak{S}_{n}}(r,n,d)$ are
indexed by the set

$\mathcal{I}_{r,n}\coloneqq\\{\bm{\alpha}=(\alpha_{0},\dots,\alpha_{2^{r}-1}):\alpha_{i}\in\mathbb{N},~{}\sum_{i=0}^{2^{r}-1}\alpha_{i}=n\\}$
(1)

Every $\bm{\alpha}\in\mathcal{I}_{r,n}$ is also considered as a real function
on $\\{0,1\\}^{r}$. Namely, $\alpha_{\bm{u}}$ is synonymous with $\alpha_{i}$,
where $\bm{u}\in\\{0,1\\}^{r}$ is the binary representatin of
$i\in\mathbb{N}$.

We will compose elements of $\mathcal{I}_{r,n}$ using indicator functions. We
denote by $\epsilon_{\bm{u}}:\\{0,1\\}^{r}\to\mathbb{R}$ the indicator of
$\bm{u}$. Namely, $\epsilon_{\bm{u}}(\bm{v})=1$ if $\bm{v}=\bm{u}$ and $0$
otherwise, for $\bm{v}\in\\{0,1\\}^{r}$. This notation is meant to distguish
between the indicators in the space $\mathbb{R}^{\\{0,1\\}^{r}}$, and the
indicators in the space $\\{0,1\\}^{r}$, which we denote by $\bm{e}_{i}$, for
$i=1,\dots,r$. We write, for example,

$\bm{\alpha}=(n-k)\epsilon_{\bm{0}}+k\epsilon_{\bm{e}_{i}}\in\mathcal{I}_{r,n}$

Here, $\bm{0},\bm{e}_{i}\in\\{0,1\\}^{r}$, and $k$ is an integer between $0$
and $n$.

We denote by $K^{S}_{\bm{\alpha}}:\mathcal{I}_{r,n}\to\mathbb{R}$ the
multivariate Krawtchouk polynomials and their partial versions, for
$S\subset[r]$ and $\bm{\alpha}\in\mathcal{I}_{r,n}$. They are the
symmetrization of $\mathcal{F}_{S}(L_{\bm{\alpha}})$, and their definition is
given below, in propositions 8 and 9.

We define the action of $\text{{GL}}(r,2)$ on $\mathcal{I}_{r,n}$ by

$(T\cdot\bm{\alpha})_{\bm{u}}=\alpha_{T^{-1}\bm{u}}$

for every $T\in\text{{GL}}(r,2)$, $\bm{\alpha}\in\mathcal{I}_{r,n}$, and
$\bm{u}\in\\{0,1\\}^{r}$.

######  Definition 4.

$\text{{{DelsarteLin}}}_{/\mathfrak{S}_{n}}(r,n,d)$:

$\displaystyle\mathrlap{\underset{{\varphi:\mathcal{I}_{r,n}\to\mathbb{R}}}{\textup{maximize}}\quad\sum_{k=0}^{n}\binom{n}{k}\varphi_{(n-k)\epsilon_{\bm{0}}+k\epsilon_{\bm{e}_{1}}}}$
($Obj_{/\mathfrak{S}_{n}}$)
$\displaystyle\operatorname{\textup{subject~{}to:}}$
$\displaystyle\quad\varphi_{n\epsilon_{\bm{0}}}=1$ ($C1_{/\mathfrak{S}_{n}}$)
$\displaystyle\quad\mathrlap{\sum_{{\bm{\alpha}}\in\mathcal{I}_{r,n}}\varphi_{\bm{\alpha}}K^{S}_{{\bm{\alpha}}}(\bm{\beta})\geq
0\quad\forall S\subset[r],~{}\bm{\beta}\in\mathcal{I}_{r,n}}$
($C2_{/\mathfrak{S}_{n}}$) $\displaystyle\quad\varphi_{\bm{\alpha}}=0$
$\displaystyle\text{if
}1\leq\frac{1}{2}(n-2^{r}\hat{\bm{\alpha}}_{\bm{e}_{1}})\leq d-1$
($C3_{/\mathfrak{S}_{n}}$)
$\displaystyle\quad\varphi_{\bm{\alpha}}=\varphi_{T\cdot{\bm{\alpha}}}$
$\displaystyle\forall T\in\text{{GL}}(r,2)$ ($C4_{/\mathfrak{S}_{n}}$)

We also mention two important variations, (3.2) and (3.3):

$\displaystyle\operatorname{\textup{maximize}}\quad\sum_{\bm{\alpha}\in\mathcal{I}_{r,n}}\varphi_{\bm{\alpha}}$
($Obj^{\prime}_{/\mathfrak{S}_{n}}$) $\displaystyle\varphi\geq
0;\quad\sum_{{\bm{\alpha}}\in\mathcal{I}_{r,n}}\varphi_{\bm{\alpha}}K_{{\bm{\alpha}}}(\bm{\beta})\geq
0\quad$ $\displaystyle\forall\bm{\beta}\in\mathcal{I}_{r,n}$
($C2^{\prime}_{/\mathfrak{S}_{n}}$)

Note that $\text{{{DelsarteLin}}}_{/\mathfrak{S}_{n}}(1,n,d)$ is identical to
Delsarte’s LP. Observe that $\mathcal{I}_{1,n}$ is isomorphic to the set
$\\{0,1,\dots,n\\}$. Rewrite the LP with a new set of variables,
$a_{k}\coloneqq\binom{n}{k}\varphi_{(n-k)\epsilon_{0}+k\epsilon_{1}}$, for
$k=0,1,\dots,n$. Using the Krawtchouk symmetry identity,
$\binom{n}{j}K_{i}(j)=\binom{n}{i}K_{j}(i)$, transform the Krawtchouk
constraint ($C2_{/\mathfrak{S}_{n}}$) as follows:

$\sum_{j=0}^{n}\binom{n}{j}^{-1}a_{j}K_{j}(i)=\binom{n}{i}^{-1}\sum_{j=0}^{n}a_{j}K_{i}(j)$

The result is Delsarte’s LP:

######  Definition 5.

$\text{{{Delsarte}}}(n,d)$:

$\displaystyle\mathrlap{\underset{a_{0},\dots,a_{n}\in\mathbb{R}}{\textup{maximize}}\quad\sum_{i=0}^{n}a_{i}}$
($obj_{/\mathfrak{S}_{n}}$)
$\displaystyle\operatorname{\textup{subject~{}to:}}$ $\displaystyle\quad
a_{0}=1$ ($d1_{/\mathfrak{S}_{n}}$) $\displaystyle\quad a_{i}\geq
0;\quad\sum_{j=0}^{n}a_{j}K_{i}(j)\geq 0,\quad 0\leq i\leq n$
($d2_{/\mathfrak{S}_{n}}$) $\displaystyle\quad a_{i}=0\quad\text{{if} }1\leq
i\leq d-1$ ($d3_{/\mathfrak{S}_{n}}$)

###  4.2 Deriving $\text{{{DelsarteLin}}}_{/\mathfrak{S}_{n}}$

As mentioned, $\mathfrak{S}_{n}$ acts on $\\{0,1\\}^{n}$ by bit permutations.
Define its action on $\\{0,1\\}^{rn}$ by

$\sigma\cdot(\bm{x}_{1},\dots,\bm{x}_{r})=(\sigma\cdot\bm{x}_{1},\dots,\sigma\cdot\bm{x}_{r})$

for $\bm{x}_{1},\dots,\bm{x}_{r}\in\\{0,1\\}^{n}$. If we view $\\{0,1\\}^{rn}$
as the space of $r\times n$ matrices, then the action of $\sigma\cdot X$ is
permutation of the columns of $X\in\\{0,1\\}^{r\times n}$.

For a function $f:\\{0,1\\}^{rn}\to\mathbb{R}$, define the action of
$\mathfrak{S}_{n}$ by

$(f\circ\sigma)(X)=f(\sigma\cdot X)$

Symmetry w.r.t. $\mathfrak{S}_{n}$ means that $f$ is constant on the orbits,
$\\{0,1\\}^{rn}/\mathfrak{S}_{n}$. Namely,

$f=\sum_{O\in\\{0,1\\}^{rn}/\mathfrak{S}_{n}}\varphi_{O}\mathbf{1}_{O}$

where $\mathbf{1}_{O}:\\{0,1\\}^{rn}\to\\{0,1\\}$ is the indicator of orbit
$O$, and $\varphi_{O}\in\mathbb{R}$, for every
$O\in\\{0,1\\}^{rn}/\mathfrak{S}_{n}$.

The set of orbits is isomorphic to the set $\mathcal{I}_{r,n}$, defined in
(1). The relation is established through the following definition.

######  Definition 6.

Let $\bm{\xi}_{1},\dots,\bm{\xi}_{n}\in\\{0,1\\}^{r}$ be the columns of
$X\in\\{0,1\\}^{r\times n}$. The column enumerator of $X$ counts how many
times each vector in $\\{0,1\\}^{r}$ appears as a column in $X$:

$\operatorname{\Gamma}_{X}\in\mathbb{N}^{2^{r}},\quad\operatorname{\Gamma}_{X}(\bm{u})=|\\{1\leq
i\leq n:\bm{\xi}_{i}=\bm{u}\\}|$

Observe that when $r=1$, $\operatorname{\Gamma}_{\bm{x}}(1)=|\bm{x}|$ and
$\operatorname{\Gamma}_{\bm{x}}(0)=n-|\bm{x}|$.

It is evident that an orbit is determined by the column enumerator of the
matrix. Namely, $\mathfrak{S}_{n}\cdot X=\mathfrak{S}_{n}\cdot
Y\iff\operatorname{\Gamma}_{X}=\operatorname{\Gamma}_{Y}$. Also, for every
$\bm{\alpha}\in\mathcal{I}_{r,n}$ there exists an $X$ with
$\operatorname{\Gamma}_{X}=\bm{\alpha}$. Therefore $\\{0,1\\}^{r\times
n}/\mathfrak{S}_{n}$ is isomorphic to $\mathcal{I}_{r,n}$.

For every ${\bm{\alpha}}\in\mathcal{I}_{r,n}$ define its level-set,

$L_{\bm{\alpha}}:\\{0,1\\}^{r\times n}\to\\{0,1\\},\quad
L_{\bm{\alpha}}(X)=\begin{cases}1&\operatorname{\Gamma}_{X}={\bm{\alpha}}\\\
0&\text{o/w}\end{cases}$

A symmetric solution to $\text{{{DelsarteLin}}}(r,n,d)$ has the from

$f=\sum_{{\bm{\alpha}}\in\mathcal{I}_{r,n}}\varphi_{\bm{\alpha}}L_{\bm{\alpha}}$

where
$\varphi=\\{\varphi_{\bm{\alpha}}\in\mathbb{R}:\bm{\alpha}\in\mathcal{I}_{r,n}\\}$.
In order to complete the derivation of
$\text{{{DelsarteLin}}}_{/\mathfrak{S}_{n}}(r,n,d)$ we need to express the
objective and constraints in terms of $\varphi$.

We start with the objective. For every $\bm{x}\in\\{0,1\\}^{n}$,

$f(\bm{x},\bm{0},\dots,\bm{0})=\varphi_{(n-|\bm{x}|)\epsilon_{\bm{0}}+|\bm{x}|\epsilon_{\bm{e}_{1}}}$

because, if $X=(\bm{x},\bm{0},\dots,\bm{0})\in\\{0,1\\}^{r\times n}$, then

$\operatorname{\Gamma}_{X}=(n-|\bm{x}|)\epsilon_{\bm{0}}+|\bm{x}|\epsilon_{\bm{e}_{1}}$

For constraint ($C1$), $f(\bm{0},\dots,\bm{0})=\varphi_{n\epsilon_{\bm{0}}}$.

For constraints ($C2$) and (3.2),

$\mathcal{F}_{S}(f)=\sum_{\bm{\alpha}\in\mathcal{I}_{r,n}}\varphi_{\bm{\alpha}}\mathcal{F}_{S}(L_{\bm{\alpha}})=\sum_{\bm{\alpha}\in\mathcal{I}_{r,n}}\varphi_{\bm{\alpha}}K^{S}_{\bm{\alpha}}$

where
$K^{S}_{\bm{\alpha}}(\operatorname{\Gamma}_{X})\coloneqq\mathcal{F}_{S}(L_{\bm{\alpha}})(X)$
for every $X\in\\{0,1\\}^{r\times n}$, $\bm{\alpha}\in\mathcal{I}_{r,n}$ and
$S\subset[r]$. Below we show that $K^{S}_{\bm{\alpha}}$ is a multivariate
Krawtchouk polynomial (if $S=[r]$) or a product of polynomials from this
family. See section 6 for details.

For constraint ($C4$), note that $\text{{GL}}(r,2)$ acts on
$\\{0,1\\}^{r\times n}$ column-wise. Thus, if
$\operatorname{\Gamma}_{X}=\bm{\alpha}$ then
$\operatorname{\Gamma}_{TX}=T\cdot\bm{\alpha}$, for every
$X\in\\{0,1\\}^{r\times n}$ and $T\in\text{{GL}}(r,2)$. The action of
$\text{{GL}}(r,2)$ on $\mathcal{I}_{r,n}$ was defined accordingly.

For constraint ($C3$) we need the following proposition, which relates
$\operatorname{\Gamma}_{X}$ to the weight of the rows of
$X\in\\{0,1\\}^{r\times n}$.

######  Proposition 1.

For every $X=(x_{i,j})\in\\{0,1\\}^{r\times n}$ and $\bm{u}\in\\{0,1\\}^{r}$,

$|\bm{u}^{\intercal}X|=\frac{1}{2}\big{(}n-2^{r}\widehat{\operatorname{\Gamma}}_{X}(\bm{u})\big{)}$

where $\widehat{\operatorname{\Gamma}}_{X}(\bm{u})$ is the Fourier transform
of $\operatorname{\Gamma}_{X}$ at $\bm{u}$.

###### Proof.

By definition, $\bm{u}^{\intercal}X\in\\{0,1\\}^{n}$ and
$|\bm{u}^{\intercal}X|=\sum_{j=1}^{n}(\bm{u}^{\intercal}X)_{j}$, where
$(\bm{u}^{\intercal}X)_{j}$ is the $j$-th bit and the sum is over the
integers. Concretely, for $j=1,\dots,n$:

$(\bm{u}^{\intercal}X)_{j}=\sum_{i:u_{i}=1}x_{i,j}\bmod
2=\frac{1}{2}\Big{(}1-(-1)^{\sum_{i:u_{i}=1}x_{i,j}}\Big{)}=\frac{1}{2}\Big{(}1-(-1)^{\langle\bm{u},\bm{\xi}_{j}\rangle}\Big{)}$

where $\bm{\xi}_{j}=(x_{i,j})_{i=1}^{r}$ is the $j$-th column of $X$. Thus

$|\bm{u}^{\intercal}X|=\frac{1}{2}\sum_{j=1}^{n}\Big{(}1-(-1)^{\langle\bm{u},\bm{\xi}_{j}\rangle}\Big{)}$

But $\bm{\xi}_{j}$ appears $\operatorname{\Gamma}_{X}(\bm{\xi}_{j})$ times in
$X$, so grouping the summands by column, we have

$|\bm{u}^{\intercal}X|=\frac{1}{2}\sum_{\bm{v}\in\\{0,1\\}^{r}}\operatorname{\Gamma}_{X}(\bm{v})(1-(-1)^{\langle\bm{u},\bm{v}\rangle})=\frac{1}{2}\big{(}n-\chi_{\bm{u}}^{\intercal}\operatorname{\Gamma}_{X}\big{)}$

∎

###  4.3 Equivalence between $\text{{{DelsarteLin}}}_{/\mathfrak{S}_{n}}$ and
DelsarteLin

######  Proposition 2.

For every positive integers $r,n,d$, such that $d\leq n/2$,

$\operatorname{val}\text{{{DelsarteLin}}}_{/\mathfrak{S}_{n}}(r,n,d)=\operatorname{val}\text{{{DelsarteLin}}}(r,n,d)$

We prove this proposition from a more general perspective.

Let the group $G$ act on the variables of a linear program $\mathcal{P}$. We
say that $\mathcal{P}$ is invariant under $G$ if $g\cdot x$ is a feasible
solution whenever $x$ is, and $\operatorname{val}(g\cdot
x)=\operatorname{val}(x)$, for every $g\in G$.

######  Proposition 3.

If $\mathcal{P}$ is invariant under $G$, then
$\operatorname{val}\mathcal{P}=\operatorname{val}\mathcal{P}_{/G}$.

###### Proof.

Every feasible solution $x$ produces a symmetric solution:

$\overline{x}\coloneqq\frac{1}{|G|}\sum_{g\in G}g\cdot x$

By linearity and invariance under $G$, $\overline{x}$ is feasible with value
$\operatorname{val}(x)$. On the other hand, every solution to
$\mathcal{P}_{/G}$ is also a solution to $\mathcal{P}$, with equal value.
Hence $\operatorname{val}\mathcal{P}=\operatorname{val}\mathcal{P}_{/G}$. ∎

######  Proposition 4.

$\text{{{DelsarteLin}}}(r,n,d)$ is invariant under $\mathfrak{S}_{n}$.

###### Proof.

Let $f:\\{0,1\\}^{rn}\to\mathbb{R}$ be a feasible solution and let
$\sigma\in\mathfrak{S}_{n}$. We show that $f\circ\sigma$ is a feasible
solution with the same value as $f$.

Clearly, $\operatorname{val}(f)=\operatorname{val}(f\circ\sigma)$, since
$\sigma$ acts on each row independently. For $\bm{0}\in\\{0,1\\}^{r\times n}$,
$\sigma\cdot\bm{0}=\bm{0}$ so $f\circ\sigma$ satisfies ($C1$). ($C2$) follows
from proposition 5, below. ($C3$) is satisfied because row weights are
preserved under column permutations. Finally, ($C4$) is satisfied by
associativity of matrix multiplication, because $\sigma$ acts on $X$ by
multiplication on the right by a permutation matrix. ∎

Proposition 2 is a consequence of Propositions 3 and 4.

##  5 On Partial Fourier Transform

In this section we explore interactions between the groups $\mathfrak{S}_{n}$
and $\text{{GL}}(r,2)$ and the partial Fourier transform. The former,
$\mathfrak{S}_{n}$ acts on $\\{0,1\\}^{r\times n}$ by permuting columns. The
latter, $\text{{GL}}(r,2)$ acts on $\\{0,1\\}^{r\times n}$ by matrix
multiplication from the left. The group of order-$r$ permutation matrices is a
subgroup of $\text{{GL}}(r,2)$ which acts on $\\{0,1\\}^{r\times n}$ by
permuting rows.

We recall our dual view of $\\{0,1\\}^{rn}$, once as a concatenation of $r$
vectors $\bm{x}_{1},\dots,\bm{x}_{r}\in\\{0,1\\}^{n}$, and once as a matrix
$X\in\\{0,1\\}^{r\times n}$ whose rows are the above vectors. If the group $G$
acts on $\\{0,1\\}^{r\times n}$, and $g\in G$, we denote $(f\circ
g)(X)=f(g\cdot X)$ for any $X\in\\{0,1\\}^{r\times n}$ and
$f:\\{0,1\\}^{rn}\to\mathbb{R}$.

The proofs for some of the following propositions appear in the appendix.

######  Proposition 5.

Let $\sigma\in\mathfrak{S}_{n}$, $X\in\\{0,1\\}^{r\times n}$, $S\subset[r]$,
and $f:\\{0,1\\}^{r\times n}\to\mathbb{R}$. Then,

$\mathcal{F}_{S}(f\circ\sigma)=\mathcal{F}_{S}(f)\circ\sigma$

######  Proposition 6.

Let $\pi\in\mathfrak{S}_{r}$ act on the set $\\{0,1\\}^{r\times n}$ by row
permutation. Let $X\in\\{0,1\\}^{r\times n}$, $S\subset[r]$, and
$f:\\{0,1\\}^{r\times n}\to\mathbb{R}$. Then,

$\mathcal{F}_{S}(f\circ\pi)=\mathcal{F}_{\pi^{-1}(S)}(f)\circ\pi$

######  Proposition 7.

Let $T\in\text{{GL}}(r,2)$ be the elementary matrix of row addition, mapping
$\bm{e}_{i}\mapsto\bm{e}_{i}+\bm{e}_{j}$, for some $i,j\in[r]$, $i\neq j$, and
$\bm{e}_{k}\mapsto\bm{e}_{k}$ for $k\neq i$, where
$\bm{e}_{k}\in\\{0,1\\}^{r}$ is the $k$-th standard basis vector. Let
$X\in\\{0,1\\}^{r\times n}$, $S\subset[r]$, and $f:\\{0,1\\}^{r\times
n}\to\mathbb{R}$. Then,

  * •

if $i,j\in S$:

$\mathcal{F}_{S}(f\circ T)=\mathcal{F}_{S}(f)\circ T^{\intercal}$

  * •

if $i,j\notin S$:

$\mathcal{F}_{S}(f\circ T)=\mathcal{F}_{S}(f)\circ T$

  * •

if $i\in S,j\notin S$:

$\mathcal{F}_{S}(f\circ
T)(X)=\chi_{\bm{x}_{i}}(\bm{x}_{j})\mathcal{F}_{S}(f)(X)$

Note that do not consider the case $i\notin S,j\in S$, since the expression
does not simplify in that case.

######  Lemma 1.

Let $f:\\{0,1\\}^{r\times n}\to\mathbb{R}$. The following are equivalent:

  1. 1.

For every $T\in\text{{GL}}(r,2)$,

$f=f\circ T.$

  2. 2.

For every $S\subset[r]$,

$\mathcal{F}_{S}(f)(\bm{x}_{1},\dots,\bm{x}_{r})=0,$

if $\langle\bm{x}_{i},\bm{x}_{j}\rangle=1\bmod 2$ for some $i\in S$ and
$j\in[r]\setminus S$.

  3. 3.

For every $S\subset[r]$,

$\mathcal{F}_{S}(f)=\mathcal{F}_{S}(f)\circ(T_{1}T_{2})$

if $T_{1},T_{2}\in\text{{GL}}(r,2)$, and $T_{1}\bm{e}_{i}=\bm{e}_{i}$ for
every $i\in S$, $T_{2}\bm{e}_{i}=\bm{e}_{i}$ for every $i\in[r]\setminus S$.

###### Proof.

  * •

$\eqref{C456_equivalence:item1}\Rightarrow\eqref{C456_equivalence:item2}$: Let
$S\subsetneq[r]$, $S\neq\emptyset$. Let
$\bm{x}_{1},\dots,\bm{x}_{r}\in\\{0,1\\}^{n}$ and $i\in S$, $j\in[r]\setminus
S$ s.t. $\langle\bm{x}_{i},\bm{x}_{j}\rangle=1\bmod 2$. Let
$T\in\text{{GL}}(r,2)$ be the mapping $\bm{x}_{i}\mapsto\bm{x}_{i}+\bm{x}_{j}$
and $\bm{x}_{k}\mapsto\bm{x}_{k}$ for $k\neq i$. By assumption and by
proposition 7,

$\mathcal{F}_{S}(f)=\mathcal{F}_{S}(f\circ
T)=\chi_{\bm{x}_{i}}(\bm{x}_{j})\mathcal{F}_{S}(f)=-\mathcal{F}_{S}(f)$

Hence $\mathcal{F}_{S}(f)=0$.

  * •

$\eqref{C456_equivalence:item2}\Rightarrow\eqref{C456_equivalence:item3}$: It
is enough to show that $\mathcal{F}_{S}(f)$ is invariant under the mapping
$\bm{x}_{i}\mapsto\bm{x}_{i}+\bm{x}_{j}$, where $i\neq j$ and $i,j$ are either
both in $S$ or both in $[r]\setminus S$. The rest follows by composition of
such operators.

If $|S|\leq 1$ the claim holds trivially. Otherwise, let $i\neq j$, $i,j\in
S$, and let $\bm{x}_{1},\dots,\bm{x}_{r}\in\\{0,1\\}^{n}$. Observe that
$\mathcal{F}_{S}(f)=\mathcal{F}_{\\{i\\}}\mathcal{F}_{S\setminus\\{i\\}}(f)$.
Hence

$\mathcal{F}_{S}(f)(\bm{x}_{1},\dots,\bm{x}_{r})=2^{-n}\sum_{\bm{y}\in\\{0,1\\}^{r}}\chi_{\bm{x}_{i}}(\bm{y})\mathcal{F}_{S\setminus\\{i\\}}(f)(\dots,\bm{x}_{i-1},\bm{y},\bm{x}_{i+1},\dots)$

by assumption,
$\mathcal{F}_{S\setminus\\{i\\}}(f)(\dots,\bm{x}_{i-1},\bm{y},\bm{x}_{i+1},\dots)=0$
if $\langle\bm{y},\bm{x}_{j}\rangle=1$, hence $\chi_{\bm{x}_{j}}(\bm{y})=1$
for every non-zero element of the sum. So

$\mathcal{F}_{S}(f)(\bm{x}_{1},\dots,\bm{x}_{r})=2^{-n}\sum_{\bm{y}\in\\{0,1\\}^{r}}\chi_{\bm{x}_{i}}(\bm{y})\chi_{\bm{x}_{j}}(\bm{y})\times\\\
\times\mathcal{F}_{S\setminus\\{i\\}}(f)(\dots,\bm{x}_{i-1},\bm{y},\bm{x}_{i+1},\dots)=\mathcal{F}_{S}(f)(\dots,\bm{x}_{i-1},\bm{x}_{i}+\bm{x}_{j},\bm{x}_{i+1},\dots)$

To see that the same applies if $i,j\in[r]\setminus S$, observe that
$\mathcal{F}_{S}(f)=2^{n}\mathcal{F}_{\\{i\\}}\mathcal{F}_{S\cup\\{i\\}}(f)$
and repeat the same steps.

  * •

$\eqref{C456_equivalence:item3}\Rightarrow\eqref{C456_equivalence:item1}$:
Take $S=\emptyset$.

∎

##  6 On Multivariate Krawtchouk Polynomials

The multivariate Krawtchouk polynomials are orthogonal polynomials on the
multinomial distribution. Univariate Krawtchouk polynomials are the Fourier
transform of the level sets in the Boolean cube, and as we show in this
section, these polynomials are the Fourier transform of the level-set
indicators $\\{L_{\alpha}\\}$.

We borrow the terminology of [8]. The multinomial distribution
$m(\bm{\alpha},\bm{p})$ arises in the stochastic process where $n$ identical
balls are independently dropped into $d$ bins, where the probability of
falling into the $i$-th bin is $p_{i}$. The probability that $\alpha_{i}$
balls end up in bin $i$ is

$m(\bm{\alpha},\bm{p})=\binom{n}{\alpha_{0},\dots,\alpha_{d-1}}\prod_{i=0}^{d-1}p_{i}^{\alpha_{i}}=\binom{n}{\bm{\alpha}}\bm{p}^{\bm{\alpha}}$

Here $\bm{p}=(p_{0},\dots,p_{d-1})$, all $\alpha_{i}$ are nonnegative integers
and their sum is $n$. We use the shorthand $m(\bm{\alpha})$ when $\bm{p}$ is
uniform.

Orthogonal systems of univariate polynomials are constructed by applying a
Gram-Schmidt process to the polynomials $1,x,x^{2},\ldots$ e.g., [17]. The
result depends only on a measure that we fix on the underlying set. However,
as mentioned e.g., in [18], in the process of defining an orthogonal
multivariate family of polynomials, there is another choice to make, and this
choice affects the resulting family. Namely, we need to choose the order at
which we go over the monomials of a given degree. In [8], this freedom is
mitigated by choosing a basis of orthogonal functions on
$\\{0,1,\dots,d-1\\}$. Every such basis leads to a unique set of orthogonal
polynomials, as follows. Let $\bm{h}=\\{h^{l}\\}_{l=0}^{d-1}$ be a complete
set of orthogonal functions w.r.t. $\bm{p}$, with $h^{0}\equiv 1$. Namely,

$\sum_{i=0}^{d-1}h^{l}(i)h^{k}(i)p_{i}=\delta_{lk}a_{k},\quad 0\leq k,l\leq d$

The Krawtchouks are defined in terms of a generating function. Fix
$\bm{\alpha}$ and $\bm{h}$ as above. For every choice of nonnegative reals
$\xi_{0},\ldots,\xi_{d-1}$ whose sum is $n$, we define

$Q(\bm{\xi})=Q_{\bm{\alpha}}(\bm{\xi},\bm{h})=\underset{\prod_{i=1}^{d-1}w_{i}^{\alpha_{i}}}{\text{coef}}\prod_{j=0}^{d-1}\bigg{\\{}1+\sum_{l=1}^{d-1}w_{l}h^{l}(j)\bigg{\\}}^{\xi_{j}}$

where $\bm{w}=(w_{0}\dots,w_{d-1})$ are formal variables. The total degree of
$Q_{\bm{\alpha}}$ is $\sum_{i=1}^{d-1}\alpha_{i}$. Note that
$\alpha_{0},w_{0}$ do not appear in the definition. An equivalent definition
that does include $\alpha_{0},w_{0}$ is:

$Q_{\bm{\alpha}}(\bm{\xi},\bm{h})=\underset{\bm{w}^{\bm{\alpha}}}{\text{coef}}\prod_{j=0}^{d-1}\bigg{\\{}\sum_{l=0}^{d-1}w_{l}h^{l}(j)\bigg{\\}}^{\xi_{j}}$
(2)

It is easy to see the equivalence by expanding each factor with the
multinomial expansion. We will be using all of this with $d=2^{r}$, uniform
$\bm{p}\equiv 2^{-r}$ and with the orthonormal functions that are the
characters of $\\{0,1\\}^{r}$:
$\bm{h}=\\{\chi_{\bm{u}}\\}_{{\bm{u}}\in\\{0,1\\}^{r}}$.

Recall the definition of level-set indicators, $\\{L_{\bm{\alpha}}\\}$:

$L_{\bm{\alpha}}(X)=\mathbf{1}_{[\operatorname{\Gamma}_{X}=\bm{\alpha}]},\quad
X\in\\{0,1\\}^{r\times n}$

We also defined $\mathcal{I}_{r,n}$ the set of all ordered partitions of $[n]$
into $2^{r}$ parts.

$\mathcal{I}_{r,n}=\\{\operatorname{\Gamma}_{X}:X\in\\{0,1\\}^{r\times n}\\}$

Also, $\mathcal{I}_{r,n}$ is the support of the multinomial distribution with
$n$ balls, $2^{r}$ bins, where $\bm{p}$ is uniform.

Let $X\in\\{0,1\\}^{r\times n}$ be a random matrix that results by sampling
$n$ columns independently and uniformly from $\\{0,1\\}^{r}$. The probability
that $L_{\bm{\alpha}}(X)=1$ is $m(\bm{\alpha})=2^{-rn}\binom{n}{\alpha}$. It
is clear that $L_{\bm{\alpha}}(X)$ depends only on
$\operatorname{\Gamma}_{X}$, and by proposition 5 this is true for
$\hat{L}_{\bm{\alpha}}(X)$ as well. Define

$K_{\bm{\alpha}}(\operatorname{\Gamma}_{X})=2^{rn}\hat{L}_{\bm{\alpha}}(X),\quad
X\in\\{0,1\\}^{r\times n}$

It is easy to see that $\\{K_{\bm{\alpha}}\\}$ are orthogonal with respect to
$m(\bm{\alpha})$, using Parseval’s identity:

$\sum_{\bm{\gamma}}m(\bm{\gamma})K_{\bm{\alpha}}(\bm{\gamma})K_{\bm{\beta}}(\bm{\gamma})=\sum_{\bm{\gamma}}2^{-rn}\sum_{X:\operatorname{\Gamma}_{X}=\bm{\gamma}}2^{2rn}\hat{L}_{\bm{\alpha}}(X)\hat{L}_{\bm{\beta}}(X)=\sum_{X\in\\{0,1\\}^{r\times
n}}L_{\bm{\alpha}}(X)L_{\bm{\beta}}(X)=\binom{n}{\bm{\alpha}}\delta_{\bm{\alpha},\bm{\beta}}$

where $\bm{\alpha},\bm{\beta},\bm{\gamma}\in\mathcal{I}_{r,n}$. The extra
$2^{-rn}$ is there because inner product is normalized in the non-Fourier
space.

The following proposition shows that $\\{K_{\bm{\alpha}}\\}$ are Krawtchouk
polynomials.

######  Proposition 8.

$K_{\bm{\alpha}}$ is the Krawtchouk polynomial $Q_{\bm{\alpha}}(\cdot,\bm{h})$
with $d=2^{r}$, $\bm{h}$ are the Fourier characters
$\\{\chi_{\bm{u}}\\}_{{\bm{u}}\in\\{0,1\\}^{r}}$, and $\bm{p}\equiv 2^{-r}$ is
the uniform distribution.

###### Proof.

Let $X\in\\{0,1\\}^{r\times n}$ and
$\operatorname{\Gamma}_{X}=\bm{\beta}=(\beta_{\bm{u}})_{{\bm{u}}\in\\{0,1\\}^{r}}$.
We show that $K_{\bm{\alpha}}(\bm{\beta})$ coincides with the definition of
$Q_{\bm{\alpha}}(\bm{\beta},\\{\chi_{\bm{u}}\\}_{{\bm{u}}\in\\{0,1\\}^{r}})$
in (2).

By definition,

$\displaystyle K_{\bm{\alpha}}(\bm{\beta})=\hat{L}_{\bm{\alpha}}(X)$
$\displaystyle=2^{-rn}\sum_{Y\in\\{0,1\\}^{r\times n}}(-1)^{\langle
X,Y\rangle}L_{\bm{\alpha}}(Y)$

The inner product between $X$ and $Y$ can be expressed column-wise,

$\langle
X,Y\rangle=\sum_{j=1}^{n}\langle(X^{\intercal})_{j},(Y^{\intercal})_{j}\rangle=\sum_{{\bm{u}},{\bm{v}}\in\\{0,1\\}^{r}}\langle{\bm{u}},{\bm{v}}\rangle\operatorname{\Gamma}_{[X,Y]}({\bm{u}},{\bm{v}})$

where $[X,Y]\in\\{0,1\\}^{2r\times n}$ is the stacking of $X$ on top of $Y$,
and $\operatorname{\Gamma}_{[X,Y]}({\bm{u}},{\bm{v}})$ is the number of times
the column $[{\bm{u}},{\bm{v}}]\in\\{0,1\\}^{2r}$ appears in the matrix
$[X,Y]$. We consider $\operatorname{\Gamma}_{[X,Y]}({\bm{u}},{\bm{v}})$ as a
matrix indexed by $\\{0,1\\}^{r}\times\\{0,1\\}^{r}$. Its ${\bm{u}}$-th row
sums to $\beta_{\bm{u}}$ and its ${\bm{v}}$-th column sums to
$\operatorname{\Gamma}_{Y}({\bm{v}})$. Hence,

$\displaystyle\hat{L}_{\bm{\alpha}}(X)=2^{-rn}\sum_{A}\sum_{\begin{subarray}{c}Y\in\\{0,1\\}^{r\times
n}:\\\
\operatorname{\Gamma}_{[X,Y]}=A\end{subarray}}\prod_{{\bm{u}},{\bm{v}}\in\\{0,1\\}^{r}}(-1)^{\langle{\bm{u}},{\bm{v}}\rangle
A_{{\bm{u}},{\bm{v}}}}L_{\bm{\alpha}}(Y)$

where the outer sum is over all matrices $A\in\mathbb{N}^{2^{r}\times 2^{r}}$
with $A\cdot\mathbf{1}=\bm{\beta}$.

If $\operatorname{\Gamma}_{Y}=\bm{\alpha}$ then $\mathbf{1}^{\intercal}\cdot
A=\bm{\alpha}$. In particular, $A$ uniquely determines $L_{\bm{\alpha}}(Y)$,
so the product does not depend on $Y$. The sum over $Y$ evaluates to the size
of the set $\\{Y\in\\{0,1\\}^{r\times n}:\operatorname{\Gamma}_{[X,Y]}=A\\}$,
which we now compute. For every ${\bm{u}}\in\\{0,1\\}^{r}$, $[X,Y]$ contains
$\operatorname{\Gamma}_{X}({\bm{u}})=\beta_{\bm{u}}$ columns whose prefix is
${\bm{u}}$. For every ${\bm{v}}\in\\{0,1\\}^{r}$, the column
$[{\bm{u}},{\bm{v}}]$ appears $A_{{\bm{u}},{\bm{v}}}$ times in $[X,Y]$. Since
the position of the ${\bm{u}}$’s is fixed, it is left to position the
${\bm{v}}$’s with respect to each $\bm{u}$. Hence

$|\\{Y\in\\{0,1\\}^{r\times
n}:\operatorname{\Gamma}_{[X,Y]}=A\\}|=\prod_{{\bm{u}}\in\\{0,1\\}^{r}}\binom{\beta_{\bm{u}}}{A_{\bm{u}}}$

where $A_{\bm{u}}$ is the row of $A$ that is indexed by $\bm{u}$.

Let $\bm{w}=(w_{\bm{v}})_{{\bm{v}}\in\\{0,1\\}^{r}}$ be formal variables. If
$A$ is such that $\mathbf{1}^{\intercal}A=\bm{\alpha}$ then

$\prod_{{\bm{u}},{\bm{v}}}w_{\bm{v}}^{A_{{\bm{u}},{\bm{v}}}}=\prod_{\bm{v}}w_{\bm{v}}^{\sum_{\bm{u}}A_{{\bm{u}},{\bm{v}}}}=\prod_{\bm{v}}w_{\bm{v}}^{\alpha_{\bm{v}}}$

hence $\hat{L}_{\bm{\alpha}}(X)$ equals

$\underset{\bm{w}^{\bm{\alpha}}}{\text{coef}}~{}2^{-rn}\sum_{A}\prod_{{\bm{u}}\in\\{0,1\\}^{r}}\binom{\beta_{\bm{u}}}{A_{\bm{u}}}\prod_{{\bm{v}}\in\\{0,1\\}^{r}}\Big{(}(-1)^{\langle{\bm{u}},{\bm{v}}\rangle}w_{\bm{v}}\Big{)}^{A_{{\bm{u}},{\bm{v}}}}$

The sum over $A$ can be expanded to nested sums over its rows,

$\sum_{A}=\sum_{A_{0}}\sum_{A_{1}}\cdots\sum_{A_{2^{r}-1}}$

where $A_{\bm{u}}\in\mathbb{N}^{2^{r}}$,
$A_{\bm{u}}\cdot\mathbf{1}=\beta_{\bm{u}}$. Every factor in the product
depends on a single row of $A$, so the product and the sum can be transposed.
Then, by the multinomial theorem:

$\hat{L}_{\bm{\alpha}}(X)=\underset{\bm{w}^{\bm{\alpha}}}{\text{coef}}~{}2^{-rn}\prod_{{\bm{u}}\in\\{0,1\\}^{r}}\bigg{\\{}\sum_{{\bm{v}}\in\\{0,1\\}^{r}}(-1)^{\langle{\bm{u}},{\bm{v}}\rangle}w_{v}\bigg{\\}}^{\beta_{\bm{u}}}=2^{-rn}Q_{\bm{\alpha}}(\bm{\beta},\\{\chi_{\bm{v}}\\}_{\bm{v}\in\\{0,1\\}^{r}})$

∎

We turn to deal with partial Fourier transform of the level-set indicators.
Let $S\subsetneq\\{1,\dots,r\\}$ be non-empty. Denote by
$X^{\prime},X^{\prime\prime}$ be the sub-matrix of $X\in\\{0,1\\}^{r\times n}$
with row set $S$ and $[r]\setminus S$, respectively. Similarly,
$\bm{u}^{\prime},\bm{u}^{\prime\prime}$ are obtained from
$\bm{u}\in\\{0,1\\}^{r}$ by restricting to $S,[r]\setminus S$, respectively.
For $\bm{\alpha}\in\mathcal{I}_{r,n}$ define the rearrangement of
$\bm{\alpha}$ into a matrix
$\bm{\alpha}^{S}=(\alpha^{S}_{\bm{u}^{\prime\prime},\bm{u}^{\prime}})_{\bm{u}^{\prime\prime}\in\\{0,1\\}^{r-|S|},\bm{u}^{\prime}\in\\{0,1\\}^{|S|}}$
by

$\alpha^{S}_{\bm{u}^{\prime\prime},\bm{u}^{\prime}}=\alpha_{\bm{u}}\quad\bm{u}\in\\{0,1\\}^{r}$

For $X\in\\{0,1\\}^{r\times n}$ we define $K^{S}_{\bm{\alpha}}$ as follows:

$K^{S}_{\bm{\alpha}}(\operatorname{\Gamma}_{X})\coloneqq
2^{|S|n}\mathcal{F}_{S}(L_{\bm{\alpha}})(X)$

The next proposition says that $K^{S}_{\bm{\alpha}}$ is a sparse product of
lower-order Krawtchouks.

######  Proposition 9.

For every $\bm{\beta}\in\mathcal{I}_{r,n}$ there holds

$K^{S}_{\bm{\alpha}}(\bm{\beta})=\begin{cases}\prod
K_{\bm{\alpha}^{S}_{\bm{v}}}(\bm{\beta}^{S}_{\bm{v}})&\text{if
}\bm{\alpha}^{S}_{\bm{v}}\cdot\mathbf{1}=\bm{\beta}^{S}_{\bm{v}}\cdot\mathbf{1}~{}\forall\bm{v}\\\
0&\text{otherwise.}\end{cases}$

where the product is over all $\bm{v}\in\\{0,1\\}^{r-|S|}$. Here
$\bm{\alpha}^{S}_{v}$ is the row of $\bm{\alpha}^{S}$ at index $\bm{v}$, and
$\bm{\alpha}^{S}_{\bm{v}}\cdot\mathbf{1}=\sum_{\bm{u}^{\prime}\in\\{0,1\\}^{|S|}}\alpha^{S}_{\bm{v},\bm{u}^{\prime}}$.

###### Proof.

Let $X\in\\{0,1\\}^{r\times n}$ such that
$\operatorname{\Gamma}_{X}=\bm{\beta}$. By definition,

$K^{S}_{\bm{\alpha}}(\bm{\beta})=\mathcal{F}_{S}(L_{\bm{\alpha}})(X)=2^{-|S|n}\sum_{Y\in\\{0,1\\}^{r\times
n}}(-1)^{\langle
X^{\prime},Y^{\prime}\rangle}\delta_{X^{\prime\prime}}(Y^{\prime\prime})L_{\bm{\alpha}}(Y)$

We express $\delta_{X^{\prime\prime}}(Y^{\prime\prime})L_{\bm{\alpha}}(Y)$ in
terms of $Y^{\prime}$, $\bm{\alpha}^{S}$ and $\bm{\beta}^{S}$.

Let $Y\in\\{0,1\\}^{r\times n}$ such that
$\operatorname{\Gamma}_{Y}=\bm{\alpha}$ and
$Y^{\prime\prime}=X^{\prime\prime}$. The number of times
$\bm{u}^{\prime\prime}\in\\{0,1\\}^{r-|S|}$ occurs in $Y^{\prime\prime}$ is
$\bm{\alpha}^{S}_{\bm{u}^{\prime\prime}}\cdot\mathbf{1}=\sum_{\bm{u}^{\prime}}\alpha^{S}_{\bm{u}^{\prime\prime},\bm{u}^{\prime}}$.
But this is equal $\bm{\beta}^{S}_{\bm{u}^{\prime\prime}}\cdot\mathbf{1}$
because $Y^{\prime\prime}=X^{\prime\prime}$.

Let $Y^{\prime}|_{Y^{\prime\prime}=\bm{u}^{\prime\prime}}$ be the subset of
columns from $Y^{\prime}$ for which the corresponding column in
$Y^{\prime\prime}$ is $\bm{u}^{\prime\prime}$. Then
$\operatorname{\Gamma}_{Y^{\prime}|_{Y^{\prime\prime}=\bm{u}^{\prime\prime}}}=\bm{\alpha}^{S}_{\bm{u}^{\prime\prime}}$.

$L_{\bm{\alpha}}(Y)\delta_{X^{\prime\prime}}(Y^{\prime\prime})=\prod_{\bm{u}^{\prime\prime}\in\\{0,1\\}^{r-|S|}}\mathbf{1}_{[\bm{\alpha}^{S}_{\bm{u}^{\prime\prime}}\cdot\mathbf{1}=\bm{\beta}^{S}_{\bm{u}^{\prime\prime}}\cdot\mathbf{1}]}L_{\bm{\alpha}^{S}_{\bm{u}^{\prime\prime}}}(Y^{\prime}|_{Y^{\prime\prime}=\bm{u}^{\prime\prime}})$

The sum over $Y$ can be broken into nested sums over
$\\{Y^{\prime}|_{Y^{\prime\prime}=\bm{u}^{\prime\prime}}\\}_{\bm{u}^{\prime\prime}\in\\{0,1\\}^{r-|S|}}$,

$\sum_{Y\in\\{0,1\\}^{r\times
n}}=\sum_{Y^{\prime}_{0}}\sum_{Y^{\prime}_{1}}\dots\sum_{Y^{\prime}_{2^{r-|S|}-1}}$

where $Y^{\prime}_{\bm{u}^{\prime\prime}}\in\\{0,1\\}^{|S|\times n}$ are
mutually independent. Each factor in the product depends on a single
$Y^{\prime}_{\bm{u}^{\prime\prime}}$ so the order of summations and products
can be reversed,

$\mathcal{F}_{S}(L_{\bm{\alpha}})(X)=2^{-|S|n}\prod_{\bm{u}^{\prime\prime}\in\\{0,1\\}^{r-|S|}}\bigg{[}\mathbf{1}_{[\bm{\alpha}^{S}_{\bm{u}^{\prime\prime}}\cdot\mathbf{1}=\bm{\beta}^{S}_{\bm{u}^{\prime\prime}}\cdot\mathbf{1}]}\times\\\
\times\sum_{Y^{\prime}_{\bm{u}^{\prime\prime}}\in\\{0,1\\}^{|S|\times
n}}(-1)^{\langle
X^{\prime}|_{X^{\prime\prime}=\bm{u}^{\prime\prime}},Y^{\prime}_{\bm{u}^{\prime\prime}}\rangle}L_{\bm{\alpha}^{S}_{\bm{u}^{\prime\prime}}}(Y^{\prime}|_{Y^{\prime\prime}=\bm{u}^{\prime\prime}})\bigg{]}$

Observe that the inner sum is simply

$\hat{L}_{\bm{\alpha}^{S}_{\bm{u}^{\prime\prime}}}(X^{\prime}|_{X^{\prime\prime}=\bm{u}^{\prime\prime}})=K^{S}_{\bm{\alpha}^{S}_{\bm{u}^{\prime\prime}}}(\bm{\beta}^{S}_{\bm{u}^{\prime\prime}}).$

∎

In the last part of this section we consider $K_{\bm{\alpha}}^{S}$ under the
action of the general linear group $\text{{GL}}(r,2)$.

Fix $S\subset[r]$ and $\bm{\alpha}\in\mathcal{I}_{r,n}$. It is easy to verify
that

$K^{S}_{T\cdot\bm{\alpha}}(\operatorname{\Gamma}_{X})=\mathcal{F}_{S}(L_{\bm{\alpha}}\circ
T)(X)$

for every $X\in\\{0,1\\}^{r\times n}$ and $T\in\text{{GL}}(r,2)$. Propositions
10 and 11 below are immediate consequences of 6 and 7.

######  Proposition 10.

Let $T\in\text{{GL}}(r,2)$ be a permutation matrix,
$T\bm{e}_{i}=\bm{e}_{\pi(i)}$ for some $\pi\in\mathfrak{S}_{r}$. Then

$K^{S}_{T\cdot\bm{\alpha}}=K^{\pi^{-1}(S)}_{\bm{\alpha}}\circ T$

######  Proposition 11.

Let $T\in\text{{GL}}(r,2)$ be the mapping
$\bm{e}_{i}\mapsto\bm{e}_{i}+\bm{e}_{j}$ for some $i,j\in[r]$, and
$\bm{e}_{k}\mapsto\bm{e}_{k}$ for every $k\neq i$.

  * •

if $i,j\in S$:

$K^{S}_{T\cdot\bm{\alpha}}=K^{S}_{\bm{\alpha}}\circ T^{\intercal}$

  * •

if $i,j\notin S$:

$K^{S}_{T\cdot\bm{\alpha}}=K^{S}_{\bm{\alpha}}\circ T$

  * •

if $i\in S,j\notin S$:

$K^{S}_{T\cdot\bm{\alpha}}(\bm{\beta})=(-1)^{\sum_{\bm{u}\in\\{0,1\\}^{r}}\beta_{\bm{u}}u_{i}u_{j}}K^{S}_{\bm{\alpha}}(\bm{\beta})$

## References

  * [1] E. N. Gilbert, “A comparison of signalling alphabets,” _The Bell system technical journal_ , vol. 31, no. 3, pp. 504–522, 1952.
  * [2] R. R. Varshamov, “Estimate of the number of signals in error correcting codes,” _Docklady Akad. Nauk, SSSR_ , vol. 117, pp. 739–741, 1957.
  * [3] R. McEliece, E. Rodemich, H. Rumsey, and L. Welch, “New upper bounds on the rate of a code via the delsarte-macwilliams inequalities,” _IEEE transactions on Information Theory_ , vol. 23, no. 2, pp. 157–166, 1977.
  * [4] P. Delsarte, “An algebraic approach to the association schemes of coding theory,” _Philips Res. Rep. Suppl._ , vol. 10, pp. vi+–97, 1973.
  * [5] A. Barg and D. B. Jaffe, “Numerical results on the asymptotic rate of binary codes.” _Codes and Association Schemes_ , vol. 56, pp. 25–32, 1999.
  * [6] L. N. Coregliano, F. G. Jeronimo, and C. Jones, “A complete linear programming hierarchy for linear codes,” _arXiv preprint arXiv:2112.09221_ , 2021.
  * [7] M. Grassl, “Bounds on the minimum distance of linear codes and quantum codes,” Online available at http://www.codetables.de, 2007, accessed on 2022-04-18.
  * [8] P. Diaconis and R. Griffiths, “An introduction to multivariate krawtchouk polynomials and their applications,” _Journal of Statistical Planning and Inference_ , vol. 154, pp. 39–53, 2014.
  * [9] F. A. Grünbaum, M. Rahman _et al._ , “A system of multivariable krawtchouk polynomials and a probabilistic application,” _SIGMA. Symmetry, Integrability and Geometry: Methods and Applications_ , vol. 7, p. 118, 2011.
  * [10] J. Friedman and J.-P. Tillich, “Generalized alon–boppana theorems and error-correcting codes,” _SIAM Journal on Discrete Mathematics_ , vol. 19, no. 3, pp. 700–718, 2005.
  * [11] M. Navon and A. Samorodnitsky, “On delsarte’s linear programming bounds for binary codes,” in _46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05)_. IEEE, 2005, pp. 327–336.
  * [12] ——, “Linear programming bounds for codes via a covering argument,” _Discrete & Computational Geometry_, vol. 41, no. 2, pp. 199–207, 2009\.
  * [13] A. Samorodnitsky, “One more proof of the first linear programming bound for binary codes and two conjectures,” _arXiv preprint arXiv:2104.14587_ , 2021\.
  * [14] A. M. Barg and D. Y. Nogin, “Spectral approach to linear programming bounds on codes,” _Problems of Information Transmission_ , vol. 42, no. 2, pp. 77–89, 2006.
  * [15] A. Barg and D. Nogin, “A functional view of upper bounds on codes,” in _Coding and cryptology_. World Scientific, 2008, pp. 15–24.
  * [16] R. O’Donnell, _Analysis of boolean functions_. Cambridge University Press, 2014.
  * [17] G. Szegö, _Orthogonal polynomials_. American Mathematical Soc., 1939, vol. 23.
  * [18] C. F. Dunkl and Y. Xu, _Orthogonal polynomials of several variables_. Cambridge University Press, 2014, no. 155.
  * [19] A. M. Gleixner, D. E. Steffy, and K. Wolter, “Improving the accuracy of linear programming solvers with iterative refinement,” in _Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation_ , 2012, pp. 187–194.
  * [20] ——, “Iterative refinement for linear programming,” _INFORMS Journal on Computing_ , vol. 28, no. 3, pp. 449–464, 2016.
  * [21] G. Gamrath, D. Anderson, K. Bestuzheva, W.-K. Chen, L. Eifler, M. Gasse, P. Gemander, A. Gleixner, L. Gottwald, K. Halbig _et al._ , “The scip optimization suite 7.0,” 2020.
  * [22] D. L. Applegate, W. Cook, S. Dash, and D. G. Espinoza, “Exact solutions to linear programming problems,” _Operations Research Letters_ , vol. 35, no. 6, pp. 693–699, 2007.

##  7 Appendix

###  7.1 Proofs for section 5

###### Proof of 5.

For $\bm{x},\bm{y}\in\\{0,1\\}^{n}$,

$\chi_{\bm{x}}(\sigma\cdot{\bm{y}})=(-1)^{\sum_{i=1}^{n}x_{i}y_{\sigma(i)}}=(-1)^{\sum_{i=1}^{n}x_{\sigma^{-1}(i)}y_{i}}=\chi_{\sigma^{-1}\cdot{\bm{x}}}({\bm{y}})$

and

$\delta_{\bm{x}}(\sigma\cdot{\bm{y}})=\prod_{i=1}^{n}\delta_{x_{i}}(y_{\sigma(i)})=\prod_{i=1}^{n}\delta_{x_{\sigma^{-1}(i)}}(y_{i})=\delta_{\sigma^{-1}\cdot{\bm{x}}}({\bm{y}})$

Hence, for $X,Y\in\\{0,1\\}^{r\times n}$,

$\chi^{S}_{X}(\sigma\cdot Y)=\chi^{S}_{\sigma^{-1}\cdot X}(Y)$

Finally, letting $Y^{\prime}=\sigma\cdot Y$,

$\mathcal{F}_{S}(f\circ\sigma)(X)=\sum_{Y\in\\{0,1\\}^{r\times
n}}\chi_{X}(Y)f(\sigma\cdot Y)=\sum_{Y^{\prime}\in\\{0,1\\}^{r\times
n}}\chi_{X}(\sigma^{-1}\cdot Y^{\prime})f(Y^{\prime})\\\
=\sum_{Y^{\prime}\in\\{0,1\\}^{r\times n}}\chi_{\sigma\cdot
X}(Y^{\prime})f(Y^{\prime})=\mathcal{F}_{S}(f)(\sigma\cdot X)$

∎

###### Proof of 6.

$\mathcal{F}_{S}(f\circ\pi)({\bm{x}}_{1},\dots,{\bm{x}}_{r})=2^{-rn}\sum_{{\bm{y}}_{1},\dots,{\bm{y}}_{r}}\chi^{S}_{{\bm{x}}_{1},\dots,{\bm{x}}_{r}}({\bm{y}}_{1},\dots,{\bm{y}}_{r})f({\bm{y}}_{\pi(1)},\dots,{\bm{y}}_{\pi(r)})=2^{-rn}\sum_{{\bm{y}}_{1},\dots,{\bm{y}}_{r}}\chi^{S}_{{\bm{x}}_{1},\dots,{\bm{x}}_{r}}({\bm{y}}_{\pi^{-1}(1)},\dots,{\bm{y}}_{\pi^{-1}(r)})\times\\\
\times
f({\bm{y}}_{1},\dots,{\bm{y}}_{r})=2^{-rn}\sum_{{\bm{y}}_{1},\dots,{\bm{y}}_{r}}\prod_{i\in
S}\chi_{{\bm{x}}_{i}}({\bm{y}}_{\pi^{-1}(i)})\times\\\
\times\prod_{i\in[r]\setminus
S}\delta_{{\bm{x}}_{i}}({\bm{y}}_{\pi^{-1}(i)})f({\bm{y}}_{1},\dots,{\bm{y}}_{r})=2^{-rn}\sum_{{\bm{y}}_{1},\dots,{\bm{y}}_{r}}\prod_{j\in\pi^{-1}(S)}\chi_{{\bm{x}}_{\pi(j)}}({\bm{y}}_{j})\times\\\
\times\prod_{j\in[r]\setminus\pi^{-1}(S)}\delta_{{\bm{x}}_{\pi(j)}}({\bm{y}}_{j})f({\bm{y}}_{1},\dots,{\bm{y}}_{r})=\mathcal{F}_{\pi^{-1}(S)}(f)({\bm{x}}_{\pi(1)},\dots,{\bm{x}}_{\pi(r)})$

∎

###### Proof of 7.

Consider $f$ as a function of $r$ vectors,
${\bm{x}}_{1},\dots,{\bm{x}}_{r}\in\\{0,1\\}^{n}$. Then $T$ maps
${\bm{x}}_{i}\mapsto{\bm{x}}_{i}+{\bm{x}}_{j}$, and
${\bm{x}}_{k}\mapsto{\bm{x}}_{k}$ for $k\neq i$.

For $k=1,\dots,r$, and ${\bm{x}}\in\\{0,1\\}^{n}$, define a set of functions
$\\{\psi^{(k)}_{\bm{x}}\\}_{k\in[r]}$, where
$\psi^{(k)}_{\bm{x}}=\chi_{\bm{x}}$ if $k\in S$ and
$\psi^{(k)}_{\bm{x}}=\delta_{\bm{x}}$ otherwise.

$\mathcal{F}_{S}(f\circ
T)({\bm{x}}_{1},\dots,{\bm{x}}_{r})=2^{-rn}\sum_{\bm{y}_{1},\dots,\bm{y}_{r}}\prod_{k=1}^{r}\psi^{(k)}_{\bm{y}_{k}}(\bm{y}_{k})f(\bm{y}_{1},\dots,\underbrace{\bm{y}_{i}+\bm{y}_{j}}_{\text{index
}i},\dots,\bm{y}_{r})$

replacing the sum over $\bm{y}_{i}$ by a sum over $\bm{y}_{i}+\bm{y}_{j}$, we
get

$=2^{-rn}\sum_{\bm{y}_{1},\dots,\bm{y}_{r}}\psi^{(i)}_{\bm{x}_{i}}(\bm{y}_{i}+\bm{y}_{j})\psi^{(j)}_{\bm{y}_{j}}(\bm{y}_{j})\prod_{k\in[r]\setminus\\{i,j\\}}\psi^{(k)}_{\bm{y}_{k}}(\bm{y}_{k})f(\bm{y}_{1},\dots,\bm{y}_{i},\dots,\bm{y}_{r})$
(3)

We now examine the expression
$\psi^{(i)}_{\bm{x}_{i}}(\bm{y}_{i}+\bm{y}_{j})\psi^{(j)}_{\bm{y}_{j}}(\bm{y}_{j})$
in the different cases of the proposition.

  * •

$i,j\in S$:

$\psi^{(i)}_{\bm{x}_{i}}(\bm{y}_{i}+\bm{y}_{j})\psi^{(j)}_{\bm{x}_{j}}(\bm{y}_{j})=\chi_{\bm{x}_{i}}(\bm{y}_{i}+\bm{y}_{j})\chi_{\bm{x}_{j}}(\bm{y}_{j})=\chi_{\bm{x}_{i}}(\bm{y}_{i})\chi_{\bm{x}_{i}+\bm{x}_{j}}(\bm{y}_{j})=\psi^{(i)}_{\bm{x}_{i}}(\bm{y}_{i})\psi^{(j)}_{\bm{x}_{i}+\bm{x}_{j}}(\bm{y}_{j})$

which is the same as applying the mapping
$\bm{x}_{j}\mapsto\bm{x}_{i}+\bm{x}_{j}$, or equivalently $T^{\intercal}$, to
${\bm{x}}_{1},\dots,{\bm{x}}_{r}$.

  * •

$i,j\notin S$:

$\psi^{(i)}_{\bm{x}_{i}}(\bm{y}_{i}+\bm{y}_{j})\psi^{(j)}_{\bm{x}_{j}}(\bm{y}_{j})=\delta_{\bm{x}_{i}}(\bm{y}_{i}+\bm{y}_{j})\delta_{\bm{x}_{j}}(\bm{y}_{j})=\delta_{\bm{x}_{i}}(\bm{y}_{i}+\bm{x}_{j})\delta_{\bm{x}_{j}}(\bm{y}_{j})=\delta_{\bm{x}_{i}+\bm{x}_{j}}(\bm{y}_{i})\delta_{\bm{x}_{j}}(\bm{y}_{j})=\psi^{(i)}_{\bm{x}_{i}+\bm{x}_{j}}(\bm{y}_{i})\psi^{(j)}_{\bm{x}_{j}}(\bm{y}_{j})$

which equivalent to applying $T$ to ${\bm{x}}_{1},\dots,{\bm{x}}_{r}$.

  * •

$i\in S,j\notin S$:

$\psi^{(i)}_{\bm{x}_{i}}(\bm{y}_{i}+\bm{y}_{j})\psi^{(j)}_{\bm{x}_{j}}(\bm{y}_{j})=\chi_{\bm{x}_{i}}(\bm{y}_{i}+\bm{y}_{j})\delta_{\bm{x}_{j}}(\bm{y}_{j})=\chi_{\bm{x}_{i}}(\bm{x}_{j})\chi_{\bm{x}_{i}}(\bm{y}_{i})\delta_{\bm{x}_{j}}(\bm{y}_{j})=\chi_{\bm{x}_{i}}(\bm{x}_{j})\psi^{(i)}_{\bm{x}_{i}}(\bm{y}_{i})\psi^{(j)}_{\bm{x}_{j}}(\bm{y}_{j})$

observe that $\chi_{\bm{x}_{i}}(\bm{x}_{j})$ is constant with respect to the
sum in (3).

  * •

$i\notin S,j\in S$:

$\psi^{(i)}_{\bm{x}_{i}}(\bm{y}_{i}+\bm{y}_{j})\psi^{(j)}_{\bm{x}_{j}}(\bm{y}_{j})=\delta_{\bm{x}_{i}}(\bm{y}_{i}+\bm{y}_{j})\chi_{\bm{x}_{j}}(\bm{y}_{j})$

Here there is no obvious way to rewrite the functions so as to separate
$\bm{y}_{i}$ and $\bm{y}_{j}$.

∎

###  7.2 Numerical Results

We have experimented with several variants of
$\text{{{DelsarteLin}}}_{/\mathfrak{S}_{n}}(2,n,d)$ with $n$ ranging between
$10$ and $40$ and $d\leq n/2$ is even. In those variants of the LP - we
replace ($C2$) with (3.2), and ($Obj$) with (3.3). The table below only shows
the results for $n\geq 20$.

The number of variables is $|\mathcal{I}_{r,n}|=\binom{n+2^{r}-1}{2^{r}-1}$
and, if we consider $r$ as a constant, there are $O_{n}(|\mathcal{I}_{r,n}|)$
constraints. In practice, symmetrization w.r.t. $\text{{GL}}(r,2)$ reduces the
problem size (variables $\times$ constraints) by a factor of $2^{\Omega(r)}$,
which is significant. Since we have not yet developed the necessary
theoretical tools for such symmetrization, it was carried algorithmically. We
intend to develop such theory so as to solve instances of
$\text{{{DelsarteLin}}}_{/\mathfrak{S}_{n}}(r,n,d)$ with larger values of $r$.

The number of variables is further reduced using the well known fact, that if
$d$ is even then $A(n,d)$ is attained by an even code. Namely, we set
$\varphi_{\bm{\alpha}}=0$ if $(n-\chi_{\bm{u}}^{\intercal}\bm{\alpha})/2$ is
odd, for some $\bm{u}\in\\{0,1\\}^{r}$.

The Krawtchouk polynomials were computed with a recurrence formula, e.g. (16)
in [8]. The partial Krawtchouks $K^{S}_{\bm{\alpha}}$ were computed using
proposition 9. We used two exact solvers: SoPlex [19, 20, 21] and QSoptEx
[22], with up to 128GB of RAM and at most 3 days of runtime. Some instances
were solved by one solver and not the other. Missing entries were solved by
neither. Entries are marked with $*$ if $\lfloor\log_{2}(\text{entry})\rfloor$
equals the best known upper bound, as reported in [7].

Variant | $(C2^{\prime})$ | $(C2)$ | Delsarte
---|---|---|---
|  | $(Obj^{\prime})$ | $(Obj)$ | $(Obj^{\prime})$ | $(Obj)$ |
n | dist. |  |  |  |  |
20 | 4 | $26214^{*}$ | $26214^{*}$ | $\textbf{21845}^{*}$ | $\textbf{21845}^{*}$ | $26214^{*}$
| 6 | $2328$ | $2285$ | $\textbf{1588}^{*}$ | $1593^{*}$ | $2373$
| 8 | $268^{*}$ | $\textbf{256}^{*}$ | $\textbf{256}^{*}$ | $\textbf{256}^{*}$ | $291^{*}$
| 10 | $40$ | $40$ | $\textbf{24}^{*}$ | $\textbf{24}^{*}$ | $40$
21 | 4 | $\textbf{43691}^{*}$ | $\textbf{43691}^{*}$ | $\textbf{43691}^{*}$ | $\textbf{43691}^{*}$ | $47663^{*}$
| 6 | $4197$ | $4138$ | $3010^{*}$ | $\textbf{2977}^{*}$ | $4443$
| 8 | $\textbf{512}^{*}$ | $\textbf{512}^{*}$ | $\textbf{512}^{*}$ | $\textbf{512}^{*}$ | $572^{*}$
| 10 | $51^{*}$ | $52^{*}$ | $\textbf{35}^{*}$ | $36^{*}$ | $64$
22 | 4 | $\textbf{87381}^{*}$ | $\textbf{87381}^{*}$ | $\textbf{87381}^{*}$ | $\textbf{87381}^{*}$ | $\textbf{87381}^{*}$
| 6 | $7380^{*}$ | $7327^{*}$ | $5770^{*}$ | $\textbf{5608}^{*}$ | $7724^{*}$
| 8 | $\textbf{1024}^{*}$ | $\textbf{1024}^{*}$ | $\textbf{1024}^{*}$ | $\textbf{1024}^{*}$ | $\textbf{1024}^{*}$
| 10 | $92$ | $89$ | $\textbf{57}^{*}$ | $61^{*}$ | $95$
23 | 4 | $\textbf{174763}^{*}$ | $\textbf{174763}^{*}$ | $\textbf{174763}^{*}$ | $\textbf{174763}^{*}$ | $\textbf{174763}^{*}$
| 6 | $13703^{*}$ | $13690^{*}$ | $10447^{*}$ | $\textbf{10102}^{*}$ | $13776^{*}$
| 8 | $\textbf{2048}^{*}$ | $\textbf{2048}^{*}$ | $\textbf{2048}^{*}$ | $\textbf{2048}^{*}$ | $\textbf{2048}^{*}$
| 10 | $152$ | $152$ | $\textbf{90}^{*}$ | $93^{*}$ | $152$
24 | 4 | $\textbf{349525}^{*}$ | $\textbf{349525}^{*}$ | $\textbf{349525}^{*}$ | $\textbf{349525}^{*}$ | $\textbf{349525}^{*}$
| 6 | $24054^{*}$ | $24018^{*}$ | $18786^{*}$ | $\textbf{18715}^{*}$ | $24108^{*}$
| 8 | $\textbf{4096}^{*}$ | $\textbf{4096}^{*}$ | $\textbf{4096}^{*}$ | $\textbf{4096}^{*}$ | $\textbf{4096}^{*}$
| 10 | $280$ | $280$ | $\textbf{155}^{*}$ | $160^{*}$ | $280$
| 12 | $\textbf{48}^{*}$ | $\textbf{48}^{*}$ | $\textbf{48}^{*}$ | $\textbf{48}^{*}$ | $\textbf{48}^{*}$
25 | 4 | $599186^{*}$ | $599186^{*}$ | $582826^{*}$ | $\textbf{579701}^{*}$ | $645278^{*}$
| 6 | $47481$ | $47176$ | 34657 | $34729$ | $48149$
| 8 | $5666^{*}$ | $5571^{*}$ | $4450^{*}$ | $\textbf{4200}^{*}$ | $6475^{*}$
| 10 | $511$ | $497$ | 262 | $284$ | $551$
| 12 | $61^{*}$ | $62^{*}$ | $49^{*}$ | $\textbf{48}^{*}$ | $75$
26 | 4 | $1198373^{*}$ | $1198373^{*}$ | $1126532^{*}$ | $\textbf{1121065}^{*}$ | $1198373^{*}$
| 6 | $86693$ | $86847$ | 66014 | $66638$ | $93623$
| 8 | $10099$ | $10031$ | $7516^{*}$ | $\textbf{7508}^{*}$ | $10435$
| 10 | $930$ | $922$ | $\textbf{490}^{*}$ | $533$ | $1040$
| 12 | $105^{*}$ | $99^{*}$ | $\textbf{77}^{*}$ | $79^{*}$ | $113^{*}$
27 | 4 | $2396745^{*}$ | $2396745^{*}$ | $\textbf{2097152}^{*}$ | $\textbf{2097152}^{*}$ | $2396745^{*}$
| 6 | $162180$ | $162027$ | $\textbf{125238}^{*}$ | $126201^{*}$ | $163840$
| 8 | $17803$ | $17727$ | $\textbf{12698}^{*}$ | $12774^{*}$ | $18190$
| 10 | $1766$ | $1766$ | $\textbf{854}^{*}$ | $954^{*}$ | $1766$
| 12 | $171^{*}$ | $171^{*}$ | $132^{*}$ | $\textbf{129}^{*}$ | $171^{*}$
28 | 4 | $4793490^{*}$ | $4793490^{*}$ | $\textbf{4194304}^{*}$ | - | $4793490^{*}$
| 6 | $291202$ | $291173$ | $234649^{*}$ | $\textbf{234626}^{*}$ | $291271$
| 8 | $32126^{*}$ | $32119^{*}$ | $\textbf{21989}^{*}$ | $22120^{*}$ | $32206^{*}$
| 10 | $3194$ | $3189$ | $\textbf{1482}^{*}$ | $1646^{*}$ | $3200$
| 12 | $288$ | $288$ | $\textbf{213}^{*}$ | $\textbf{213}^{*}$ | $288$
| 14 | $56^{*}$ | $56^{*}$ | $\textbf{32}^{*}$ | $\textbf{32}^{*}$ | $56^{*}$
29 | 4 | $\textbf{8388608}^{*}$ | $\textbf{8388608}^{*}$ | $\textbf{8388608}^{*}$ | $\textbf{8388608}^{*}$ | $8947849^{*}$
| 6 | $574493$ | $573756$ | $\textbf{430773}^{*}$ | $432499^{*}$ | $581827$
| 8 | $57247$ | $57217$ | 38276 | $39205$ | $58097$
| 10 | $6155$ | $6074$ | 2743 | $3181$ | $6363$
| 12 | $550$ | $541$ | $\textbf{320}^{*}$ | $323^{*}$ | $573$
| 14 | $70$ | $72$ | $\textbf{47}^{*}$ | $49^{*}$ | $88$
30 | 8 | $108267$ | $107044$ | 67353 | $71095$ | $114816$
| 10 | $11517$ | $11340$ | 4827 | $5929$ | $12525$
| 12 | $1022^{*}$ | $1026$ | $\textbf{535}^{*}$ | $582^{*}$ | $1132$
| 14 | $114^{*}$ | $112^{*}$ | $\textbf{74}^{*}$ | $80^{*}$ | $130$
31 | 10 | $20838$ | $20738$ | 8651 | - | $22296$
| 12 | $1781^{*}$ | $1763^{*}$ | $\textbf{1024}^{*}$ | $\textbf{1024}^{*}$ | $1840^{*}$
| 14 | $196$ | $196$ | $\textbf{110}^{*}$ | $115^{*}$ | $196$
32 | 12 | $3082^{*}$ | $3082^{*}$ | $\textbf{2048}^{*}$ | $\textbf{2048}^{*}$ | $3082^{*}$
| 14 | $314$ | $313$ | $\textbf{187}^{*}$ | $191^{*}$ | $315$
| 16 | $\textbf{64}^{*}$ | $\textbf{64}^{*}$ | $\textbf{64}^{*}$ | $\textbf{64}^{*}$ | $\textbf{64}^{*}$
33 | 12 | $5821$ | $5821$ | $\textbf{2903}^{*}$ | $3037^{*}$ | $5821$
| 14 | $617$ | $612$ | $\textbf{310}^{*}$ | $324^{*}$ | $629$
| 16 | $80^{*}$ | $82^{*}$ | $65^{*}$ | $\textbf{64}^{*}$ | $99^{*}$
34 | 12 | $10878$ | $10671$ | - | $\textbf{5726}^{*}$ | $11641$
| 14 | $1195$ | $1203$ | $\textbf{510}^{*}$ | $568$ | $1258$
| 16 | $124^{*}$ | $120^{*}$ | $\textbf{99}^{*}$ | $103^{*}$ | $144$
35 | 12 | $20011$ | $19810$ | - | 10603 | $21727$
| 14 | $1774$ | $1759$ | $\textbf{890}^{*}$ | $989^{*}$ | $2026$
| 16 | $215^{*}$ | $215^{*}$ | $172^{*}$ | $\textbf{169}^{*}$ | $215^{*}$
36 | 14 | - | - | $\textbf{1664}^{*}$ | $1786^{*}$ | $3177$
| 16 | $352^{*}$ | $352^{*}$ | $\textbf{256}^{*}$ | $\textbf{256}^{*}$ | $352^{*}$
| 18 | $72$ | $72$ | 40 | 40 | $72$
37 | 16 | $704$ | $704$ | $\textbf{366}^{*}$ | - | $704$
38 | 14 | - | $10211$ | - | $\textbf{5348}^{*}$ | $10211$
39 | 16 | $1905$ | $1918$ | 1138 | 1138 | $2271$
40 | 16 | $3493$ | $3488$ | - | 2276 | $3510$