index.html 16.3 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213
<!DOCTYPE html>

  <meta charset="utf-8">
  <meta content="IE=edge" http-equiv="X-UA-Compatible">
  <title>Scientific math paper</title>
  <meta content="width=device-width, initial-scale=1" name="viewport">


  <script type="text/x-mathjax-config">
      tex2jax: {
        inlineMath: [ ['$','$'], ["\\(","\\)"] ],
        processEscapes: true

  <script src=""></script>

    window.PagedConfig = {
      auto: false
  <script src=""></script>
    MathJax.Hub.Queue(function () {

<!-- <link rel="stylesheet" href="fonts/ibm-plex-sans/stylesheet.css" /> -->
<!-- <link rel="stylesheet" href="fonts/ibm-plex-serif/stylesheet.css" /> -->
<link rel="stylesheet" href="fonts/spectral/stylesheet.css" />

<link rel="stylesheet" href="style.css" />



        <h1>An explicit formula for a weight enumerator of linear-congruence codes</h1>
        <p id="authors">Taro Sakurai</p>

        <p class="abstract">An explicit formula for a weight enumerator of linear-congruence codes is provided. This extends the work of Bibak and Milenkovic [IEEE ISIT (2018) 431–435] addressing the binary case to the non-binary case. Furthermore, the extension simplifies their proof and provides a complete solution to a problem posed by them.</p>
        <p class="keywords">weight enumerator, code size, linear-congruence code, exponential sum</p>
        <p class="date">August 29, 2018.</p>
        <p class="math-class">2010 Mathematics Subject Classification: <span>94B60 (05A15, 11L15)</span></p>
        <p class="source">Source: <span></span></p>

<h2 id="introduction" class="unnumbered unnumbered">Introduction</h2>
<p> Throughout this article, <span class="math inline"><em>n</em></span> and <span class="math inline"><em>m</em></span> denote positive integers, <span class="math inline"><em>b</em></span> denotes an integer and <span class="math inline">$\mathbb{Z}_q &#x2254; \{0, 1, \dotsc, q-1\} \subset \mathbb{Z}$</span> for a positive integer <span class="math inline"><em>q</em></span>. We will use <span class="math inline"><em>n</em></span> for a code length, <span class="math inline"><em>m</em></span> for a modulus, <span class="math inline"><em>b</em></span> for a defining parameter of a code and <span class="math inline"><sub><em>q</em></sub></span> for a code alphabet.</p>
<p>Let <span class="math inline">$a = (a_1, \dotsc, a_n) \in \mathbb{Z}^n$</span> and <span class="math inline"><em>b</em> ∈ ℤ</span>. The set <span class="math inline"><em>C</em></span> of all the solutions <span class="math inline">$x = (x_1, \dotsc, x_n) \in \mathbb{Z}_q^n$</span> for a linear congruence equation <span class="math display num">$$\label{eq: ax = b}
        a\cdot x \equiv b \pmod m$$</span> is said to be a <em>linear-congruence code</em> where <span class="math inline">$a\cdot x &#x2254; a_1x_1 + \dotsb + a_nx_n$</span>. A linear-congruence code <span class="math inline"><em>C</em></span> is called <em>binary</em> when <span class="math inline"><em>q</em> = 2</span>.</p>

<p>Several deletion-correcting codes which have been studied are linear-congruence codes; the Varshamov-Tenengol’ts codes <span class="citation" data-cites="VT65"></span>, the Levenshtein codes <span class="citation" data-cites="Lev66"></span>, the Helberg codes <span class="citation" data-cites="HF02"></span>, the Le-Nguyen codes <span class="citation" data-cites="LN16"></span>, the construction <span class="math inline"><em>C</em></span> of Hagiwara <span class="citation" data-cites="Hag17"></span> (for some parameters), the consecutively systematic encodable codes and the ternary integer codes in <span class="citation" data-cites="Hag16"></span> fall into this category (Table).</p>

<caption>Examples of linear-congruence codes</caption>
<tr class="header">
<th style="text-align: left;">Linear-congruence code</th>
<th style="text-align: right;"><span class="math inline"><em>q</em></span></th>
<th style="text-align: right;"><span class="math inline">$(a_1, \dotsc, a_n)$</span></th>
<th style="text-align: right;"><span class="math inline"><em>m</em></span></th>
<th style="text-align: left;">Constraints</th>
<tr class="odd">
<td style="text-align: left;">Varshamov-Tenengol’ts code</td>
<td style="text-align: right;"><span class="math inline">2</span></td>
<td style="text-align: right;"><span class="math inline">$(  1, \dotsc,   n)$</span></td>
<td style="text-align: right;"><span class="math inline"><em>n</em> + 1</span></td>
<td style="text-align: left;"></td>
<tr class="even">
<td style="text-align: left;">Levenshtein code</td>
<td style="text-align: right;"><span class="math inline">2</span></td>
<td style="text-align: right;"><span class="math inline">$(  1, \dotsc,   n)$</span></td>
<td style="text-align: right;"><span class="math inline"><em>m</em></span></td>
<td style="text-align: left;"><span class="math inline"><em>m</em> ≥ <em>n</em> + 1</span></td>
<tr class="odd">
<td style="text-align: left;">Helberg code</td>
<td style="text-align: right;"><span class="math inline">2</span></td>
<td style="text-align: right;"><span class="math inline">$(v_1, \dotsc, v_n)$</span></td>
<td style="text-align: right;"><span class="math inline"><em>v</em><sub><em>n</em> + 1</sub></span></td>
<td style="text-align: left;"><span class="math inline"><em>s</em> ∈ ℤ<sub>&gt; 0</sub></span></td>
<tr class="even">
<td style="text-align: left;">Le-Nguyen code</td>
<td style="text-align: right;"><span class="math inline"><em>q</em></span></td>
<td style="text-align: right;"><span class="math inline">$(w_1, \dotsc, w_n)$</span></td>
<td style="text-align: right;"><span class="math inline"><em>m</em></span></td>
<td style="text-align: left;"><span class="math inline"><em>m</em> ≥ <em>w</em><sub><em>n</em> + 1</sub></span>, <span class="math inline"><em>s</em> ∈ ℤ<sub>&gt; 0</sub></span></td>
<tr class="odd">
<td style="text-align: left;">Construction <span class="math inline"><em>C</em></span></td>
<td style="text-align: right;"><span class="math inline">2</span></td>
<td style="text-align: right;"><span class="math inline">$(c_1, \dotsc, c_n)$</span></td>
<td style="text-align: right;"><span class="math inline"><em>n</em></span></td>
<td style="text-align: left;"><span class="math inline">$b \not\equiv 0, n(n+1)/2 \pmod n$</span></td>
<tr class="even">
<td style="text-align: left;">Consecutively systematic encodable codes</td>
<td style="text-align: right;"><span class="math inline">2</span></td>
<td style="text-align: right;"><span class="math inline">$(b_1, \dotsc, b_n)$</span></td>
<td style="text-align: right;"><span class="math inline">2<sup><em>s</em> + 1</sup></span></td>
<td style="text-align: left;"><span class="math inline"><em>b</em> = 0</span>, <span class="math inline"><em>s</em> ∈ ℤ<sub>&gt; 0</sub></span>, <span class="math inline">0 &lt;<em>n</em> − <em>s</em>&lt; 2<sup><em>s</em> − 1</sup></span></td>
<tr class="odd">
<td style="text-align: left;">Ternary integer code</td>
<td style="text-align: right;"><span class="math inline">3</span></td>
<td style="text-align: right;"><span class="math inline">$(t_1, \dotsc, t_n)$</span></td>
<td style="text-align: right;"><span class="math inline">2<sup><em>n</em> + 1</sup> − 1</span></td>
<td style="text-align: left;"></td>

<p>The following problem concerning the size of a linear-congruence code—the number of solutions for a linear congruence equation <a href="#eq: ax = b" data-reference-type="eqref" data-reference="eq: ax = b">[eq: ax = b]</a>—is posed by Bibak and Milenkovic.</p>


<p>Give an explicit formula for the size of a linear-congruence code.</p>
<p>Finding an explicit formula would be a first step toward understanding the asymptotic behavior of the size of a linear-congruence code. Bibak and Milenkovic provide a solution to the problem for the binary case. In this article, we provide a complete solution to the problem with a simple proof, which improves the argument of Bibak and Milenkovic. Actually, what we will show is how the Hamming weights of the solutions for a linear congruence equation distribute. This immediately gives an expression of the size of a linear-congruence code involving exponential sums—Weyl sums of degree one.</p>
<p>To state the main theorem we need notation which will be standard.</p>

<p>For a code <span class="math inline"><em>C</em> ⊆ ℤ<sub><em>q</em></sub><sup><em>n</em></sup></span>, we define a polynomial <span class="math inline"><em>W</em><sub><em>C</em></sub>(<em>z</em>)</span> by <!--<br />--><span class="math display">$$W_C(z)
        = \sum_{x \in C} z^{wt(x)}
        = \sum_{i=0}^n A_i(C) z^i,$$</span><!--<br />--> where <span class="math inline">$wt(x)$</span> denotes the Hamming weight and <!--<br />--><span class="math display">$$A_i(C) &#x2254; |{ x \in C : wt(x) = i }\rvert \qquad (0 \leq i \leq n).$$</span><!--<br />--> The polynomial <span class="math inline"><em>W</em><sub><em>C</em></sub>(<em>z</em>)</span> is said to be the (non-homogeneous) <em>weight enumerator</em> of the code <span class="math inline"><em>C</em></span>.</p>
<p>Following custom due to Vinogradov in additive number theory, <span class="math inline"><em>e</em>(<em>α</em>)</span> denotes <span class="math inline">$e^{2\pi\alpha\sqrt{-1}}$</span> for <span class="math inline"><em>α</em> ∈ ℝ</span>. Now we are in position to state our main theorem.</p>
<h3 class="break-before">Theorem</h3>
<p>Let <span class="math inline">$a = (a_1, \dotsc, a_n) \in \mathbb{Z}^n$</span> and <span class="math inline"><em>b</em> ∈ ℤ</span>. Then the weight enumerator <span class="math inline"><em>W</em><sub><em>C</em></sub>(<em>z</em>)</span> of the linear-congruence code <span class="math display num">$$\label{eq: LCC}
        C = { x \in \mathbb{Z}_q^n : a\cdot x \equiv b \pmod m }$$</span><!--<br />--> is given by <span class="num math display">$$W_C(z) =
        \frac{1}{m}\sum_{j=1}^m e\left(-\frac{jb}{m}\right)
            \prod_{i=1}^n\left(1 + ze\left(\frac{ja_i}{m}\right) + \dotsb + ze\left(\frac{ja_i(q-1)}{m}\right)\right).$$</span><!--<br />--></p>
<p>With the same notation as above, the size of the code <span class="math inline"><em>C</em></span> is given by <!--<br />--><span class="math display">$$\lvert C\rvert =
        \frac{1}{m}\sum_{j=1}^m e\left(-\frac{jb}{m}\right)
            \prod_{i=1}^n\left(1 + e\left(\frac{ja_i}{m}\right) + \dotsb + e\left(\frac{ja_i(q-1)}{m}\right)\right).$$</span><!--<br />--></p>
<h2 id="proof-of-theorem" class="unnumbered unnumbered">Proof of Theorem</h2>
<p>The only lemma we need to prove the main theorem is the following trivial one.</p>
<p><!--<br />--><span class="math display">$$\frac{1}{m}\sum_{j=1}^m e\left(\frac{jb}{m}\right)
        = \begin{cases}
            1 &amp; \mathrm{if   } \ b     \equiv 0 \pmod m  \\
            0 &amp; \mathrm{if  } \ b \not\equiv 0 \pmod m .
        \end{cases}$$</span><!--<br />--></p>
<p>The proof is straightforward: <!--<br />--><span class="math display">$$\begin{aligned}
        &amp;\frac{1}{m}\sum_{j=1}^m e\left(-\frac{jb}{m}\right)
            \prod_{i=1}^n\left(1 + ze\left(\frac{ja_i}{m}\right) + \dotsb + ze\left(\frac{ja_i(q-1)}{m}\right)\right) \\
        \frac{1}{m}\sum_{j=1}^m e\left(-\frac{jb}{m}\right)
            \prod_{i=1}^n \sum_{x_i \in \mathbb{Z}_q} z^{wt(x_i)}e\left(\frac{ja_ix_i}{m}\right) \\
        \frac{1}{m}\sum_{j=1}^m e\left(-\frac{jb}{m}\right)
            \sum_{(x_1, \dotsc, x_n) \in \mathbb{Z}_q^n} \prod_{i=1}^n z^{wt(x_i)}e\left(\frac{ja_i x_i}{m}\right) \\
        \frac{1}{m}\sum_{j=1}^m e\left(-\frac{jb}{m}\right)
            \sum_{x \in \mathbb{Z}_q^n} z^{wt(x)}e\left(\frac{ja\cdot x}{m}\right) \\
        \sum_{x \in \mathbb{Z}_q^n}
                e\left(\frac{j(a\cdot x - b)}{m}\right) \right)
                     z^{wt(x)} \\
        \sum_{x \in C}z^{wt(x)} \qquad (\text{By Lemma.}) \\
        &amp;\qquad= W_C(z).

    \end{aligned}$$</span><br /></p>
<p>The original proof by Bibak and Milenkovic <span class="citation" data-cites="BM18"></span> for the binary case uses a theorem of Lehmer <span class="citation" data-cites="Leh23"></span>, which states a linear congruence equation <!--<br />--><span class="math display">$$a\cdot x \equiv b \pmod m$$</span><!--<br />--> defined by <span class="math inline">$a = (a_1, \dotsc, a_n) \in \mathbb{Z}^n$</span> and <span class="math inline"><em>b</em> ∈ ℤ</span> has a solution <span class="math inline"><em>x</em> ∈ ℤ<sub><em>m</em></sub><sup><em>n</em></sup></span> if and only if <span class="math inline">$\gcd(a_1, \dotsc, a_n, m)$</span> divides <span class="math inline"><em>b</em></span>. Consequently, their result is stated depending on whether <span class="math inline">$\gcd(a_1, \dotsc, a_n, m)$</span> divides <span class="math inline"><em>b</em></span> or not. By contrast, our result does not refer to <span class="math inline">$\gcd(a_1, \dotsc, a_n, m)$</span> because our proof does not rely on the Lehmer theorem.</p>
<h2 id="acknowledgments" class="unnumbered unnumbered">Acknowledgments</h2>
<p>The author thanks Professor Manabu Hagiwara for drawing the author’s attention to the work of Bibak and Milenkovic and his invaluable help during the preparation of this article. This work is partially supported by KAKENHI(B) 18H01435, 16K12391 and 16K06336.</p>

<section id="references">
<h2 class="unnumbered unnumbered">References</h2>

<p>K. Bibak and O. Milenkovic, Weight enumerators of some classes of deletion correcting codes, <em>IEEE ISIT</em> (2018) 431–435, doi:<a href="">10.1109/ISIT.2018.8437121</a>.</p>

<p>M. Hagiwara, On ordered syndromes for multi insertion/deletion error-correcting codes, <em>IEEE ISIT</em> (2016) 625–629, doi:<a href="">10.1109/ISIT.2016.7541374</a>.</p>

<p>Perfect codes for single balanced adjacent deletions, <em>IEEE ISIT</em> (2017) 1938–1942, doi:<a href="">10.1109/ISIT.2017.8006867</a>.</p>

<p>A. S. J. Helberg and H. C. Ferreira, On multiple insertion/deletion correcting codes, <em>IEEE Trans. Inf. Theory</em> <strong>48</strong> (2002) 305–308, doi:<a href="">10.1109/18.971760</a>. MR <a href="">1872185</a> Zbl <a href="">1059.94040</a></p>

<p>T. A. Le and H. D. Nguyen, New multiple insertion/deletion correcting codes for non-binary alphabets, <em>IEEE Trans. Inform. Theory</em> <strong>62</strong> (2016), 2682–2693, doi:<a href="">10.1109/TIT.2016.2541139</a>. MR <a href="">3493869</a> Zbl <a href="">1359.94714</a></p>

<p>D. N. Lehmer, Certain theorems in the theory of quadratic residues, <em>Amer. Math. Monthly</em> <strong>20</strong> (1913) 151–157, doi:<a href="">10.2307/2972413</a>. MR <a href="">1517830</a> Zbl <a href="">44.0248.09</a></p>

<p>V. I. Levenshtein, <a href="">Binary codes capable of correcting deletions, insertions, and reversals</a>, <em>Soviet Physics Dokl.</em> <strong>10</strong> (1966) 707–710. MR <a href="">189928</a> Zbl <a href="">0149.15905</a></p>

<p>R. R. Varshamov and G. M. Tenengol’ts, <a href="">Code correcting single asymmetric errors</a>, <em>Avtomat. i Telemeh.</em> <strong>26</strong> (1965) 288–292. MR <a href="">172738</a></p>