<p>In this paper, we study the largest size <i>A</i>(<i>n</i>,&#xa0;<i>d</i>) of permutation codes of length <i>n</i>, i.e., subsets of the set <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_809_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="20" /> </InlineMediaObject> <EquationSource Format="TEX">\(S_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> of all permutations on <i>n</i> letters with the minimum distance at least <i>d</i> under the Hamming metric. In Abdollahi et al. (Cryptogr. Commun. <b>15</b>, 891–903 <CitationRef CitationID="CR2">2023</CitationRef>) we have developed a method using the representation theory of symmetric groups to find upper bounds on the size of permutation codes in <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_809_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="20" /> </InlineMediaObject> <EquationSource Format="TEX">\(S_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> with the minimum distance of <i>d</i> under the Kendall <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_809_Article_IEq3.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="11" /> </InlineMediaObject> <EquationSource Format="TEX">\(\tau \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>τ</mi> </math></EquationSource> </InlineEquation>-metric. The latter method is used for the permutation codes under the metric induced by Cayley graphs of <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_809_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="20" /> </InlineMediaObject> <EquationSource Format="TEX">\(S_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation>. Since the metric induced by any Cayley graph of <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_809_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="20" /> </InlineMediaObject> <EquationSource Format="TEX">\(S_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> is not equivalent to the Hamming metric, we can not use the method for the Hamming metric. In this paper we find a trick by which we can again use the method to find upper bounds for <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_809_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="86" /> </InlineMediaObject> <EquationSource Format="TEX">\(A(n, 2t+1)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>A</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mn>2</mn> <mi>t</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. We present three practical results that prove the non-existence of perfect 2-error-correcting codes in <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_809_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="20" /> </InlineMediaObject> <EquationSource Format="TEX">\(S_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> under the Hamming metric for numerous values of <i>n</i>. Specifically, we prove that 91 and 907 are the only values for <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_809_Article_IEq8.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="66" /> </InlineMediaObject> <EquationSource Format="TEX">\(n \le 1000\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≤</mo> <mn>1000</mn> </mrow> </math></EquationSource> </InlineEquation> for which <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_809_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="20" /> </InlineMediaObject> <EquationSource Format="TEX">\(S_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> may contain a perfect 2-error-correcting code under the Hamming metric. Additionally, we prove that for any integer <i>n</i> such that <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_809_Article_IEq10.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="77" /> </InlineMediaObject> <EquationSource Format="TEX">\(n^2 - n + 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo>-</mo> <mi>n</mi> <mo>+</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> is divisible by a prime exceeding <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_809_Article_IEq11.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="61" /> </InlineMediaObject> <EquationSource Format="TEX">\(n-\lfloor \frac{n}{7}\rfloor \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>-</mo> <mo>⌊</mo> <mfrac> <mi>n</mi> <mn>7</mn> </mfrac> <mo>⌋</mo> </mrow> </math></EquationSource> </InlineEquation>, <Equation ID="Equ10"> <MediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_809_Article_Equ10.gif" Format="GIF" Height="53" Rendition="HTML" Resolution="72" Type="Linedraw" Width="530" /> </MediaObject> <EquationSource Format="TEX">\( A(n,5)\le \frac{2\times n!}{n^2-n+2}-\dfrac{20n-56}{(n^2-n+2)\sqrt{698n^2-1428n+1274}}\sqrt{\dfrac{n!}{(n-\lfloor \frac{n}{7}\rfloor )!}}. \)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mi>A</mi> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mn>5</mn> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mfrac> <mrow> <mn>2</mn> <mo>×</mo> <mi>n</mi> <mo>!</mo> </mrow> <mrow> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo>-</mo> <mi>n</mi> <mo>+</mo> <mn>2</mn> </mrow> </mfrac> <mo>-</mo> <mstyle displaystyle="true" scriptlevel="0"> <mfrac> <mrow> <mn>20</mn> <mi>n</mi> <mo>-</mo> <mn>56</mn> </mrow> <mrow> <mrow> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo>-</mo> <mi>n</mi> <mo>+</mo> <mn>2</mn> <mo stretchy="false">)</mo> </mrow> <msqrt> <mrow> <mn>698</mn> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo>-</mo> <mn>1428</mn> <mi>n</mi> <mo>+</mo> <mn>1274</mn> </mrow> </msqrt> </mrow> </mfrac> </mstyle> <msqrt> <mstyle displaystyle="true" scriptlevel="0"> <mfrac> <mrow> <mi>n</mi> <mo>!</mo> </mrow> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>-</mo> <mrow> <mo>⌊</mo> <mfrac> <mi>n</mi> <mn>7</mn> </mfrac> <mo>⌋</mo> </mrow> <mo stretchy="false">)</mo> <mo>!</mo> </mrow> </mfrac> </mstyle> </msqrt> <mo>.</mo> </mrow> </math></EquationSource> </Equation>The result improves the known upper bounds of <i>A</i>(<i>n</i>,&#xa0;5) for all integers <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_809_Article_IEq12.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">\(n \ge 35\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>35</mn> </mrow> </math></EquationSource> </InlineEquation> such that <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_809_Article_IEq10.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="77" /> </InlineMediaObject> <EquationSource Format="TEX">\(n^2 - n + 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo>-</mo> <mi>n</mi> <mo>+</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> is divisible by a prime exceeding <InlineEquation ID="IEq14"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_809_Article_IEq11.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="61" /> </InlineMediaObject> <EquationSource Format="TEX">\(n-\lfloor \frac{n}{7}\rfloor \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>-</mo> <mo>⌊</mo> <mfrac> <mi>n</mi> <mn>7</mn> </mfrac> <mo>⌋</mo> </mrow> </math></EquationSource> </InlineEquation>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Upper bounds on the size of permutation codes with a Hamming distance of five

  • Alireza Abdollahi,
  • Javad Bagherian,
  • Fatemeh Jafari,
  • Maryam Khatami,
  • Farzad Parvaresh,
  • Reza Sobhani

摘要

In this paper, we study the largest size A(nd) of permutation codes of length n, i.e., subsets of the set \(S_n\) S n of all permutations on n letters with the minimum distance at least d under the Hamming metric. In Abdollahi et al. (Cryptogr. Commun. 15, 891–903 2023) we have developed a method using the representation theory of symmetric groups to find upper bounds on the size of permutation codes in \(S_n\) S n with the minimum distance of d under the Kendall \(\tau \) τ -metric. The latter method is used for the permutation codes under the metric induced by Cayley graphs of \(S_n\) S n . Since the metric induced by any Cayley graph of \(S_n\) S n is not equivalent to the Hamming metric, we can not use the method for the Hamming metric. In this paper we find a trick by which we can again use the method to find upper bounds for \(A(n, 2t+1)\) A ( n , 2 t + 1 ) . We present three practical results that prove the non-existence of perfect 2-error-correcting codes in \(S_n\) S n under the Hamming metric for numerous values of n. Specifically, we prove that 91 and 907 are the only values for \(n \le 1000\) n 1000 for which \(S_n\) S n may contain a perfect 2-error-correcting code under the Hamming metric. Additionally, we prove that for any integer n such that \(n^2 - n + 2\) n 2 - n + 2 is divisible by a prime exceeding \(n-\lfloor \frac{n}{7}\rfloor \) n - n 7 , \( A(n,5)\le \frac{2\times n!}{n^2-n+2}-\dfrac{20n-56}{(n^2-n+2)\sqrt{698n^2-1428n+1274}}\sqrt{\dfrac{n!}{(n-\lfloor \frac{n}{7}\rfloor )!}}. \) A ( n , 5 ) 2 × n ! n 2 - n + 2 - 20 n - 56 ( n 2 - n + 2 ) 698 n 2 - 1428 n + 1274 n ! ( n - n 7 ) ! . The result improves the known upper bounds of A(n, 5) for all integers \(n \ge 35\) n 35 such that \(n^2 - n + 2\) n 2 - n + 2 is divisible by a prime exceeding \(n-\lfloor \frac{n}{7}\rfloor \) n - n 7 .