Optimality conjecture for Levenshtein-bound refinements

About 8 years old · traced to

Let q≥3q\geq 3 be fixed. Let sqs_q be a constant, let s∈[−1,sq)∩Tns\in[-1,s_q)\cap T_n, and interpret s∈Tns\in T_n in the setting of the paper's code bounds, with d/n=(1−s)/2d/n=(1-s)/2. Theorem 1 provides the relevant upper bound and the paper's refinements are the bounds being compared.

Optimality conjecture. There exists a constant sqs_q such that whenever s∈[−1,sq)∩Tns\in[-1,s_q)\cap T_n, the refinements described above are the best bounds that can be obtained from Theorem 1.

The conjecture asserts asymptotic-range optimality of the proposed refinements for sufficiently large relative distance. The supplied passage gives computational and comparative evidence but no resolution, so the conjecture remains open.

References

Primary source

Peter Boyvalenkov, Danyo Danev and Maya Stoyanova, “Refinements of Levenshtein bounds in q-ary Hamming spaces”, arXiv:1801.01982 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.