Slight extension of cross posting from https://cstheory.stackexchange.com/questions/7408/lee-metric-gilbert-varshamov-and-hamming-bounds-for-larger-relative-distance-rang (closed there)

The following link provides a Gilbert-Varshamov lower bound and a Hamming upper bound for the Lee metric when the distance between codewords is smaller than the length of the code (captured by $r = \delta n$ where $0 \le \delta \le 0.37$ in the paper).


Consider the alphabet is of form $2k + 1$ where $k$ is any non-negative integer.

Is there a reference which provides the corresponding lower/upper bound for ranges above this? Atleast is there a lower bound (preferably as powerful as the Gilbert-Varshamov bound) and a upper bound(preferably tighter than the Hamming bound) for the case $\frac{2 \delta n + 1}{n} = \frac{n + 1}{n}$, that is $\delta = \frac{1}{2}$?

Are there any constructive techniques known for the case $\delta = 0.5$ for all/any even/any odd $n$ to build good codes?

Are there any spectral/fourier analytic/algebraic geometric techniques that has studied this problem? In particular are there connections to domino tiling that are studied anywhere?

  • $\begingroup$ Algebraic Geometry codes over rings (such as $\mathbb{Z}/4$) give codes for the Lee metric. These were first studied in J. Walker's PhD thesis and a number of papers after that. I don't recall seeing asymptotic results, though. $\endgroup$ – Felipe Voloch Jul 17 '11 at 0:55
  • $\begingroup$ @Felipe I forgot the alphabet constraint. Let me add that as well. $\endgroup$ – user16007 Jul 17 '11 at 1:16
  • $\begingroup$ @Felipe After reading through some portions(of what I understand) of the paper "Euclidean weights of codes from elliptic curves over rings" by yourself and Judy walker, there seems to be a straight forward connection between euclidean and lee distance. It is well known euclidean distances is connected to lattice codes or shells of lattice codes. If we know bounds on densities of lattices would that not provide some kind of hint to lee distance bounds for odd alphabets? I may be mistaken. But your response is very welcome. Thankyou:)!!!! $\endgroup$ – user16007 Jul 17 '11 at 3:36
  • $\begingroup$ @Felipe I am not a topologist. So I am asking this question. Is there a connection between $n$-tori and codes of length $n$ over $\mathbb{Z}/q$? $\endgroup$ – user16007 Jul 17 '11 at 3:53
  • $\begingroup$ @unknown (yahoo) re: n-tori. I have no idea. $\endgroup$ – Felipe Voloch Jul 17 '11 at 9:47

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.