2023-03-05

有限可換群の部分群―Lagrangeの定理の逆

数学

$\newcommand{\setZ}{\mathbb{Z}} \newcommand{\setN}{\mathbb{N}} \newcommand{\divides}{\trianglelefteq} \newcommand{\coloneqq}{:=} \def\shiguma{\sigma} \newcommand{\acperm}[4]{\begin{pmatrix} 1 & 2 & 3 & 4 \\ #1 & #2 & #3 & #4 \end{pmatrix}}$

以下で使う記法の注釈

$\setN_{\ge a}$ ：集合 $\{x \in \setN \mid x \ge a\}$
$a \divides b$ ： $a$ は $b$ を割り切る
$\lvert G \rvert$ ：群 $G$ の位数
$A \sqcup B$ ：集合 $A \cup B$ を $A \cap B = \emptyset$ であることを強調した記法

一般に，有限群 $G$ では，任意の部分群 $H$ の位数について $\lvert H \rvert \divides \lvert G \rvert$ という関係が成立します．これは Lagrange の定理（の系）として知られています．

では，逆に，有限群 $G$ とその位数の正の約数 $d$ を任意にとってきたとき， $G$ には位数が $d$ である部分群 $H$ は存在するのでしょうか．これについて可換群の場合を見ていきます．

有限可換群と Lagrange の定理の逆
Lagrange の定理の逆を満たさない群
参考文献

有限可換群と Lagrange の定理の逆

次の有限可換群の基本定理（定理 1.1）を起点とします．ここでは定理 1.1 の証明は割愛します．

定理 1.1（有限可換群の基本定理）有限可換群 $G$ に対し，ある整数 $e_{1}, e_{2}, \ldots, e_{t} \ge 2$ で， $i = 1,2,\ldots, t-1$ に対して $e_{i} \divides e_{i+1}$ となるものが存在し，次が成立する．
\begin{align}
G \cong \setZ/e_{1}\setZ \times \cdots \times \setZ/e_{t}\setZ.
\end{align}また，この条件を満たす $e_{1}, \ldots, e_{t}$ は一意的に定まる．ただし， $t = 0$ ならば $G \cong \{0\}$ と解釈する．

この有限可換群の基本定理から次の主張が得られます．これで早くも目標は達成です．

命題 1.2 $G$ を有限可換群とし， $d \in \setN$ を $\lvert G \rvert$ の正の約数とする．このとき， $G$ には位数 $d$ の部分群が存在する．

証明．定理 1.1 から， $e_{1} \divides e_{2} \divides \cdots \divides e_{t}$ を満たす $e_{1}, \ldots, e_{t} \in \setN_{\ge 2}$ が存在して， $G \cong \setZ/e_{1}\setZ \times \cdots \times \setZ/e_{t}\setZ$ が成り立つ．

この同型から $\lvert G \rvert$ に関して $\lvert G \rvert = e_{1} e_{2} \cdots e_{t}$ が得られる． $d$ はこれを割り切る整数であるから，すべての $i = 1, 2, \ldots, t$ に対して $d_{i} \divides e_{i}$ となるような正の整数 $d_{1}, d_{2}, \ldots, d_{t} \in \setN_{\ge 1}$ が存在して， $d = d_{1} d_{2} \cdots d_{t}$ となる．

そこで， $i = 1, 2, \ldots, t$ で $f_{i} \coloneqq e_{i}/d_{i} \in \setN$ とおいて，
\begin{align}
\widehat{H} \coloneqq (f_{1}\setZ/e_{1}\setZ) \times \cdots \times (f_{t}\setZ/e_{t}\setZ)
\end{align}とおくと， $\widehat{H}$ の位数 $\lvert \widehat{H} \rvert$ は
\begin{align}
\lvert \widehat{H} \rvert = \prod_{i=1}^{t} \lvert f_{i} \setZ/e_{i} \setZ \rvert = \prod_{i=1}^{t} \frac{e_{i}}{f_{i}} = \prod_{i=1}^{t} d_{i} = d
\end{align}となる．

したがって， $G$ の部分群にも位数が $d$ のものが存在する．□

Lagrange の定理の逆を満たさない群

前節で有限可換群に対して，その位数の正の約数を位数とする部分群が存在することを示すことができました．言わば「Lagrange の定理の逆が成り立つ」ことが分かりました．ところで，そもそも「Lagrange の定理の逆が成り立たないような群」，すなわち「位数の正の約数を適当にとったとき，その値を位数とするような部分群が存在しないことがある群」は存在するのでしょうか．

実は置換群の部分群である交代群にそのような群が存在します．最後にこのことを示します．

命題 2.14 次の交代群 $\mathfrak{A}_{4}$ には位数が 6 の部分群が存在しない．

この命題の証明のために補題を一つ用意します．

補題 2.2指数 2 の部分群は正規部分群である．

証明．群 $G$ の部分群 $H$ が $\lvert G/H \rvert = 2$ を満たすとする． $\shiguma \notin H$ ならば $\shiguma H \neq H,\;H\shiguma \neq H$ である．さらに，
\begin{align}
\lvert \shiguma H \rvert= \lvert H \shiguma \rvert = \lvert H \rvert = \frac{\lvert G \rvert}{2}
\end{align}が成り立つ．したがって $\shiguma H = H \shiguma = G \setminus H$ となる．ここで $G \setminus H$ は差集合を表す．これより次のように書ける．
\begin{align}
G = H \sqcup \shiguma H = H \sqcup H \shiguma.
\end{align}

いま $\shiguma \in G$ と $\tau \in H$ をそれぞれ任意にとる．このとき，以下のようにして $\shiguma \tau \shiguma^{-1} \in H$ が従う．

もし $\shiguma \in H$ であれば， $H$ は部分群なので， $\shiguma \tau \shiguma^{-1} \in H$ ．
もし $\shiguma \notin H$ であれば， $\shiguma H = H \shiguma$ となることから， $\shiguma \tau \shiguma^{-1} \in H$ ．

以上より， $H$ は $G$ の正規部分群となる．□

命題 2.1 の証明． $H$ が $\mathfrak{A}_{4}$ の位数 6 の部分群であるとする．補題 2.2 より $H$ は $\mathfrak{A}_{4}$ の正規部分群であり，（左）剰余類の間に演算が入る．この演算を用いて $\shiguma \in \mathfrak{A}_{4}$ に対して $\shiguma^{2} H = (\shiguma H)^{2} = H$ を得る．ここで $\lvert \mathfrak{A}_{4}/H \rvert = 2$ であることを用いた．もし仮に $\shiguma \in \mathfrak{A}_{4}$ が
\begin{align}
\shiguma^{3} = 1
\end{align}を満たすなら， $\shiguma^{2}H = H \ni 1 = \shiguma^{3} = \shiguma^{2} \cdot \shiguma$ より $\shiguma \in H$ を得る．したがって，
\begin{align}
\# \{\shiguma \in \mathfrak{A}_{4} \mid \shiguma^{3} = 1\} \le \lvert H \rvert = 6
\end{align}となる．しかし， $\mathfrak{A}_{4}$ には条件 $\shiguma^{3} = 1$ を満たす元が
\begin{alignat}{3}
&\acperm 1234, & \quad\quad & \acperm 1342, & \quad\quad & \acperm 1423,\\
&\acperm 2314, && \acperm 2431, && \acperm 3124,\\
&\acperm 3241, && \acperm 4132, && \acperm 4213
\end{alignat}の 9 個あり，先ほどの不等式と矛盾する．したがって $\mathfrak{A}_{4}$ には位数 6 の部分群はない．□

なお， $n$ 次の交代群 $\mathfrak{A}_{n}$ については， $n \le 3$ ならば可換群であるため命題 1.2 から「Lagrangeの定理の逆が成り立つ群」であると， $n \ge 5$ ならば単純群であるため補題 2.2 から「Lagrangeの定理の逆が成り立たないような群」であると明らかになります．

参考文献

[1] abstract algebra - $A_4$ has no subgroup of order $6$? - Mathematics Stack Exchange
[2] Does a finite group has subgroups of order of all divisors of its order? - Mathematics Stack Exchange

2022-11-03

複素数に対する作図可能性の代数的な特徴付け

本記事では，いま読んでいる本*1 *2 にあった個人的に引っかかった記述を，自分なりに掘り下げた報告を行います．記事の本文に当たる部分はLaTeXでpdfにしたほうが楽に作れるため，貼り付けたGoogleドライブのリンク先のファイルに預けてあります．そこで，以下ではpdfの要旨を，これを書いた経緯（いきさつ）*3 から書き残しておきます．

記事本文の預け先：
drive.google.com

経緯（いきさつ）

『数論序説』の18節：「正 $l$ 角形の作図」には，正 $l$ 角形に関して，$l$ が2冪の場合には作図可能であること（命題2.12*4）と，作図可能となる奇素数 $l$ の条件（定理2.5）が記述されています．

このとき，「複素数 $\alpha$ が作図可能」ということは次のように定義されています．

定義 A$\alpha \in \mathbb{C}$ が作図可能であるとは，次の条件を満たすことである：

体の列 $\mathbb{Q} = K_{0} \subseteq K_{1} \subseteq \cdots \subseteq K_{n} \subseteq \mathbb{C}$ であって，

すべての $i = 1, 2, \ldots, n$ に対して $[F_{i} : F_{i-1}] \le 2$
$\alpha \in K_{n}$

となるものが存在する

しかし，この定義は我々が「作図可能」という単語を聞いたときに思い浮かべるであろう直観的な定義，すなわち，

定義 B$\alpha \in \mathbb{C}$ が作図可能であるとは，次の条件を満たすことである：

平面上の点 $(\mathop{\mathrm{Re}} \alpha, \mathop{\mathrm{Im}} \alpha) \in \mathbb{R}^{2}$ が作図によって得られる

とは掛け離れています*5．

『数論序説』には上記の定義の直前にこのギャップを埋める説明がなされていますが，証明というよりも事実（あるいは読者の演習）程度の記述でした．そこで私は他のテキストを当たることにしました……*6

『代数学2 環と体とガロア理論』（いわゆる「雪江代数青」）の4.8節：「作図問題」では，作図可能性の定義として上記の「直観的な」定義を据えて記述がなされています．そして作図可能性について以下のような代数的な特徴付け（補題4.8.3および定理4.8.4）を得ています．

定理 C$\alpha \in \mathbb{R}$ が作図可能であるとは，次の条件を満たすことである：

体の列 $\mathbb{Q} = K_{0} \subseteq K_{1} \subseteq \cdots \subseteq K_{n} \subseteq \mathbb{R}$ であって，

すべての $i = 1, 2, \ldots, n$ に対して $[F_{i} : F_{i-1}] = 2$
$\alpha \in K_{n}$

となるものが存在する

「これで行間が埋まった……！！」と思いたいところですが，よく見ると定理Cの特徴付けは実数に対してだけされていて，「2次拡大」の列も $\mathbb{R}$ の部分体に限定されています．したがって，これを一般の複素数に対して適用しようと思うと，ちょっと話が変わってきます．

実は定理Cの証明を再考すると，複素数に対する特徴付けとして次の主張を得ることができます．

定理 D$\alpha \in \mathbb{C}$ が作図可能であることは，次の条件を満たすことと等価である：

体の列 $\mathbb{Q} = K_{0} \subseteq K_{1} \subseteq \cdots \subseteq K_{n} \subseteq \mathbb{R}$ であって，

すべての $i = 1, 2, \ldots, n$ に対して $[F_{i} : F_{i-1}] \le 2$
$\mathop{\mathrm{Re}} \alpha,\ \mathop{\mathrm{Im}} \alpha \in K_{n}$

となるものが存在する

以上を踏まえると，最初に感じた行間は以下の主張を示せば完全に埋まることになります．

残滓 E(1) 実部分体からなる2次拡大の列

$$\mathbb{Q} = K_{0} \subseteq K_{1} \subseteq \cdots \subseteq K_{n} \ni \mathop{\mathrm{Re}} \alpha,\ \mathop{\mathrm{Im}} \alpha$$

があること

と

(2) 複素部分体からなる2次拡大の列

$$\mathbb{Q} = K_{0} \subseteq K_{1} \subseteq \cdots \subseteq K_{n} \ni \alpha$$

があること

は等価である

つまり，複素数 $\alpha$ そのものについて複素数体の部分体である2次拡大の列がうまくとれることと，その実部と虚部について実数体の部分体である2次拡大の列がうまくとれることが等価であることを示せばよいことになります．

「この残滓Eの証明をやったよ」というのがpdfの主たる内容（定理1.3.3）ということになります．

*1:『数論序説』（小野孝著，裳華房，1987）

*2:以前，研究室の人たちと久しぶりに会ったときにこの本の話題になり，そこで数学書を読むペースが遅いと冗談混じりに煽られましたが，自分でも遅いと思います．真実です．

*3:ルビが振れると聞いて無駄に振ってみました．

*4:命題番号は掲載文書のナンバリングそのものを表すものです．以下同様．

*5:複素平面を考えて数と点を対応させれば自然に出てくる定義です．

*6:こういうときにはすぐに調べずに自分の頭で考えることが重要というのは分かってはおります……でも時間は有限なのでご勘弁を……

2022-01-01

algorithm 環境とは別にそれと似た環境を作る

この記事では擬似コードを挿入する LaTeX の環境である algorithm 環境と同等の環境を簡単に作成できるようにする方法を紹介します。このとき algorithm 環境を残したまま新たな環境，例えば protocol 環境を自作することができるようにします。これにより，「アルゴリズム」と「プロトコル」という2つのラベルをもつ環境を下図のように併存させることができます*1。

f:id:tobetakoyaki:20211219184941p:plain:w600 — 「アルゴリズム」と「プロトコル」を並置した様子

なお，本記事では jsclasses 系のドキュメントクラス（jsarticle，jsreport，jsbook）の使用を想定して説明を行います*2。

また，この記事は私の LaTeX 擬似コード系ブログの第3弾です。第2弾はこんな記事でした*3。

tobetakoyaki.hatenablog.com

完成コード
float 環境の作り方
- ちょっとした改良
可変名のコマンド定義のしかた
- \csname ~~ \endcsname
- \def にうまく組み込むための \expandafter
cleverefパッケージへの対応
- \if@english を用いた定義の切り替え
\newalgfloat の使用例
本文中で言及しなかった参考文献

完成コード

本記事では以下に示す「\newalgfloat」というコマンドの定義方法を説明します。

名称	\newalgfloat
入力	#1: type，#2: label，#3: ext
仕様	① type という名称の algorithm 環境と同様の環境を作成 ② キャプションに label を指定 ③ type 環境の目次は拡張子 ext のファイルで管理 ④ 環境の目次は jsclasses 系の出力に合わせる ⑤ cleveref に対応させる

まず完成品を示すと，こんな感じです↓

\usepackage{xparse}%
%
\usepackage[chapter]{algorithm}%
\usepackage[noend]{algpseudocode}%
%
% define a new algorithm-like environment
% (partly cited from algorithm.sty)
\def\newalgfloat#1#2#3{% #1 type, #2 label, #3 .ext
  \floatstyle{\ALG@floatstyle}%
  %
  \ifthenelse{\boolean{ALG@within}}{%
    \ifthenelse{\equal{\ALG@within}{part}}%
      {\newfloat{#1}{htbp}{#3}[part]}{}%
    \ifthenelse{\equal{\ALG@within}{chapter}}%
      {\newfloat{#1}{htbp}{#3}[chapter]}{}%
    \ifthenelse{\equal{\ALG@within}{section}}%
      {\newfloat{#1}{htbp}{#3}[section]}{}%
    \ifthenelse{\equal{\ALG@within}{subsection}}%
      {\newfloat{#1}{htbp}{#3}[subsection]}{}%
    \ifthenelse{\equal{\ALG@within}{subsubsection}}%
      {\newfloat{#1}{htbp}{#3}[subsubsection]}{}%
    \ifthenelse{\equal{\ALG@within}{nothing}}%
      {\newfloat{#1}{htbp}{#3}}{}%
  }{%
    \newfloat{#1}{htbp}{#3}%
  }%
  %
  \floatname{#1}{#2}%
  %
  % for listof"float"s
  \expandafter\def\csname list#1name\endcsname{%
    \if@english List of \MakeUppercase #2s\else #2目次\fi%
  }%
  \expandafter\def\csname listof#1s\endcsname{%
    \if@twocolumn\@restonecoltrue\onecolumn%
    \else\@restonecolfalse\fi%
    \ifdefined\chapter%
      \chapter*{\csname list#1name\endcsname}%
    \else%
      \section*{\csname list#1name\endcsname}%
    \fi%
    \@mkboth{\csname list#1name\endcsname}{}%
    \@starttoc{#3}%
    \if@restonecol\twocolumn\fi%
  }%
  \expandafter\let\csname l@#1\endcsname\l@figure%
  %
  % for cleveref
  \crefname{#1}{#2}{#2}%
  \if@english%
    \crefformat{#1}{##2\textgb{#2 ##1}##3}%
    \crefmultiformat{#1}%
      {##2\textgb{#2 ##1}##3}%
      {, ##2\textgb{#2 ##1}##3}%
      {, ##2\textgb{#2 ##1}##3}%
      {, ##2\textgb{#2 ##1}##3}%
  \else%
    \crefformat{#1}{##2\textgb{#2##1}##3}%
    \crefmultiformat{#1}%
      {##2\textgb{#2##1}##3}%
      {，##2\textgb{#2##1}##3}%
      {，##2\textgb{#2##1}##3}%
      {，##2\textgb{#2##1}##3}%
  \fi%
}%
%
% e.g. define some new algorithmic float by \newalgfloat
\newalgfloat{protocol}{プロトコル}{lop}%
%

以下ではこのコードについて何点か説明を加えます。

float 環境の作り方

algorithm 環境のような float 環境*4を新しく定義するには，基本的に次の4つを用います。

(1) \floatstyle{style}
この先で定義する float 環境のスタイルを決めます。

(2) \newfloat{type}{placement}{ext}[within]
新しい float 環境を作成するコマンドです。各引数の内容は以下に述べる通りです。

type ... これで \begin{type} – \end{type} によって環境を使用できるようになります。
placement ... 環境のデフォルト配置優先度を決めます。htbpなどで指定するやつです。
ext ... この float 環境だけの目次を作成する際に使われるファイルの拡張子を指定します。
within ... ここに指定した見出しレベルを含めた番号で環境に番号を振ります。

(3) \floatname{type}{float name}
float name に指定した文字列が type 環境のキャプションに使われます。

(4) \listof{type}{title}
type 環境だけの目次を出力するコマンドです。目次のタイトルが title になります。

ちょっとした改良

基本的には上の4つを使えば float 環境を新しく整備できますが，
上記の \listof を使って目次を出力すると，jsclasses 系のフォーマットと統一されません。

f:id:tobetakoyaki:20220101081040p:plain:w500 — 左が jsclasses 系による出力，右が float.sty の \listof による出力

そこで，今回は

\listof を使わずに jsclasses 系の目次出力のコマンド（例えば \listoffigures）を基に \listoftypes を定義する*5。
\listoftypes によって出力される見出しには，あれば \chapter を使い，なければ \section を使う*6

という作戦を取りました。

1個目は単にコピペすれば良いだけで解決できます。

2個目は説明を割愛しますが，「\ifdefined」という指定されたコマンドが定義されているかどうかで処理を分岐させるコマンドを用い，

\ifdefined\chapter%
  \chapter*{プロトコル目次}%
\else%
  \section*{プロトコル目次}%
\fi%

とすれば対応できます。

↓出力はこんな感じになります。

f:id:tobetakoyaki:20211219191016p:plain:w500 — プロトコル目次の出力のイメージ

可変名のコマンド定義のしかた

例えば，foo，bar，baz という3つの float 環境を定義したいときは，\listoffoos，\listofbars，\listofbazs という3つのコマンドを1つずつ定義する必要があります。
しかし，これだとコードは複雑になる上，統一した修正を加えたいときにとても面倒です。これらのコマンドの処理内容はほぼ同じですから，コマンド名の一部を変数にして \listof#1s として一般の定義を書けたら凄く楽でしょう。これを実現できるようにするのが \csname ~~ \endcsname です。

\csname ~~ \endcsname

この2つのコマンドで挟まれた文字列はコマンドの名前として処理され，次のコード例に書き込んだように，1つ目の変数に入る内容によって異なるコマンド名を意味することができます*7。

\csname listof#1s\endcsname
% #1 = foo なら，\listoffoos と等価
% #1 = bar なら，\listofbars と等価

\def にうまく組み込むための \expandafter

今回は \csname listof#1s\endcsname という名前のコマンドを \def によって定義したいのですが，これを

\def\csname listof#1s\endcsname...

と書いても，まず「\def\csname」の部分で解釈されてしまうためうまくいきません*8。

正しくは以下のコードのようにコマンドの展開の順番を後回しにする「\expandafter」というコマンドを使用します。

\expandafter\def\csname listof#1s\endcsname{定義内容}%
% #1 = foo なら，\def\listoffoos{定義内容} と等価
% #1 = bar なら，\def\listofbars{定義内容} と等価

cleverefパッケージへの対応

最後に参照をうまく取り扱ってくれる cleveref パッケージに対応させてみましょう。今回は\crefname，\crefformat，\crefmultiformat の3つを定義しておきました。

これらのコマンドの詳細な説明は公式ドキュメントや他の解説記事に譲り，次の節では英語と日本語のどちらで文章を書いていても対応できるようにコマンドを定義する方法についてまとめます。

公式ドキュメントなど
www.ctan.org

解説記事①
qiita.com

解説記事②
qiita.com

\if@english を用いた定義の切り替え

jsclasses 系のドキュメントスタイルは english オプションを付けることで英語版の体裁に変えることができます。これを用いてもし英語版であれば処理Aを，そうでなければ処理Bを行うというコマンドを作ることができます。

\def\hoge{%
  \if@english%
    % 処理A %
  \else%
    % 処理B %
  \fi%
}

\newalgfloat の使用例

ここまでで冒頭に示した完成コードの構成要素を説明しおわりました。

最後に，\newalgfloat を使って新しく algorithm 環境に類似した環境を作ってみます。

……といっても定義は非常にシンプルです*9。

% 環境を使う前に定義しておく
\newalgfloat{protocol}{プロトコル}{lop}%
%
% 環境の出力時
\begin{protocol}
  \caption{値を交換する}
  \label{prot:change}
  \begin{algorithmic}[1]
    \AlgInput A: $s_{0}$，B: $s_{1}$ 
    \AlgOutput A: $t_{0}$，B: $t_{1}$ \Comment{$t_{i} = s_{1-i}$}
    \State A sends $s_{0}$ to B, B receives it as $t_{1}$
    \State B sends $s_{1}$ to A, A receives it as $t_{0}$ 
    \Return A: $t_{0}$，B: $t_{1}$
  \end{algorithmic}
\end{protocol}

↓出力例はこんな感じです。

f:id:tobetakoyaki:20211219192510p:plain:w350 — protocol環境の出力例

本文中で言及しなかった参考文献

1. 公式ドキュメント
CTAN: Package float
2. 公式ドキュメント
CTAN: Package algorithms
3. 公式ドキュメント
CTAN: Package jsclasses
4. 解説記事 —\expandafter について
徹底解説！ \expandafter 活用術（キホン編） - Qiita

*1:残念ながら皆さんにとって需要があるかは判然としませんが，少なくとも私には需要があったので紹介することにしました。

*2:なお，動作確認はupLaTeX→dvipdfmxの設定で行っております。

*3:こんなことは皆さんにはどうでもよいと思いますが，第2弾を公開する前にこの記事を書き始めています。

*4:float 環境は figure 環境や table 環境のなかまであり，コンテンツを本文と分離した上でキャプションを加えるなどして出力する環境を指します。

*5:jsclasses 系でないドキュメントスタイルに合わせる場合も，このコマンドの定義を参考にするとうまくいくでしょう。

*6:例えば jsarticle には \chapter というコマンドは定義されていません。したがって，jsbook に合わせて目次を \chapter で出力させると，jsarticle を使ったときにうまく機能しないコードになります。そのためこのような改良を加えました。

*7:半角スペースが入る場所と入らない場所に気をつけてください。\endcsname の前にスペースが入ると正しく処理されません。

*8:\expandafter を挿入しない場合，TeXは「\def」を先に展開し「\def\csname~~」を「\csname を ~~ と定義しなさい」と解釈します。これはいまやりたいことではありません。いまやりたいのは「\csname ~~ \endcsname」を展開して得られるコマンド名のコマンドを定義することですから，「\def」の展開を後に回す必要があります。したがって「\expandafter」を使います。

*9:複雑な部分を \newalgfloat の内部に押し込んだのでそれはそう。

2021-12-31

algpseudocode.sty の algorithmic 環境で「入力」や「出力」を作る

LaTeX

この記事では algpseudocode.sty の algorithmic 環境を用いて LaTeX で擬似コードを書く場合に、アルゴリズムの「入力」や「出力」を下図のように表示するための方法を紹介します*1。

f:id:tobetakoyaki:20210617015000p:plain:h350 — 冒頭に「Input」と「Output」を追加してアルゴリズムの機能を説明する様子

具体的には、もともとこの sty ファイルに定義されている「Require」や「Ensure」を出力するコマンドと同じように定義をする方法を紹介していきます。

なお、この記事は私の LaTeX 擬似コード系ブログとしては第2弾になります。第1弾はこんな記事でした。第3弾も予定しています*2。
tobetakoyaki.hatenablog.com

概要
algorithm.sty と algpseudocode.sty
algnewcommand で新しいコマンドを定義する
参考文献

概要

先に完成コードを提示します。詳しい説明は本文をお読みください。

\usepackage[chapter]{algorithm}%
\usepackage[noend]{algpseudocode}%
%
% augmenting the commands of algorithmicx package
\algnewcommand\algorithmicinput{{\bfseries\gtfamily 入力}}%
\algnewcommand\algorithmicoutput{{\bfseries\gtfamily 出力}}%
\algnewcommand\AlgInput{\item[\algorithmicinput]}%
\algnewcommand\AlgOutput{\item[\algorithmicoutput]}%
\algrenewcommand\Return{\State\textbf{return} }%

algorithm.sty と algpseudocode.sty

LaTeX でアルゴリズムの擬似コードを書く際に役立つパッケージに algorithm.sty と algpseudocode.sty があります。それぞれのパッケージの頒布元を以下に引用します。

algorithmパッケージ: CTAN: Package algorithms
algpseudocodeパッケージ: CTAN: Package algorithmicx

この記事ではこの2つのパッケージの基本的な使い方は紹介しません。上記のサイトに掲載のドキュメントや以下に引用する解説記事を参照ください。

解説記事①
qiita.com

解説記事②
li-feel.hatenablog.com

algnewcommand で新しいコマンドを定義する

algorithmic 環境では

コマンドの定義や再定義には \algnewcommand や \algrenewcommand を使う*3
\item を使うと行頭に文字を出力できる*4

これを踏まえると、「入力」を行頭に出すコマンドは次のように定義できます。

\algnewcommand\algorithmicinput{{\bfseries\gtfamily 入力}}%
\algnewcommand\AlgInput{\item[\algorithmicinput]}%

↓使用例はこんな感じです*5。

\begin{algorithm}
  \caption{Factorial}
  \label{alg:factorial}
  \begin{algorithmic}[1]
    \AlgInput $n$
    \State $P \leftarrow 1$
    \For{$i=2,\dotsc,n$}
      \State $P \leftarrow P \times i$
    \EndFor
    \Return $P$
  \end{algorithmic}
\end{algorithm}

↓出力はこんな感じです*6。

f:id:tobetakoyaki:20211219021710p:plain:w350 — \AlgInputを使用したコードの出力例

参考文献

algorithm や algpseudocode について
1. algorithmsパッケージのCTANホームページ
CTAN: Package algorithms
2. algorithmicxパッケージのCTANホームページ
CTAN: Package algorithmicx
3. 基本的な使い方に関する解説記事①
algorithmicxを使いLaTeXに擬似コードを追加 - Qiita
4. 基本的な使い方に関する解説記事②
LaTeXのalgorithmicxの擬似コードをカスタマイズしてみる - Li::Feel

*1:図では「入力」や「出力」ではなく「Input」と「Output」になっていますがここは自由に変更できます。

*2:と宣言することで自分にプレッシャーをかけています。

*3:コードを見て \newcommand との違いを調べましたが、私には理解できませんでした。力不足……。

*4:list 環境という、itemize 環境や enumerate 環境、description 環境を一般化したものを用いて algorithmic 環境が定義されていることによります。

*5:「\Return」は冒頭にある完成コマンドに載せたもので自ら再定義しています。

*6:for 文の終わりに「endfor」が出力されていないのは「noend」オプションを指定して algorithmic を読み込んでいるためです。

2021-11-17

計数工学科卒論・修論 LaTeXテンプレートについて

LaTeX 計数工学科

この記事では計数工学科*1で卒業論文や修士論文を書く際に標準となっている LaTeXテンプレートの使い方を勝手に解説します。Overleaf で作業する場合を想定した使い方も併記します。なお，細かい説明は註に書き込むため，詳細を気にする方はそちらも併せてご覧ください。

LaTeX テンプレートをダウンロード
文字コードを修正
upLaTeX を使う—ファイル篇
Overleaf で (u)pLaTeX を使用する
いざコンパイル
参考文献
おまけ

LaTeX テンプレートをダウンロード

まずは標準クラスファイルをダウンロードします。

数理 ➡︎URL: https://www.keisu.t.u-tokyo.ac.jp/research/latex/

「suribt」は論文（卒論・修論）用のクラスファイル
「suribtabst」は要約用のクラスファイル

システム ➡︎URL: https://www.keisu.t.u-tokyo.ac.jp/research/latex-system

「systemB」は卒論用のクラスファイル
「systemM」は修論用のクラスファイル

文字コードを修正

上記ページで配布されるファイルには，UTF-8 ではない文字コードで書かれたものもあります*2。これを修正します*3。

nkf（Network Kanji Filter）というソフトウェア*4を使用するとファイルの文字コードを変更することができます。UTF-8 に変更するなら

nkf -w --overwrite [ファイル名]

をターミナルで実行すれば OK です*5。

upLaTeX を使う—ファイル篇

普段，upLaTeX を使っている方*6は以下の内容を cls ファイルから見つけ出して*7，例えば「11pt」の後ろに uplatex オプションを追記します*8 *9。

\LoadClass[a4paper,onecolumn,titlepage,11pt,uplatex
  % 6行中略 %
]{jsbook}

なお，2021年11月7日現在配布されている suribt.cls では既に「uplatex」が追記されています。upLaTeX を使いたくない場合は，これを消してください*10。

Overleaf で (u)pLaTeX を使用する

コンパイラを LaTeX に設定しただけではうまく (u)pLaTeX でコンパイルしてくれないため*11，Overleafの案内にあるように「latexmkrc」というファイルを作ります*12。ちなみに以下は私個人が使っている設定です。

upLaTeX の場合の latexmkrc はこれ⬇︎

$latex = 'uplatex %O -kanji=utf8 -no-guess-input-enc -synctex=1 -interaction=nonstopmode %S';
$bibtex = 'upbibtex %O %B';
$dvipdf = 'dvipdfmx %O -o %D %S';
$makeindex = 'mendex %O -o %D %S';
$pdf_mode = '3';

pLaTeX の場合の latexmkrc はこれ⬇︎

$latex = 'platex %O -kanji=utf8 -no-guess-input-enc -synctex=1 -interaction=nonstopmode %S';
$bibtex = 'pbibtex %O %B';
$dvipdf = 'dvipdfmx %O -o %D %S';
$makeindex = 'mendex %O -o %D %S';
$pdf_mode = '3';

いざコンパイル

ここまで来れば正しくコンパイルできると思います。
思う存分，あなたの研究結果をまとめてください。

参考文献

計数卒論・修論テンプレートについて（近年更新があるもの）
1. 計数工学科 LaTeX テンプレートについて - Qiita
2. 計数工学科卒論LaTeXテンプレートをOverleafでコンパイルする - Qiita
3. 東京大学工学部計数工学科 | LaTeXテンプレート【数理側】
4. 東京大学工学部計数工学科 | LaTeXテンプレート（システム情報工学コース／システム情報学専攻）【システム側】

nkf について
5. nkf Network Kanji Filter Project Top Page - OSDN 【公式】
6. 【 nkf 】コマンド――文字コードと改行コードを変換する：Linux基本コマンドTips（51） - ＠IT

latexmk について
7. Latexmk 【公式】
8. Latexmk - TeX Wiki

Overleaf × 日本語について
9. Japanese - Overleaf, オンラインLaTeXエディター【公式】
10. Overleaf v2 で日本語を使用する方法 - TeX Alchemist Online

おまけ

upLaTeX vs pLaTeX
upTeX,upLaTeX - TeX Wikiに upTeX や upLaTeX に関する説明がありますが，upLaTeX は pLaTeX の上位互換といえます。個人的にはこの2つなら upLaTeX を使うほうが良いと考えます。

BibTeX
BibTeX とは参考文献リストの成形を行うツールです。一定の書式で参考文献を出力するためには必須のツールと言えます。

BibTeX では以下のような書式で文献情報を登録した項目を書き連ねた bib ファイルを作成します*13。この書式はBibTeX - Wikipediaにも載っていますし，Springer や IEEE などのページでは BibTeX 形式の文献情報を出力する機能がついていますから，わざわざ覚える必要はありません。

@inproceedings{KEY,
  author = {Author, First and Author, Second},
  booktitle = {Book Title},
  title = {{Literature Whose Title Has Some Capitalized Word in It}},
  year = {9999},
  pages = {1--14},
}

……で，おまけとしてお伝えしたかったのは次の2つ：

title のエントリはさらに波括弧で括ることで大文字小文字を忠実に出力してくれます。
pages のように，数の範囲には hyphen (-) ではなく en dash (–)
を使います*14。

文献タイトルは「title =」の後を二重波括弧で記したものを[1]と[3]，一重波括弧で記したものを[2]と[4]に出力しています。[2]と[4]では文献タイトルの1単語目しかキャピタライズされません。

f:id:tobetakoyaki:20211110011308p:plain:w300 — BibTeX を利用した参考文献リストの出力例

和暦
「\和暦」➡︎「\today」で年号に和暦を使えます*15。しかし，2021年11月9日現在，suribt.cls 以外では「令和」対応がされていないようです*16。これには「\today」の定義を，jsbook.cls や jsarticle.cls にある「\today」と置き換えることで対応できますが，論文提出月は固定されているため，ほとんどの方は \today を使わずに月を直接入力するでしょうから特に問題はありません。#それはそう

*1:正確には，東京大学工学部計数工学科および同大学院情報理工学系研究科数理情報学専攻および同研究科システム情報学専攻です。

*2:nkf の guess によれば，「suribt-20191220.zip」は tex，cls が UTF-8，dtx が ISO-2022-JP，ins が ASCII で書かれており，「suribtabst-20141120.zip」は tex が Shift_JIS，cls は ISO-2022-JP で書かれており，「systemB-20181225.zip」は tex が Shift_JIS，cls は ISO-2022-JP で書かれており，「systemM-20181225.zip」は tex が Shift_JIS，cls は ISO-2022-JP で書かれているようです。

*3:修正しないとコメントアウトに何が書いてあるのか分からないだけでなく，定義内容が正確に処理されない可能性があります。修正しましょう。

*4:URL: https://osdn.net/projects/nkf/

*5:nkf の使い方に関しては参考文献6: https://atmarkit.itmedia.co.jp/ait/articles/1609/29/news016.htmlで詳しく解説されています。

*6:例えば tex ファイルの冒頭に「\documentclass[uplatex, dvipdfmx]{jsarticle}」などと書いている人はこれに該当します。

*7:「LoadClass」または「jsbook」で検索するとすぐ見つかります。

*8:補足　「\LoadClass」というコマンドは cls ファイルの中で別の cls ファイルを読み込むコマンドです。使い方は通常のドキュメントファイルの冒頭で使う「\documentclass」と同じです。今回は upLaTeX を使いたいため，通常の文書で行うのと同じように，jsbook クラスに uplatex オプションを付けて読み込むようにしています。なお，dvipdfmx の指定もここに書き加えて良いと思いますが，tex ファイルの冒頭で「\documentclass[..., dvipdfmx, ...]{suribt}」のように記述しても構いません。

*9:ちなみにクラスファイルを本気で書き換えようと思う場合は，例えば「\newif\ifuplatex」「\uplatexfalse」「\DeclareOption{uplatex}{\uplatextrue}」を「\ProcessOptions」の前に挿入した上で，「\ifuplatex ,uplatex\fi」を jsbook の呼び出しをしているどこかに挿入することで実現できます。これらのコマンド群の内容を説明します。まず初めの「\newif」の行では新しい if コマンドを定義しています。次の行ではこのコマンドを false にしています。そして，クラスファイルの読み込み時に uplatex オプションが指定されたときに \ifuplatex が true になるように変更します。これを使うと，uplatex オプションが指定されたときだけ「\ifuplatex = true」となるので，「\ifuplatex ,uplatex\fi」によって uplatex オプションが jsbook に渡されたことになります。

*10:dtx ファイルにはこの追記がなされていないため，新たに ins ファイルから生成しなおしても問題ありません。

*11:ログを見るとコンパイラを LaTeX にしても pdfLaTeX にしたときと挙動があまり変わらないように見えました。どうして……

*12:補足　1行目は upLaTeX でファイルをコンパイルするときの設定です。同様に2–4行目はそれぞれ，BibTeX を upBibTeX で，dvipdf を dvipdfmx で，makeindex を mendex で行うと設定しています。5行目は pdf の生成方法を指定しています。数字が0なら PDF を生成しない，1なら pdfLaTeX で生成する，2なら ps ファイルから生成する，3なら dvi ファイルから「$dvipdf」に指定した方法で pdf ファイルを生成する，4なら LuaLaTeX で生成する，5なら XeLaTeX で生成するというように対応が決まっています。

*13:どのタイミングで作成するかについてですが，論文を書き始めたときでも良いですし，日頃から論文を読み漁っているそのときからでも構いません。……というような話が『美文書入門』にあったと記憶しています。BibTeX では本文中で引用されていない文献は参考文献一覧に通常出力されませんから，bib ファイルを平時からの文献リストとして使用しても執筆に支障はないと思います。ちなみに「\cite{*}」をファイルのどこかで記述すると，bib ファイルに記入したすべての文献を参考文献リストに出力することができます。~~でも決してこの機能を使って参考文献一覧を嵩増ししてはいけない。~~

*14:hyphen は「-」，en dash は「--」，em dash は「---」を打つことで出力できます。

*15:ちなみに「\number\year」で年だけを「\number\month」で月だけを「\number\day」で日だけを取得できます。

*16:補足　標準テンプレートでは jsbook などとは異なり日付を月までしか出力しません。この違いのために標準テンプレートの中で「\today」を再定義しているため，ここが古いままだと令和に対応できないということになります。

2021-06-24

Bertrand-Chebyshevの定理の初等的な証明について

数学

この記事ではBertrand-Chebyshevの定理と呼ばれる整数論の定理を紹介します。この記事で行う証明は高校数学の内容が分かっていれば十分に理解できるものになっています。
$\def\floor#1{\left\lfloor #1 \right\rfloor}$

Bertrandの予想とChebyshevによる解決
証明の準備
証明
まとめ
参考文献

Bertrandの予想とChebyshevによる解決

1845年，フランスのJoseph Bertrandは素数の分布について次のような予想を提出しました。

予想 1.1任意の正の整数 $n$ に対して， $n < p \le 2n$ を満たす素数 $p$ が存在する。

この予想を提出したとき，Bertrandは $n \le 3 \times 10^6$ の場合にこれが正しいことを検証したようです。

さて，時が流れること5年，ロシアのPafnuty Chebyshevはガンマ関数を用いてこの予想 1.1を肯定的に解決しました。このことから，現在では予想 1.1は「Bertrand-Chebyshevの定理」と呼ばれています。ちなみにChebyshevは「ロシア数学の父」と呼ばれることもある数学者で，統計や確率論でたくさんお世話になるChebyshevの不等式にもその名前を残しています。教え子の中には「Markov連鎖」に名を残すAndrey Markovもいるようです。

Chebyshevによる証明が行われてからおよそ80年後，1932年にはハンガリーのPaul Erdősがこの主張を初等的な数学を用いて証明しました。ちなみに「Erdös」ではなく「Erdős」です。さて，本記事ではこのErdősによる証明をさらに洗練させた，栃折の証明方法[栃折 2013]で予想 1.1を証明しましょう。

証明の準備

まず，Bertrand-Chebyshevの定理を証明するにあたっていくつか準備を進めます。以下に示す命題の証明はそこまで難しくないため詳細は割愛します。

補題 2.1正の数 $x$ に対して $x$ 以下の素数の個数を $\pi(x)$ で表すと， $\pi(x) < \dfrac{1}{3} x + 2$ が成り立つ。

証明の概略
$2$ と $3$ 以外の素数は， $2$ の倍数でも $3$ の倍数でもない。また， $1$ も素数ではない。このことから，
\begin{align}
\pi(x) \le \floor{x} - \left( \floor{\frac{x}{2}} + \floor{\frac{x}{3}} - \floor{\frac{x}{6}} \right) + 1
\end{align}
と評価できる。ただし， $\floor{x}$ は $x$ を超えない最大の整数を返す関数で床関数 (floor function)と呼ばれる。あとは， $x = 6m + r$ （ $m$ は整数， $0 \le r < 6$ ）とでもおいて細かく場合分けすればよい。なお， $r = 0$ と $0 < r < 2$ を区別すると等号の成立条件を考えなくてもうまくいくことに注意。■

ここで $P(x)$ を $x$ 以下の素数の総積とする。このとき，次の補題 2.2が成り立つ。

補題 2.2 $n$ を正の整数，実数 $x$ は $x \ge 3$ を満たすとする。このとき次の2つが成立する。
(1) $\dfrac{P(2n-1)}{P(n)} \le {}_{2n-1}\mathrm{C}_{n} \le 2^{2n-2}$
(2) $P(x) < 2^{2x-3}$

証明の概略
(1) ${}_{2n-1}\mathrm{C}_{n}$ の分子には $n+1$ 以上 $2n-1$ 以下の素数がすべて現れることに着目する。これらの積は分母と約分されないことから，左側の不等式が成り立つ。右側の不等式も計算により示すことができる。
(2) まず $x$ が整数のときだけ考えればよいことを示す。 $x$ が整数の場合については帰納法を使って示すことができる。初めに $x = 3, 4$ での成立を示すとうまくいく。途中で(1)を使う。■

補題 2.3 $n \ge 4$ を正の整数とする。 ${}_{2n}\mathrm{C}_{n} > \dfrac{2^{2n}}{n}$ が成り立つ。

証明の概略
$n$ に関する帰納法を用いて示すことができる。■

ここで， ${}_{2n}\mathrm{C}_{n}$ の素因数 $p$ に対して， $a_p$ をその指数とする。すなわち， ${}_{2n}\mathrm{C}_{n}$ は $p^{a_p}$ では割り切れるが， $p^{a_p + 1}$ では割り切れないとする。 $a_p$ は整数論の言葉ではオーダー (order)とも呼ばれ， $\operatorname{ord}_{p}({}_{2n}\mathrm{C}_{n})$ とも書かれる。このオーダーについて次の補題 2.4が成り立つ。

補題 2.4 $N = \floor{\log_p(2n)}$ とする。このとき， $a_p = \sum_{i=1}^{N} \left( \floor{\frac{2n}{p^i}} - 2 \floor{\frac{n}{p^i}} \right)$ が成り立つ。

証明
${}_{2n}\mathrm{C}_{n} = \dfrac{(2n)!}{(n!)^2}$ となるため， $M = \floor{\log_p(n)}$ とおくと，
\begin{align}
a_p = \operatorname{ord}_p((2n)!) - 2 \operatorname{ord}_p(n!) = \sum_{i=1}^{N} \floor{\frac{2n}{p^i}} - 2 \sum_{i=1}^{M} \floor{\frac{n}{p^i}} = \sum_{i=1}^{N} \left( \floor{\frac{2n}{p^i}} - 2 \floor{\frac{n}{p^i}} \right) +2 \sum_{i=M+1}^{N} \floor{\frac{n}{p^i}}.
\end{align}
ここで， $i \ge M+1 > \log_p(n)$ のとき， $\dfrac{n}{p^i} < 1$ となるから，最後のシグマは $0$ である。これより主張は成り立つ。■

以上で準備は終わりです。これらの事実を活用してBertrand-Chebyshevの定理を証明しましょう。

証明

証明は背理法による。すなわち，ある正の整数 $n$ が存在して，区間 $(n, 2n ]$ の範囲に素数が存在しないとする。
ちょっと頑張ると $64$ 未満の正の整数 $m$ の場合は区間 $(m, 2m ]$ の範囲に素数を見つけられるため，この $n$ は $n \ge 64$ を満たす。

$p$ を ${}_{2n}\mathrm{C}_{n}$ の素因数として， $a_p = \operatorname{ord}_p({}_{2n}\mathrm{C}_{n})$ とする。
$p > \dfrac{2}{3}n$ と仮定する。このとき，素因数 $p$ は $n$ より大きくなれないため， $\dfrac{2}{3}n < p \le n$ を満たす。
特に $n \ge 5$ であるから $2n < \dfrac{4}{9} n^2$ であり， $\dfrac{4}{9}n^2 < p^2$ である。これらより，
\begin{align}
\log_p(2n) = \frac{\log(2n)}{\log p} < \frac{\log\left(\dfrac{4}{9} n^2\right)}{\log p} < \frac{\log(p^2)}{\log p} = 2
\end{align}
となるため， $\floor{\log_p(2n)} \le 1$ である。すると補題 2.4から
\begin{align}
a_p \le \floor{\frac{2n}{p}} - 2 \floor{\frac{n}{p}} = 2 - 2 \times 1 = 0.
\end{align}
ここで $1 \le \dfrac{n}{p} < \dfrac{3}{2}$ を用いた。 $p$ は ${}_{2n}\mathrm{C}_{n}$ の素因数としたから $a_p \ge 1$ であるためこれは矛盾する。
よって， $p \le \dfrac{2}{3}n$ が成り立つ。

また任意の実数 $x$ に対して $\floor{2x} - 2 \floor{x} = 0,1$ であることに注意すれば，
\begin{align}
a_p = \sum_{i=1}^{N} \left( \floor{\frac{2n}{p^i}} - 2 \floor{\frac{n}{p^i}} \right) \le \sum_{i=1}^{N} 1 = N \le \log_p(2n) \tag{I}
\end{align}
である。したがって $p^{a_p} \le 2n$ となる。特に $p > \sqrt{2n}$ であれば， $a_p < 2$ となり， $a_p =1$ に確定する。
なお， $n \ge 5$ では $\sqrt{2n} < \dfrac{2}{3}n$ が成り立つことからこのような素数 $p$ は存在しうることに注意。

以上より，
\begin{align}
{}_{2n}\mathrm{C}_{n} = \left( \prod_{\substack{p \le \sqrt{2n}, \\ p \text{ divides } {}_{2n}\mathrm{C}_{n}}} p^{a_p} \right) \left( \prod_{\substack{\sqrt{2n} < p \le \frac{2}{3} n, \\ p \text{ divides } {}_{2n}\mathrm{C}_{n}}} p^{a_p} \right) = \left( \prod_{\substack{p \le \sqrt{2n}, \\ p \text{ divides } {}_{2n}\mathrm{C}_{n}}} p^{a_p} \right) \left( \prod_{\substack{\sqrt{2n} < p \le \frac{2}{3} n, \\ p \text{ divides } {}_{2n}\mathrm{C}_{n}}} p \right) < \left( \prod_{p \le \sqrt{2n}} p^{a_p} \right) \dfrac{P\left( \dfrac{2}{3}n \right)}{P( \sqrt{2n})}
\end{align}
である。いま

$P\left( \dfrac{2}{3}n \right) < 2^{2\times \frac{2}{3} n - 3}$ （補題 2.2より），
$n \ge 5$ ならば $P(\sqrt{2n}) > P(3) = 6$ ，
$p^{a_p} \le 2n$ （式(I)より），
$\pi(\sqrt{2n}) < \dfrac{1}{3} \sqrt{2n} + 2$ （補題 2.1より）

であることから，
\begin{align}
\left( \prod_{p \le \sqrt{2n}} p^{a_p} \right) \dfrac{P\left( \dfrac{2}{3}n \right)}{P( \sqrt{2n})} < \frac{2^{\frac{4}{3}n - 3}}{6} (2n)^{\frac{1}{3}\sqrt{2n}+2} < 2^{\frac{4}{3}n - 5} (2n)^{\frac{1}{3}\sqrt{2n}+2}
\end{align}
である。これより，補題 2.3から
\begin{align}
\frac{2^{2n}}{n} < {}_{2n}\mathrm{C}_{n} < 2^{\frac{4}{3}n - 5} (2n)^{\frac{1}{3}\sqrt{2n}+2}
\end{align}
を得る。最左辺と最右辺の対数をとって，
\begin{align}
2n \log 2 - \log n < \left( \frac{4}{3}n - 5 \right) \log 2 + \left( \frac{1}{3}\sqrt{2n}+2 \right) \log(2n)
\end{align}
となる。整理して，
\begin{align}
\frac{\log(2n)}{\sqrt{2n}} + \frac{9}{2n} \log \frac{n}{2} - \log 2 > 0 \tag{II}
\end{align}
を得る。すなわち，区間 $(n, 2n]$ の範囲に素数が存在しないような $n$ に対しては式(II)が成り立つ。式(II)の左辺を $f(n)$ とおく。

詳細な計算は演習とするものの， $f(x)$ のふるまいを調べると， $f(x)$ は $x > 0$ の範囲では，ある $x_0 > 0$ を境に $0< x < x_0$ では増加， $x_0 < x$ では減少する。この $x_0$ はたとえば $f^{\prime}(8) = \dfrac{13}{128}(1-2\log2) < 0$ であることから， $x_0 < 8$ であると分かる。

これより， $n \ge 64$ のとき，
\begin{align}
f(n) \le f(64) = 2^{-7} \log 2 \times (56\sqrt{2} - 83) < 0
\end{align}
となる。これは式(II)と矛盾する。

以上より，すべての正の整数 $n$ に対して，区間 $(n, 2n]$ の範囲に素数が存在する。■

まとめ

整数の性質を示す上で解析的な性質を利用するというのが，解析的整数論の面白さでもあると思いますが，今回は解析的整数論の中でも高校のカリキュラムで扱うような微積の知識だけを用いて証明ができるBertrand-Chebyshevの定理を紹介しました。解析的整数論の成果としてはほかにも「正の整数 $m$ と，それと互いに素な整数 $a$ に対して， $m$ を法として $a$ と合同な素数 $p$ が無限に存在する」ということを主張するDirichletの算術級数定理や，「 $\pi(x)$ が漸近的に $\dfrac{x}{\log x}$ と同じように振る舞う*1」ということを主張する素数定理といった定理があります。これらは今回とは違い，高校の学習範囲を超えた知識を利用して主張を示すものです。私もまだこれらの証明を理解しているわけではないので，いつか理解したいと思います。

なお，上に述べた証明の出だしで「ちょっと頑張ると $64$ 未満の正の整数 $m$ の場合は区間 $(m, 2m]$ の範囲に素数を見つけられる」と書きました。ちゃんとした証明の中に「ちょっと頑張る」という表現は本当は良くないのですが，実際に行うことといえば一つ一つの $m$ に対して調べていくだけなのでお許しください。

参考文献

[Wikipedia]　ベルトランの仮説 - Wikipedia，Bertrand's postulate - Wikipedia．参照日: 2021/06/20
[栃折 2013]　「 $n$ と $2n$ の間に素数がある」の証明を考える ‐ ベルトラン・チェビシェフの定理のより強い評価による証明 ‐ ．栃折成紀．2013．

*1:2021年6月24日23:27追記。この部分は当初「 $\pi(x)$ が漸近的に $x \log x$ と同じように振る舞う」と書いてありましたがこれは誤りで，正しくは既に修正してあるように「 $\pi(x)$ が漸近的に $\dfrac{x}{\log x}$ と同じように振る舞う」です。大変失礼いたしました。

2021-05-03

中断しても番号が途切れない参考文献の出力

LaTeX

LaTeXでレポートや何かの申請書を書く際に*1，「3ページ目と6ページ目の後ろ」といったように複数の箇所に参考文献を分けて出力したいことがあるかもしれません．
このような場合，デフォルトのままでは「\begin{thebibliography}」とやるたびに文献番号がリセットされてしまいます．そこで，本記事では文献番号が連続するように複数個の参考文献を出力する方法を考えていきます．

なお，コードとその出力例は下記のOverleafに掲載しています．

Overleaf, Online LaTeX Editor

前提
愚直な方法
jsarticle.clsのデフォルトのthebibliography環境を使用している場合
- カウンタを直接いじる場合
- thebibliography環境を直接いじる場合
natbibパッケージを使用している場合
- カウンタを直接いじる場合
- thebibliography環境を直接いじる場合

前提

LaTeXで参考文献を出力する最も基本的な方法は以下のようにすることです．

\begin{thebibliography}{9}
  \bibitem{文献1} 本界 多蔵．『本を書いたぞ』．出版出版．2021．
  \bibitem{文献2} 本場刈野 伊江．『本ばかりの家』．書店書店．2020.
\end{thebibliography}

このようにすると，この順で参考文献のリストに出力され，また，本文中で例えば「\cite{文献1}」とすると『本を書いたぞ』の引用ができます．

本記事では複数箇所に参考文献を挿入することを想定しますので，以下のようにthebibliography環境を2つ使った例を取り上げ説明を行います．

\begin{thebibliography}{9}
  \bibitem{文献1} 本界 多蔵．『本を書いたぞ』．出版出版．2021．
\end{thebibliography}
\begin{thebibliography}
  \bibitem{文献2} 本場刈野 伊江．『本ばかりの家』．書店書店．2020.
\end{thebibliography}

この場合の出力は以下のようになります．冒頭に述べたように出力されるラベルは共に「1」となり，番号がリセットされていることが分かります．

f:id:tobetakoyaki:20210504135004p:plain:w500 — ただ単に複数個の参考文献を使用しただけのときの出力の様子

本記事では次のように2つ目以降の参考文献の番号が中断したところから再開してくれるように設定することを目標とします．

f:id:tobetakoyaki:20210606135040p:plain:w500 — 継続される参考文献の出力の様子（今回の目標）

愚直な方法

\bibitemはオプション引数で文献ラベルを指定することが可能です．これを利用すれば，簡単に目標を達成できます*2．

\begin{thebibliography}{9}
  \bibitem[1]{文献1} 本界 多蔵．『本を書いたぞ』．出版出版．2021．
\end{thebibliography}
\begin{thebibliography}{9}
  \bibitem[2]{文献2} 本場刈野 伊江．『本ばかりの家』．書店書店．2020.
\end{thebibliography}

なお，この方法によれば，例えば数字だけのラベリングだけでなく「本界21」のような「著者名+年号」タイプのラベリングも出力できます*3．

jsarticle.clsのデフォルトのthebibliography環境を使用している場合

カウンタを直接いじる場合

すべてを手動で設定するのが面倒であれば，次のようにカウンタを逐次変更してやる方法もあります．

\begin{thebibliography}{9}
  \bibitem{文献1} 本界 多蔵．『本を書いたぞ』．出版出版．2021．
\end{thebibliography}
\begin{thebibliography}{9}
  \setcounter{enumiv}{1} % カウンタの値を変更
  \bibitem{文献2} 本場刈野 伊江．『本ばかりの家』．書店書店．2020.
\end{thebibliography}

thebibliography環境を直接いじる場合

「いちいちカウンタの値を入力するのなんてしたくない！」という方．やや怖いですが，thebibliography環境の定義を直接いじることでも解決できます*4．

注意．カウンタの定義部分と設定部分である3行だけが追加した部分で，残りはjsarticle.clsによるthebibliography環境の定義の内容です．

\newcounter{patch@enumiv@numcarry} % 追加部分①
\renewenvironment{thebibliography}[1]{%
  \global\let\presectionname\relax
  \global\let\postsectionname\relax
  \section*{\refname}\@mkboth{\refname}{\refname}%
  \list{\@biblabel{\@arabic\c@enumiv}}%
    {\settowidth\labelwidth{\@biblabel{#1}}%
    \leftmargin\labelwidth
    \advance\leftmargin\labelsep
    \@openbib@code
    \usecounter{enumiv}%
    \setcounter{enumiv}{\value{patch@enumiv@numcarry}} % 追加部分②
    \let\p@enumiv\@empty
    \renewcommand\theenumiv{\@arabic\c@enumiv}}%
  \sloppy
  \clubpenalty4000
  \@clubpenalty\clubpenalty
  \widowpenalty4000%
  \sfcode`\.\@m}
  {\def\@noitemerr
    {\@latex@warning{Empty `thebibliography' environment}}%
  \setcounter{patch@enumiv@numcarry}{\value{enumiv}} % 追加部分③
  \endlist}

natbibパッケージを使用している場合

参考文献を綺麗に出力してくれるパッケージにnatbibパッケージ*5があります．
natbibパッケージを利用している場合はthebibliography環境の定義がjsarticle.clsとは全く異なるため，再定義の仕方を変更する必要があります．

カウンタを直接いじる場合

カウンタを直接いじる場合は，natbibパッケージが文献のラベリングを「NAT@ctr」というカウンタを用いて行っているため，先ほどの「\setcounter{enumiv}{1}」とする代わりに「\setcounter{NAT@ctr}{1}」を使えばよくなります．

thebibliography環境を直接いじる場合

また，thebibliography環境を直接いじる場合は，以下のようにします*6．

注意． カウンタの定義部分と設定部分である3行だけが追加された部分で，残りの大部分は元々あるnatbib.styによるthebibliography環境の再定義の内容です．

\newcounter{NAT@patch@numcarry} % 追加部分①
\renewenvironment{thebibliography}[1]{%
 \bibsection
 \parindent\z@
 \bibpreamble
 \bibfont
 \list{\@biblabel{\the\c@NAT@ctr}}{\@bibsetup{#1}\global\c@NAT@ctr\z@}%
 \setcounter{NAT@ctr}{\value{NAT@patch@numcarry}}  % 追加部分②
 \ifNAT@openbib
   \renewcommand\newblock{\par}%
 \else
   \renewcommand\newblock{\hskip .11em \@plus.33em \@minus.07em}%
 \fi
 \sloppy\clubpenalty4000\widowpenalty4000
 \sfcode`\.\@m
 \let\NAT@bibitem@first@sw\@firstoftwo
    \let\citeN\cite \let\shortcite\cite
    \let\citeasnoun\cite
}{%
 \bibitem@fin
 \bibpostamble
 \def\@noitemerr{%
  \PackageWarning{natbib}{Empty `thebibliography' environment}%
 }%
 \setcounter{NAT@patch@numcarry}{\value{NAT@ctr}} % 追加部分③
 \endlist
 \bibcleanup
}%

*1:私自身が何かの申請書を最近書いたのかと言われれば，答えはNoになりますが．

*2:文献数が1桁であればこれでも全く問題はありませんが，この方法では桁数の異なるラベルが設定されたときに数字が左揃えで出力されてしまいます．これだと通常の参考文献が右揃えで数字を出力することと反するため，完璧な再現とはいえません．

*3:\bibitem[本界21]{文献1}のように書けばよいわけです．

*4:thebibliography環境はlistという環境を利用して出力されています．以下のコードはlist環境に対して番号をうまくやる解決法を提示したHow to interrupt/resume a list in LaTeX? - Stack Overflowを参考にしました．なおlist環境については例えばにっき♪: クラスファイルを作ろう(7)をご覧ください．

*5:ソース: CTAN: Package natbib

*6:natbib.sty (ver. 8.31) では1063行目からthebibliography環境の再定義がなされており，1068行目から続くlist環境の中で文献一覧が出力される仕組みになっています．