MDS符号

同義語:MDS codemaximum distance separable code最大距離分離符号

概要

MDS符号(MDS code)とは、長さ $n$、最小距離 $d$ の符号で、符号語の個数が Singleton の限界 $q^{n-d+1}$ に等しいもの、線形符号なら次元 $k$ について $d=n-k+1$ となるものである。どの $k$ 個の座標の値を指定しても符号語がただ 1 つに決まり、線形の場合は生成行列のどの $k$ 列も一次独立であることや双対符号も MDS であることと同値である。重みの分布は $n,k,q$ だけで決まり、そこから $k\ge2$ なら $n\le q+k-1$、二元の MDS 符号は自明なものに限ることが従う。長さの本当の上限は $q+1$(例外あり)と予想され、$q$ が素数の場合は証明されている。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 線形符号, 有限体, Reed–Solomon符号

長さ $n$ の語を $q$ 種類の文字で書くとき、符号語どうしを $d$ か所以上で異ならせたいなら、符号語の個数は $q^{n-d+1}$ を超えられない。どの 2 つの符号語も最初の $n-d+1$ 文字が違うはずだからである。これが Singleton の限界で、等号を達成する符号を MDS 符号(maximum distance separable code)という。線形符号なら、長さ $n$、次元 $k$ に対して最小距離が最大の $n-k+1$ になる符号である。Reed–Solomon符号 がその代表で、誤りと消失の訂正の能力がもっとも高い。
MDS 符号は「どの $k$ 個の座標の値も自由に指定でき、それで符号語が決まる」符号である。この性質は生成行列の列の一次独立性、検査行列の列の一次独立性、双対符号、行列の小行列式という 4 通りの言葉に言い換えられる(thm-mds-equiv)。さらに、重みの分布は $n,k,q$ だけで決まり(thm-mds-weights)、そこから長さの上限 $n\le q+k-1$ が出る(cor-mds-length)。とくに二元の MDS 符号は反復符号などの自明なものしかない。長さの本当の上限は $q+1$($q$ が偶数の特別な場合は $q+2$)と予想されていて、MDS 予想と呼ばれる。

定義と Singleton の限界

以下、$q\ge2$ とする。$q$ 個の元からなる集合 $\Sigma$(文字の集合)を固定し、$\Sigma^n$ の元を長さ $n$ の語、相異なる 2 つの語の異なる座標の個数を Hamming 距離という。$2$ 個以上の元をもつ部分集合 $C\subset\Sigma^n$ を符号といい、相異なる 2 元の距離の最小値を最小距離 $d(C)$ という。$\Sigma=\mathbb F_q$ で $C$ が線形部分空間のときが 線形符号 で、$[n,k,d]_q$ などの記号はその記事の意味で使う。

Singleton の限界

$C\subset\Sigma^n$ を最小距離 $d$ の符号とすると、$\lvert C\rvert\le q^{n-d+1}$ である。等号が成り立つことと、どの $n-d+1$ 個の座標を選んでも、その座標への制限 $C\to\Sigma^{n-d+1}$ が全単射であることは同値である。

頭の文字で区別する

$S$ を $n-d+1$ 個の座標の集合とし、$\pi_S\colon C\to\Sigma^S$ をその座標への制限とする。相異なる $c,c'\in C$ について $\pi_S(c)=\pi_S(c')$ なら、$c$ と $c'$ が異なる座標は $S$ の外の $d-1$ 個に限られ、$d(c,c')\le d-1$ となって最小距離に反する。よって $\pi_S$ は単射で、$\lvert C\rvert\le\lvert\Sigma^S\rvert=q^{n-d+1}$ である。
等号が成り立てば、単射 $\pi_S$ の値域と終域の元の個数が等しいので $\pi_S$ は全単射である。逆に、ある $S$ で $\pi_S$ が全単射なら $\lvert C\rvert=q^{n-d+1}$ である。$\square$

線形符号の場合は 線形符号 の定理「Singleton の限界」で検査行列の列を数えて示したが、上の証明は線形性を使わない(GRS25 Theorem 4.3.1、p. 79)。

MDS 符号

最小距離 $d$ の符号 $C\subset\Sigma^n$ で $\lvert C\rvert=q^{n-d+1}$ となるものを MDS 符号 という。線形符号 $C\subset\mathbb F_q^n$ では、次元を $k$ として $d=n-k+1$ となることである。

thm-mds-singleton により、MDS 符号では どの $k=n-d+1$ 個の座標の値も自由に指定でき、それで符号語がただ 1 つに決まる(GRS25 Definition 5.3.1・Proposition 5.3.3、pp. 101–102)。消失の訂正で言えば、位置の分かっている $n-k$ 個の文字が失われても、残りの $k$ 個から符号語が復元できる。
次の 3 つは、どの $n\ge1$ と $q$ でも存在する線形の MDS 符号で、自明な MDS 符号 という。

符号パラメータMDS である理由
全空間 $\mathbb F_q^n$$[n,n,1]_q$$d=1=n-n+1$
パリティ検査符号 $\{c:\sum_ic_i=0\}$$[n,n-1,2]_q$($n\ge2$)重み $1$ の語は和が $0$ でない
反復符号 $\{(a,\dots,a)\}$$[n,1,n]_q$$0$ でない符号語の重みは $n$

主定理:MDS であることの言い換え

MDS 符号の同値条件

$1\le k\le n-1$ とし、$C\subset\mathbb F_q^n$ を次元 $k$ の線形符号、$G$ をその生成行列($k\times n$)、$H$ を検査行列($(n-k)\times n$)とする。次は同値である。

  1. $C$ は MDS 符号である。
  2. $H$ のどの $n-k$ 本の列も一次独立である。
  3. $G$ のどの $k$ 本の列も一次独立である。
  4. 双対符号 $C^\perp$ は MDS 符号である。
    さらに、これらが成り立てば $G$ の最初の $k$ 本の列は一次独立で、行の基本変形により $G=(I_k\mid A)$($A$ は $k\times(n-k)$ 行列)の形にとれる。$G=(I_k\mid A)$ の形の生成行列については、上の条件は次と同値である。
  5. $A$ のすべての正方小行列($1\times1$ から $\min(k,n-k)$ 次まで)が正則である。
列の一次関係と符号語の零

1 ⇔ 2:線形符号 の定理「検査行列の列と最小距離」により、$d(C)\ge n-k+1$ は $H$ のどの $n-k$ 本の列も一次独立であることと同値である。Singleton の限界から $d(C)\le n-k+1$ なので、これは $d(C)=n-k+1$ と同値である。
1 ⇔ 3:$G$ の第 $j$ 列を $g_j$ とし、情報 $m\in\mathbb F_q^k$(行ベクトル)の符号語を $mG$ とすると、その第 $j$ 座標は $m g_j$ である。座標の集合 $S$($\lvert S\rvert=k$)について、列 $g_j$($j\in S$)を並べた $k\times k$ 行列 $G_S$ が特異であることは、$mG_S=0$ となる $m\ne0$ があること、すなわち $S$ の座標がすべて $0$ の $0$ でない符号語 $mG$ があることと同値である($G$ の行は一次独立なので $m\ne0$ なら $mG\ne0$)。そのような符号語の重みは $n-k$ 以下である。逆に重み $n-k$ 以下の $0$ でない符号語があれば、その零の座標から $k$ 個を選んだ $S$ で $G_S$ は特異になる。よって「どの $G_S$ も正則」は「$0$ でない符号語の重みがすべて $n-k+1$ 以上」と同値で、上と同じく 1 と同値である。
2 ⇔ 4:線形符号 の命題「双対符号の次元」により、$H$ は $C^\perp$(次元 $n-k$)の生成行列である。$C^\perp$ に 1 ⇔ 3 を当てると、$C^\perp$ が MDS であることは $H$ のどの $n-k$ 本の列も一次独立であることと同値である。
標準形:3 から最初の $k$ 本の列は一次独立で、$G_{\{1,\dots,k\}}$ は正則である。$G$ を $(G_{\{1,\dots,k\}})^{-1}G$ に替えても行が同じ空間を張るので、$G=(I_k\mid A)$ の形にとれる。
3 ⇔ 5:$G=(I_k\mid A)$ とし、$A$ の列の番号を $k+1,\dots,n$ とする。$k$ 個の座標の集合 $S$ を、$\{1,\dots,k\}$ に入る部分 $S_1$ とそれ以外の部分 $T$($\lvert T\rvert=t$)に分け、$R:=\{1,\dots,k\}\setminus S_1$ とおく($\lvert R\rvert=t$)。$G_S$ の列のうち $S_1$ の列は単位ベクトル $e_i$($i\in S_1$)なので、$G_S$ の行列式をこれらの列について展開すると、$\pm\det A_{R,T}$($A$ の行 $R$・列 $T$ の小行列式。$t=0$ なら $1$)になる。逆に $A$ の $t$ 次の正方小行列 $A_{R,T}$($1\le t\le\min(k,n-k)$)は、$S=(\{1,\dots,k\}\setminus R)\cup T$ としてこの形に現れる。よって「どの $G_S$ も正則」と「$A$ のどの正方小行列も正則」は同値である。$\square$

3 は、$G$ の $n$ 本の列が $\mathbb F_q^k$ の中で「どの $k$ 本も基底になる」ベクトルの集まりであることを言っている。この見方では、線形の MDS 符号は射影空間の点の集合で一般の位置にあるもの(弧、arc)と同じものになる(Bal12 §9、p. 744)。

Cauchy 行列から作る MDS 符号

$x_1,\dots,x_k,y_1,\dots,y_{n-k}$ を $\mathbb F_q$ の相異なる元とし($n\le q$)、$A_{ij}:=1/(x_i-y_j)$ とする。$A$ の正方小行列は同じ形の行列(Cauchy 行列)なので、相異なる $x_1,\dots,x_t,y_1,\dots,y_t$ について $t\times t$ 行列 $\bigl(1/(x_i-y_j)\bigr)$ が正則であることを示せばよい。$\sum_ja_j/(x_i-y_j)=0$($i=1,\dots,t$)とし、$P(z):=\sum_ja_j\prod_{l\ne j}(z-y_l)$ とおく。$P$ は次数 $t-1$ 以下で、$P(x_i)=\prod_l(x_i-y_l)\cdot\sum_ja_j/(x_i-y_j)=0$ なので $t$ 個の根をもち、$P=0$ である。$z=y_j$ を代入すると $a_j\prod_{l\ne j}(y_j-y_l)=0$ で、$a_j=0$ となる。よって thm-mds-equiv の 5 から、$(I_k\mid A)$ の生成する符号は $[n,k,n-k+1]_q$ の MDS 符号である。例えば $q=5$、$(x_1,x_2)=(0,1)$、$(y_1,y_2,y_3)=(2,3,4)$ なら
$$ A=\begin{pmatrix}2&3&1\\4&2&3\end{pmatrix} $$
で、$(I_2\mid A)$ は $[5,2,4]_5$ 符号を生成する。

重みの分布と長さの上限

線形の MDS 符号では、どの重みの符号語がいくつあるかが $n,k,q$ だけで決まる。重み $w$ の符号語の個数を $A_w$ と書く。

MDS 符号の重みの分布

$C$ を $[n,k,d]_q$ の MDS 符号($1\le k\le n$、$d=n-k+1$)とする。$A_0=1$、$1\le w\le d-1$ なら $A_w=0$ で、$d\le w\le n$ なら
$$ A_w=\binom nw\sum_{j=0}^{w-d}(-1)^j\binom wj\bigl(q^{\,w-d+1-j}-1\bigr) $$
である。とくに $A_d=\binom nd(q-1)$ で、$d+1\le n$ なら $A_{d+1}=\binom n{d+1}(q-1)(q-d)$ である。

台を含む集合で数えて包除する

座標の集合 $U$ について、台が $U$ に含まれる符号語($U$ の外の座標がすべて $0$ のもの)の個数を $N(U)$ とする。$U$ の外の座標の集合を $T$($\lvert T\rvert=n-\lvert U\rvert$)とする。
$\lvert T\rvert\le k$ のとき、thm-mds-singleton により $T$ を含む $k$ 個の座標への制限は全単射なので、$T$ への制限 $C\to\mathbb F_q^T$ は全射な線形写像で、その核の次元は $k-\lvert T\rvert$ である。$\lvert T\rvert\ge k$ のときは、$T$ の中の $k$ 個の座標がすべて $0$ の符号語は $0$ だけなので、核は $0$ である。どちらの場合も、$\lvert U\rvert=u$ として
$$ N(U)=q^{\max(k-n+u,\,0)}=q^{\max(u-d+1,\,0)} $$
である($n-k=d-1$)。台がちょうど $W$($\lvert W\rvert=w$)の符号語の個数は、包除原理(部分集合の上の Möbius の反転)により
$$ \sum_{V\subset W}(-1)^{w-\lvert V\rvert}N(V)=\sum_{v=0}^w(-1)^{w-v}\binom wv q^{\max(v-d+1,0)} $$
である。$w\ge1$ なら $\sum_v(-1)^{w-v}\binom wv=0$ なので、各項から $1$ を引いてよい。すると $v\le d-1$ の項は消え、$j:=w-v$ と置き直すと
$$ \sum_{v=d}^w(-1)^{w-v}\binom wv\bigl(q^{v-d+1}-1\bigr)=\sum_{j=0}^{w-d}(-1)^j\binom wj\bigl(q^{w-d+1-j}-1\bigr) $$
となる。$w< d$ なら和は空で $0$ である。重み $w$ の台は $\binom nw$ 通りあるので主張の式を得る。
$w=d$ では和は $j=0$ の項 $q-1$ だけである。$w=d+1$ では $(q^2-1)-(d+1)(q-1)=(q-1)(q-d)$ である。$\square$

符号語を 1 つずつ数えなくても重みの分布が分かる。例えば $[5,2,4]_5$ の Reed–Solomon 符号(ex-mds-cauchy の符号も同じ)では $A_4=\binom54\cdot4=20$、$A_5=(5^2-1)-5\cdot4=4$ で、$1+20+4=25=5^2$ である。
重みの個数は負にならないので、$A_{d+1}\ge0$ から長さの上限が出る。

長さの上限と二元の MDS 符号

$C$ を $[n,k,d]_q$ の線形の MDS 符号とする。

  1. $k\ge2$ ならば $d\le q$、すなわち $n\le q+k-1$ である。
  2. $k\le n-2$ ならば $k\le q-1$ である。
  3. $2\le k\le n-2$ ならば $n\le2q-2$ である。とくに二元($q=2$)の線形の MDS 符号は自明な MDS 符号($[n,n,1]_2$、$[n,n-1,2]_2$、$[n,1,n]_2$)に限る。
重み $d+1$ の個数

1:$k\ge2$ なので $d+1=n-k+2\le n$ で、thm-mds-weights により $0\le A_{d+1}=\binom n{d+1}(q-1)(q-d)$ である。$\binom n{d+1}(q-1)>0$ なので $q\ge d=n-k+1$ である。
2:$1\le k\le n-1$ なので thm-mds-equiv により $C^\perp$ は $[n,n-k,k+1]_q$ の MDS 符号で、次元 $n-k\ge2$ である。1 を $C^\perp$ に当てると $k+1\le q$ である。
3:1 と 2 から $n=(n-k)+k\le(q-1)+(q-1)$ である。$q=2$ なら 2 から $k\le1$ となり $k\ge2$ に反するので、$k\le1$ か $k\ge n-1$ である($k\ge1$ とする)。$k=1$ の MDS 符号は $d=n$ で、$0$ でない符号語はすべての座標が $1$ の語だけだから反復符号である。$k=n$ なら全空間である。$k=n-1$ なら $C^\perp$ は $[n,1,n]_2$ の MDS 符号すなわち反復符号なので、$C$ はパリティ検査符号である。$\square$

1 の評価は、$G$ の列を $\mathbb F_q^k$ のベクトルの集合とみて超平面を数える方法でも示せる(Bal12 Lemma 1.2、p. 734)。二元の符号で MDS が自明なものしかないことは、MDS 符号が文字の種類の多い符号でしか意味をもたないことを表している。Reed–Solomon符号 が長さ $n\le q$ に限られるのも同じ事情である。

長い MDS 符号と MDS 予想

cor-mds-length の上限 $n\le q+k-1$ は一般には達成されない。実際に作れる長さは $q+1$ までで、例外は 1 種類しかない。

二重拡大 Reed–Solomon 符号

$1\le k\le q$ とし、$\mathbb F_q=\{a_1,\dots,a_q\}$ とする。次数 $k-1$ 以下の多項式 $f=f_0+f_1x+\dots+f_{k-1}x^{k-1}$ に
$$ \bigl(f(a_1),\dots,f(a_q),\ f_{k-1}\bigr)\in\mathbb F_q^{q+1} $$
を対応させる写像の像は、$[q+1,k,q-k+2]_q$ の MDS 符号である。

最高次の係数を最後の座標に置く

写像は線形である。$f\ne0$ の像の重みが $q-k+2$ 以上であることを示せば、写像は単射で次元は $k$、最小距離は $q-k+2=(q+1)-k+1$ 以上となり、Singleton の限界から等号が成り立つ。$f_{k-1}\ne0$ なら $f$ の次数は $k-1$ で根は $k-1$ 個以下なので、最初の $q$ 座標のうち $q-k+1$ 個以上が $0$ でなく、最後の座標も $0$ でないから重みは $q-k+2$ 以上である。$f_{k-1}=0$ なら $f$ は次数 $k-2$ 以下の $0$ でない多項式で、根は $k-2$ 個以下なので、最初の $q$ 座標だけで重みは $q-k+2$ 以上である。$\square$

最初の $q$ 座標だけをとったものが評価点を $\mathbb F_q$ 全体にした Reed–Solomon符号 で、評価点を $\mathbb F_q^\times$ にした長さ $q-1$ の符号に、点 $0$ での値 $f(0)$ と、「無限遠点での値」にあたる最高次の係数 $f_{k-1}$ の 2 座標を足した形なので「二重拡大」という。生成行列の列は $(1,a,a^2,\dots,a^{k-1})^{\mathsf T}$($a\in\mathbb F_q$)と $(0,\dots,0,1)^{\mathsf T}$ である。

標数 $2$ の超卵形から作る符号

$q$ を $2$ の冪とする。$q+2$ 本の列
$$ (1,a,a^2)^{\mathsf T}\ (a\in\mathbb F_q),\qquad(0,1,0)^{\mathsf T},\qquad(0,0,1)^{\mathsf T} $$
を並べた $3\times(q+2)$ 行列は、$[q+2,3,q]_q$ の MDS 符号の生成行列である。$q$ が奇数なら、同じ $q+2$ 本の列の中に一次従属な 3 本がある。

3 本の列の行列式

thm-mds-equiv の 3 により、どの 3 本も一次独立であることを示せばよい(このとき行列の階数は $3$ で、生成行列になる)。相異なる $a,b,c\in\mathbb F_q$ について、場合ごとに行列式を計算する。

  • $(1,a,a^2),(1,b,b^2),(1,c,c^2)$:Vandermonde の行列式 $(b-a)(c-a)(c-b)\ne0$(Vandermondeの行列式)。
  • $(1,a,a^2),(1,b,b^2),(0,0,1)$:$b-a\ne0$。
  • $(1,a,a^2),(0,1,0),(0,0,1)$:$1$。
  • $(1,a,a^2),(1,b,b^2),(0,1,0)$:第 3 列で展開して $-(b^2-a^2)=-(b-a)(b+a)$。
    標数 $2$ では $b+a=b-a\ne0$ なので最後の場合も $0$ でなく、どの 3 本も一次独立である。$q$ が奇数なら $a=1$、$b=-1$($1\ne-1$)で最後の行列式が $0$ になる。$\square$

thm-mds-equiv の 4 により、この符号の双対符号は $[q+2,q-1,4]_q$ の MDS 符号である。$q+2$ 本の列の集合は、射影平面 $\mathrm{PG}(2,q)$ の 超卵形(hyperoval)と呼ばれる $q+2$ 点の弧に当たる(Bal12 p. 734)。

MDS 予想

次の主張は MDS 予想 と呼ばれる(Bal12 Conjecture 1.4、p. 734 の形。Segre の 1955 年の問いにさかのぼる)。

$2\le k\le q$ のとき、線形の $[n,k]_q$ MDS 符号の長さは $n\le q+1$ である。ただし $q$ が偶数で $k=3$ または $k=q-1$ のときは $n\le q+2$ である。
prop-mds-extended と prop-mds-hyperoval(とその双対)が、上限の長さの符号を与えている。$k\ge q+1$ の場合は cor-mds-length の 2 により自明な符号しかない。Ball は、$q=p^h$($p$ は素数)、$k\le q$ のとき $n\le q+k+1-\min(k,p)$ を証明した(Bal12 Theorem 1.7、p. 735、符号の形では Corollary 9.1、p. 744)。$k\le p$ なら上限は $q+1$ なので、$q$ が素数なら MDS 予想は成り立つ。一般の $q$ についての予想は、同論文の時点(2012 年)で、$q\le27$、$k\le5$ などの場合に確かめられていた(同 p. 734)。この記事では Ball の定理を証明しない。

例

符号パラメータMDS であることの根拠
自明な MDS 符号$[n,n,1]_q$、$[n,n-1,2]_q$、$[n,1,n]_q$定義の直後の表
Reed–Solomon符号$[n,k,n-k+1]_q$、$n\le q$根の個数
Cauchy 行列の符号$[n,k,n-k+1]_q$、$n\le q$ex-mds-cauchy
三元の $[4,2,3]_3$ 符号生成行列 $\begin{pmatrix}1&0&1&1\\0&1&1&2\end{pmatrix}$$A=\begin{pmatrix}1&1\\1&2\end{pmatrix}$ の成分と行列式 $1$ が $0$ でない(thm-mds-equiv の 5)
二重拡大 Reed–Solomon 符号$[q+1,k,q-k+2]_q$prop-mds-extended
超卵形の符号とその双対$[q+2,3,q]_q$、$[q+2,q-1,4]_q$($q$ は偶数)prop-mds-hyperoval

三元の $[4,2,3]_3$ 符号は $n=q+k-1=4$ で、cor-mds-length の 1 の等号が成り立つ例である。重みの分布は thm-mds-weights から $A_3=\binom43\cdot2=8$、$A_4=(3^2-1)-4\cdot2=0$ で、$0$ でない $8$ 個の符号語はすべて重み $3$ である。$q=4$ の超卵形の $[6,3,4]_4$ 符号では $A_4=45$、$A_5=0$、$A_6=18$ である。

反例

外す条件反例成り立たなくなること
$k\ge2$(cor-mds-length の 1)反復符号 $[n,1,n]_q$ で $n>q$$n\le q+k-1$
MDS であること(thm-mds-weights)二元の $[7,4,3]_2$ Hamming符号重み $d$ の符号語の個数が $\binom nd(q-1)$
標数 $2$(prop-mds-hyperoval)$q=5$ で同じ $7$ 本の列どの 3 本の列も一次独立
$k\le p$(rem-mds-conjecture の Ball の定理の上限 $q+1$)$q=4$($p=2$)、$k=3$ の超卵形の符号$n\le q+1$
どの $k$ 本の列も一次独立(thm-mds-equiv の 3)生成行列 $(1,1,0)$ の $[3,1,2]_2$ 符号MDS であること
反例の確認

各行の反例は、外した条件のほかの仮定を満たす。

各行の確認を開く

1 行目:反復符号は $d=n=n-1+1$ の MDS 符号で、$k=1$ である。$n>q=q+k-1$ なので上限は成り立たない。

2 行目:Hamming 符号は線形で $d=3< 4=n-k+1$ なので MDS でない。重み $3$ の符号語は $7$ 個で、式の値 $\binom73\cdot1=35$ と異なる。

3 行目:$q=5$ は奇数で、prop-mds-hyperoval の後半により列 $(1,1,1)$、$(1,4,1)$、$(0,1,0)$ が一次従属である。

4 行目:$k=3\le q$ だが $k>p=2$ である。prop-mds-hyperoval により長さ $6=q+2$ の MDS 符号がある。

5 行目:第 1 列 $(1)$ は一次独立だが、第 3 列 $(0)$ は一次独立でない。最小距離は $2< 3=n-k+1$ である。

補足

文献

一般の符号の Singleton の限界と、MDS 符号のどの $k$ 座標への制限も全単射であることは GRS25 Theorem 4.3.1(p. 79)、Definition 5.3.1・Proposition 5.3.3(pp. 101–102)にある。弧との対応、MDS 予想の形、Ball の定理は Bal12 の Conjecture 1.4・Lemma 1.2(p. 734)、Theorem 1.7(p. 735)、§9(p. 744)にある。thm-mds-weights と cor-mds-length の証明はこの記事で書き下ろした形である。

関連項目

参考文献

[2]
Simeon Ball, On sets of vectors of a finite vector space in which every subset of basis size is a basis, J. Eur. Math. Soc. 14 (2012), no. 3, 733–748, 2012, Lemma 1.2・Conjecture 1.4(p. 734)、Theorem 1.7(p. 735)、§9 Corollary 9.1(p. 744)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する