Proof of a conjecture of Kløve on permutation codes under the Chebychev distance

DOI10.1007/S10623-016-0255-YzbMATH Open1359.05004arXiv1704.01295OpenAlexW2486036536WikidataQ59516355 ScholiaQ59516355MaRDI QIDQ521871FDOQ521871

Authors: Victor J. W. Guo, Yiting Yang 

Publication date: 12 April 2017

Published in: Designs, Codes and Cryptography (Search for Journal in Brave)

Abstract: Let $d$ be a positive integer and $x$ a real number. Let $A_{d,x}$ be a $dimes2d$ matrix with its entries ${\displaystyle }$ a_{i,j}=left{ �egin{array}{ll} x & mbox{for} 1leqslant jleqslant d+1-i, 1 & mbox{for} d+2-ileqslant jleqslant d+i, 0 & mbox{for} d+1+ileqslant jleqslant 2d. end{array} ight. ${\displaystyle }$ Further, let $R_d$ be a set of sequences of integers as follows: ${\displaystyle }$R_d={( ho_1, ho_2,ldots, ho_d)|1leqslant ho_ileqslant d+i, 1leqslant i leqslant d, mbox{and} ho_r

eq ho_s mbox{for} r

eq s}.${\displaystyle }$ and define ${\displaystyle }$Omega_d(x)=sum_{ hoin R_d}a_{1, ho_1}a_{2, ho_2}ldots a_{d, ho_d}.${\displaystyle }$ In order to give a better bound on the size of spheres of permutation codes under the Chebychev distance, Kl{o}ve introduced the above function and conjectured that ${\displaystyle }$Omega_d(x)=sum_{m=0}^d{dchoose m}(m+1)^d(x-1)^{d-m}.${\displaystyle }$ In this paper, we settle down this conjecture positively.

Full work available at URL: https://arxiv.org/abs/1704.01295

Recommendations

• Bounds on permutation codes of distance four
• Upper bounds on permutation codes via linear programming
• On the minimal distance of a polynomial code
• Covering radius in the Hamming permutation space
• Permutation codes with specified packing radius

zbMATH Keywords

permanentpermutation codeChebychev distance

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Bounds on codes (94B65)

Cites Work

• The On-Line Encyclopedia of Integer Sequences
• Title not available (Why is that?)
• Lower bounds on the size of spheres of permutations under the Chebychev distance
• Permutation Arrays Under the Chebyshev Distance
• Bounds on the Size of Permutation Codes With the Kendall <inline-formula> <tex-math notation="LaTeX">$\tau $ </tex-math></inline-formula>-Metric
• Error-Correction in Flash Memories via Codes in the Ulam Metric
• Metrics on permutations, a survey
• Asymptotic Improvement of the Gilbert–Varshamov Bound on the Size of Binary Codes
• Codes in Permutations and Error Correction for Rank Modulation
• Correcting Charge-Constrained Errors in the Rank-Modulation Scheme

Cited In (1)

• A lower bound on permutation codes of distance \(n-1\)

Uses Software

• OEIS

This page was built for publication: Proof of a conjecture of Kløve on permutation codes under the Chebychev distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q521871)