Monotonicity conjecture for the asymptotic code rate

At least 8 years old · documented by

Let q>2q>2 and let θ=1−1/q\theta=1-1/q. For xx in the relevant relative-distance range, write α(x)=lim⁡n→∞n−1log⁡qAq(n,xn)\alpha(x)=\lim_{n\to\infty}n^{-1}\log_q A_q(n,xn), where Aq(n,d)A_q(n,d) is the maximum size of a qq-ary code of length nn and minimum Hamming distance at least dd. Monotonicity conjecture. The function

α(x)θ−x\frac{\alpha(x)}{\theta-x}

is decreasing. Equivalently,

α(tx+(1−t)θ)≤tα(x)+(1−t)α(θ),t∈[0,1].\alpha(tx+(1-t)\theta)\leq t\alpha(x)+(1-t)\alpha(\theta),\qquad t\in[0,1].

The conjecture is proposed as a weaker alternative to the unproved assertion that α(x)\alpha(x) is cup-convex. The preceding hybrid Elias–Plotkin bound has the same relevant convexity and differentiability features, but it is not known whether the asserted monotonicity holds for the asymptotic rate function itself.

References

Primary source

Krishna Kaipa, “An improvement of the asymptotic Elias bound for non-binary codes”, arXiv:1705.07785 (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.