2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ What is $A_q(n,3)$? $\endgroup$ – Emil Jeřábek Feb 21 '18 at 11:31
  • $\begingroup$ 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 $\endgroup$ – Max Hopkins Feb 21 '18 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.