<p>The problem of giving an explicit formula for $A_q(n,d)$ is sometimes referred to as "the main problem in coding theory." The value of $A_q(n,d)$ is given by the maximum number of codewords in a q-ary code of length $n$ and distance $d$. More specifically, let the hamming weight of an element of $\mathbb{F}_q^n$ be its $l_0$-pseudonorm, the number of non-zero components, and the hamming distance between two elements $f,g$ the weight of their difference $d(f,g)$. Then $A_q(n,d)$ is the largest set $S \subset F_q^n$ s.t. for two elements $f,g \in S$, $d(f,g)\geq d$.</p>

<p>There are a number of famous upper bounds on $A_q(n,d)$, including Hamming's sphere packing bound. The best are given by a linear programming approach (now improved to a semi-definite programming approach) given by Delsarte in the late 70s. I have recently been searching for an explicit formula for Delsarte's Linear Programming Upper Bound for $A_q(n,3)$ in the literature, which correspond to single error correcting codes, and have not had much luck for non-binary codes. For binary codes this appears to be well known, and shown as early as 1977 by Best and Brouwer. </p>

<p>Non-binary codes seem to be a completely different story. There is a paper called "Some upper bounds for codes derived from Delsartes inequalities for
Hamming schemes" by C. Roos and C. de Vroedt, which the authors claim deals with the q-ary case, but I have not been able to find a copy. There appears to have been a very large amount of work in this field so I would be shocked if no such formula exists (well, at least a formula for some special cases of n,q).</p>

<p>Is there a body of work in this area I am missing? Do such formulae exist? </p>

<p>Note: I have also posted this question to MO, since I think $A_q(n,d)$ has received significant attention from both communities. The link is: <a href="https://mathoverflow.net/questions/293549/explicit-formula-of-delsartes-linear-programming-upper-bound-for-a-qn-3">https://mathoverflow.net/questions/293549/explicit-formula-of-delsartes-linear-programming-upper-bound-for-a-qn-3</a></p>

CC BY-SA 3.0
2018-02-21T11:31:12.110Z
What is $A_q(n,3)$?
Emil Jeřábek
CC BY-SA 3.0
2018-02-21T14:21:11.440Z
The maximum number of codewords in a q-ary code of length n (i.e. codewords are elements of $\mathbb{F}_q^n$) of distance 3. I will update the post to reflect the definition
Max Hopkins
<linear-programming><coding-theory><upper-bounds>
Explicit Formula of Delsarte's Linear Programming Upper Bound for $A_q(n,3)$
Max Hopkins
# Explicit Formula of Delsarte's Linear Programming Upper Bound for $A_q(n,3)$

(Asked by: username_0 on 2018-02-21)

The problem of giving an explicit formula for $A\_q(n,d)$ is sometimes referred to as "the main problem in coding theory." The value of $A\_q(n,d)$ is given by the maximum number of codewords in a q-ary code of length $n$ and distance $d$. More specifically, let the hamming weight of an element of $\mathbb{F}\_q^n$ be its $l\_0$-pseudonorm, the number of non-zero components, and the hamming distance between two elements $f,g$ the weight of their difference $d(f,g)$. Then $A\_q(n,d)$ is the largest set $S \subset F\_q^n$ s.t. for two elements $f,g \in S$, $d(f,g)\geq d$.

There are a number of famous upper bounds on $A\_q(n,d)$, including Hamming's sphere packing bound. The best are given by a linear programming approach (now improved to a semi-definite programming approach) given by Delsarte in the late 70s. I have recently been searching for an explicit formula for Delsarte's Linear Programming Upper Bound for $A\_q(n,3)$ in the literature, which correspond to single error correcting codes, and have not had much luck for non-binary codes. For binary codes this appears to be well known, and shown as early as 1977 by Best and Brouwer.

Non-binary codes seem to be a completely different story. There is a paper called "Some upper bounds for codes derived from Delsartes inequalities for
Hamming schemes" by C. Roos and C. de Vroedt, which the authors claim deals with the q-ary case, but I have not been able to find a copy. There appears to have been a very large amount of work in this field so I would be shocked if no such formula exists (well, at least a formula for some special cases of n,q).

Is there a body of work in this area I am missing? Do such formulae exist?

Note: I have also posted this question to MO, since I think $A\_q(n,d)$ has received significant attention from both communities. The link is: <https://mathoverflow.net/questions/293549/explicit-formula-of-delsartes-linear-programming-upper-bound-for-a-qn-3>

**Tags:** linear-programming, coding-theory, upper-bounds

> **Comments:**
> **username_1**: What is $A_q(n,3)$?  
> **username_0**: The maximum number of codewords in a q-ary code of length n (i.e. codewords are elements of $\mathbb{F}_q^n$) of distance 3. I will update the post to reflect the definition  

---

## 0 answers

