forked from pagedjs/pagedjs
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmath.html
196 lines (166 loc) · 15.8 KB
/
math.html
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
<!DOCTYPE html>
<html>
<head>
<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">
MathJax.Hub.Config({
tex2jax: {
inlineMath: [ ['$','$'], ["\\(","\\)"] ],
processEscapes: true
}
});
</script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<script>
window.PagedConfig = {
auto: false
};
</script>
<script src="../dist/paged.polyfill.js"></script>
<script>
MathJax.Hub.Queue(function () {
window.PagedPolyfill.preview();
});
</script>
<style>
@page{
size: A4;
border: 1px solid black;
}
</style>
</head>
<body>
<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>Date: August 29, 2018.</p>
<p>2010 Mathematics Subject Classification: 94B60 (05A15, 11L15).</p>
<p>Keywords and phrases: weight enumerator, code size, linear-congruence code, exponential sum</p>
<p>Source: https://arxiv.org/abs/1808.09365v1</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 ≔ \{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 <br /><span class="math display">$$\label{eq: ax = b}
a\cdot x \equiv b \pmod m$$</span><br /> is said to be a <em>linear-congruence code</em> where <span class="math inline">$a\cdot x ≔ 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>
<table>
<caption>Examples of linear-congruence codes</caption>
<thead>
<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>
</thead>
<tbody>
<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>
<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>
<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> > 0</sub></span></td>
</tr>
<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> > 0</sub></span></td>
</tr>
<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>
<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> > 0</sub></span>, <span class="math inline">0 < <em>n</em> − <em>s</em> < 2<sup><em>s</em> − 1</sup></span></td>
</tr>
<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>
</tr>
</tbody>
</table>
<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) ≔ |{ 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>
<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 <br /><span class="math display">$$\label{eq: LCC}
C = { x \in \mathbb{Z}_q^n : a\cdot x \equiv b \pmod m }$$</span><br /> is given by <br /><span class="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 & \mathrm{if } \ b \equiv 0 \pmod m \\
0 & \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}
&\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) \\
&\qquad=
\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) \\
&\qquad=
\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) \\
&\qquad=
\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) \\
&\qquad=
\sum_{x \in \mathbb{Z}_q^n}
\left(\frac{1}{m}\sum_{j=1}^m
e\left(\frac{j(a\cdot x - b)}{m}\right) \right)
z^{wt(x)} \\
&\qquad=
\sum_{x \in C}z^{wt(x)} \qquad (\text{By Lemma.}) \\
&\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>
<p><span>99</span> K. Bibak and O. Milenkovic, Weight enumerators of some classes of deletion correcting codes, <em>IEEE ISIT</em> (2018) 431–435, doi:<a href="https://doi.org/10.1109/ISIT.2018.8437121">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="https://doi.org/10.1109/ISIT.2016.7541374">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="https://doi.org/10.1109/ISIT.2017.8006867">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="https://doi.org/10.1109/18.971760">10.1109/18.971760</a>. MR <a href="http://www.ams.org/mathscinet-getitem?mr=1872185">1872185</a> Zbl <a href="https://zbmath.org/?q=an:1059.94040">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="https://doi.org/10.1109/TIT.2016.2541139">10.1109/TIT.2016.2541139</a>. MR <a href="http://www.ams.org/mathscinet-getitem?mr=3493869">3493869</a> Zbl <a href="https://zbmath.org/?q=an:1359.94714">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="https://doi.org/10.2307/2972413">10.2307/2972413</a>. MR <a href="http://www.ams.org/mathscinet-getitem?mr=1517830">1517830</a> Zbl <a href="https://zbmath.org/?q=an:44.0248.09">44.0248.09</a></p>
<p>V. I. Levenshtein, <a href="https://nymity.ch/sybilhunting/pdf/Levenshtein1966a.pdf">Binary codes capable of correcting deletions, insertions, and reversals</a>, <em>Soviet Physics Dokl.</em> <strong>10</strong> (1966) 707–710. MR <a href="http://www.ams.org/mathscinet-getitem?mr=189928">189928</a> Zbl <a href="https://zbmath.org/?q=an:0149.15905">0149.15905</a></p>
<p>R. R. Varshamov and G. M. Tenengol’ts, <a href="http://mi.mathnet.ru/eng/at11293">Code correcting single asymmetric errors</a>, <em>Avtomat. i Telemeh.</em> <strong>26</strong> (1965) 288–292. MR <a href="http://www.ams.org/mathscinet-getitem?mr=172738">172738</a></p>
</body>
</html>