5
$\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 on the TCS SE here: https://cstheory.stackexchange.com/questions/40238/explicit-formula-of-delsartes-linear-programming-upper-bound-for-a-qn-3 The results on $A_q(n,d)$ are often published in top combinatorics journals (Journal of Combinatorial Theory, Series A, for instance), and so I think it is appropriate and hopefully of interest to MO users as well.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The paper "Some upper bounds for codes derived from Delsarte's inequalities for Hamming schemes" by C. Roos and C. de Vroedt does give a formula for Delsarte's bound. Or at least according to Mathematical Reviews it provides such a formula. I too was unable to locate the paper, but I did find the MR which states the following formula for the bound denoted by $D(n,3,q)$.

$$D(n,3,q) = q^n\frac{\lambda n - a(q-a)}{(\lambda n + a)(\lambda n + a - q)}$$

Where $\lambda = q-1$, $n \equiv a \pmod q$, and $1 \leq a \leq q$. The formula is said to hold for $q > 2$ and $n$ sufficiently large.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Any chance you could link to the MR? Also should the denominator include both terms? $\endgroup$
    – Max Hopkins
    Feb 22, 2018 at 3:24
  • 1
    $\begingroup$ @MaxHopkins Here is the MR link mathscinet.ams.org/mathscinet-getitem?mr=484738 $\endgroup$
    – j.c.
    Feb 22, 2018 at 13:47
  • 2
    $\begingroup$ @MaxHopkins I see j.c. has provided a link. If you are able to get past the paywall you will see I try to write the bound exactly as in the MR. But I think you edit is better. After all the bound better be less than $q^n$ :) $\endgroup$
    – John Machacek
    Feb 22, 2018 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.