hotchpotch/wikipedia-multilingual-ir-pairs huggingface dataset:
マージソート
マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。
n個のデータを含む配列をソートする場合、最悪計算量O(n log n)である。分割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレースな（すなわち入力の記憶領域を出力にも使うので、追加の作業記憶領域を必要としない）バリエーションも提案されているが、一般には、O(n)の追加の作業記憶領域を必要とする。
（ナイーブな）クイックソートと比べると、最悪計算量は少ない。ランダムなデータでは通常、クイックソートのほうが速い。
1945年、フォン・ノイマンによって考案された。
マージソート アルゴリズム
基本的な手順は以下の通りである。
ステップ1と2の途中（すなわち細分化するまでの部分）についてこのアルゴリズムの手順に含めず、あらかじめ局所的に整列されている多数の列が与えられるもの、とすることもある。後述する、テープをマージする手法の場合、最初のテープから主記憶を可能な限り全部使って整列できるだけ整列した部分列を、順次書き出したテープから始める。
ステップ3のマージでは、2本のデータ列の先頭同士を比べ小さい方をデータ列から取り出して出力し、残りのデータをもつ2本のデータ列に対して再帰的に同じ処理を、両方が空になるまで行う。ソートすべきデータ列が部分的に順次得られる場合、オンラインアルゴリズムとして、部分データ列をソートして後でマージするという変形も可能である。
クイックソート等と同様、完全に細分化せずにスレッショルドとして適度に大きい個数を設定し、それ以下になった時点でなんらかの「ごく少数の対象専用の高速なコードによるソート」を併用するという高速化手法がある。手順として書き出すと次のようになる。
マージソート アルゴリズム
他に特殊な応用例として、外部ソートの1手法でテープ（のようなシーケンシャルアクセスメディア）に収められたデータをソートする、というものがある。最も単純な、4本のテープを2本ずつ使う「平衡2系列マージ」を例に説明する。まず元のデータから、利用可能な内部記憶をできるだけ使って、部分的に整列されている列をテープに書き出す。この時、2本のテープに交互に書き出すようにする。
次に、2本のテープのそれぞれの先頭部分にある、それぞれの部分列をマージしながら、別の2本のテープに交互に書き出す。この操作により、より長い整列した列が得られる。全てのマージが終わったら、コピー元とコピー先を入れ替え、同様に繰り返す。繰返し毎に各部分列の長さは約2倍に、列の個数は約半分になると期待できる。
最終的に、テープを切り替えることなく、1本のテープに全てのデータが出力されたら完了である。この技法はコンピュータがまだ高価で、テープが大容量外部記憶の主力だった時代にさかんに研究され、さまざまなバリエーションが編み出された。『The Art of Computer Programming』の§5.4にそれらの詳細がある。
（※ Haskellのリストは「長さを測って半分ずつに分ける」という操作には適さないため、要素を1個ずつ振り分ける関数を使っている。この実装では安定ではない）
マージソート アルゴリズムの動作例
初期データ: 8 4 3 7 6 5 2 1
フーリエ変換
数学においてフーリエ変換（フーリエへんかん、英: Fourier transform、FT）は、実変数の複素または実数値関数を、その周波数成分を表す別の関数ˆfに写す変換である。
工学においては、変換後の関数ˆfはもとの関数に含まれる周波数を記述していると考え、しばしばもとの関数の周波数領域表現 (frequency domain representation) と呼ばれる。言い換えれば、フーリエ変換は関数を（離散的な正弦波・余弦波の和であるフーリエ級数とは対照的に）連続的な周波数成分の集まりとして分解する操作である。
フーリエ変換 (FT) は他の多くの数学的な演算と同様にフーリエ解析の主題を成す。「フーリエ変換」という言葉は関数の周波数領域表現のことを指すこともあるし、関数を周波数領域表現へ写す変換の過程・公式を言うこともある。なおこの呼称は、19世紀フランスの数学者・物理学者で次元解析の創始者とされるジョゼフ・フーリエに由来する。
フーリエ変換 概要
フーリエ変換は、関数をその周波数成分に分解し、どの周波数がどれだけ含まれているかを示す「周波数スペクトル」に変換する数学的な操作である。この変換は、19世紀初頭にフランスの数学者・物理学者であるジョゼフ・フーリエが、熱伝導方程式の研究において、熱の伝わり方をフーリエ級数を用いて表そうとしたことに端を発する。
時間や空間に関する関数（波形など）を、その関数を構成する正弦波（または複素指数関数）の集まりとして表現し直す操作と見なすことができる。元の関数が時間領域（または空間領域）の関数  であれば、フーリエ変換後の関数  は周波数領域（または波数領域）の関数となり、元の関数  に周波数  の成分がどれだけ含まれているかを表す。
この変換は可逆であり、フーリエ逆変換と呼ばれる操作によって、周波数スペクトル  から元の関数  を復元することができる。
フーリエ変換は、数学におけるフーリエ解析の中心的な道具であるだけでなく、物理学、工学（特に信号処理、画像処理、通信工学）、量子力学など、現代科学の非常に広範な分野で不可欠なツールとなっている。
フーリエ変換 定義
フーリエ変換の定義には、用いる周波数の変数（周波数  [ヘルツ] か、角周波数  [ラジアン/秒] か）や、変換・逆変換の係数（正規化係数）の選び方によって、いくつかの流儀が存在する。分野によって慣習的に用いられる定義が異なるため注意が必要である。
主な定義として以下の3つが挙げられる。
本項では、特に断りのない限り、数学や一部の信号処理の文献で用いられることのある、周波数 （ヘルツ）を用い、変換・逆変換の係数が  である定義1（ユニタリ・周波数）を採用する。この定義は、フーリエ変換と逆変換が対称形（ の肩の符号が異なるだけ）である点に特徴がある。
また、この定義（および定義3）が「ユニタリ（英: unitary）」と呼ばれるのは、プランシュレルの定理で示されるように、関数のノルム（信号のエネルギーに相当）が変換前後で保存される、すなわち  が成り立つためであり、フーリエ変換が（空間における）ユニタリ作用素であることを意味する。定義2（非ユニタリ）では、このような単純なエネルギー保存則は成立しない（係数  が必要となる）。
絶対可積分関数 f: R → C のフーリエ変換は、
で定義される。ここでギリシャ文字小文字の ξ は任意の実数（周波数）である。
フーリエ変換 定義
対象の関数における独立変数が物理量の場合、フーリエ変換は独立変数の次元をもとの逆数に移す。例えば、変換前の関数における独立変数 x が時間の次元をもつとき、変換後の独立変数 ξ は周波数の次元を持つ。あるいは、変換前の独立変数 x が長さの次元をもつとき、変換後の独立変数 ξ は波数の次元を持つ。この性質は定義より x ξ が無次元量であることから従う。
適当な条件のもと、f はその変換 ˆf からフーリエ逆変換 (inverse transform)
によって復元することができる（x は任意の実数）。
絶対可積分でない関数、例えば  （定数関数）や  （周期関数）、あるいはディラックのデルタ関数  のような「関数」ではない対象についてもフーリエ変換を定義したいという強い要請が物理学や工学には存在する。
このため、フーリエ変換の定義を緩増加超関数（またはシュワルツ超関数）の空間  に拡張することが行われる。
緩増加超関数  は、シュワルツ空間 （急減少関数、すなわち無限回微分可能で、自身およびその全ての導関数が  で多項式の逆数よりも速く 0 に近づく滑らかな関数  の集まり）上の連続線型汎関数として定義される。つまり、 は各  に対して複素数  を対応させる写像である。
フーリエ変換 定義
（絶対可積分関数  も、 により、 という超関数とみなすことができる。）
シュワルツ空間  はフーリエ変換  の下で閉じている（急減少関数のフーリエ変換は再び急減少関数となる）という重要な性質を持つ。
この性質を利用し、緩増加超関数  のフーリエ変換  は、任意の急減少関数  に対して、以下の関係（プランシュレルの定理の一般化）を満たす超関数  として定義される。
ここで  は急減少関数  の（絶対可積分関数としての）フーリエ変換である。この定義により、超関数のフーリエ変換は再び緩増加超関数となる。
例：定数関数  を超関数  （）とみなす。そのフーリエ変換  は、定義より  となる。 ここで、 のフーリエ逆変換の定義  において  とおくと、 という関係が得られる（この関係は、急減少関数  に対して成立する）。 したがって、 である。 一方、 という超関数  は、定義により  である。 したがって、、すなわち定数関数  のフーリエ変換は  となる。
例：デルタ関数  （）のフーリエ変換  は、  これは、 という定数関数が定める超関数  の作用  に等しい。 したがって、デルタ関数  のフーリエ変換は定数関数  となる。
フーリエ変換 導入
この節では、フーリエ変換の「動機」の一つとして、フーリエ級数からの類推的な導入を解説する。この方法は、フーリエ変換がどのようにして関数を周波数成分の「連続的な集まり」として表現し直すかという直観的なイメージを掴む上で、歴史的にも教育的にも重要である。
フーリエ変換を考える動機はフーリエ級数の研究に始まる。フーリエ級数の研究において、複雑な周期関数は単純な波動の数学的な表現である正弦関数や余弦関数の和として表される。正弦や余弦の性質のおかげで、この和に現れる各波の量、フーリエ係数を積分によって計算することができる。
多くの場合に、（オイラーの公式）を用いて、正弦関数および余弦関数の代りに基本波動  を用いた方が便利である。この場合には多くの公式が簡単化され、本項で後述するフーリエ変換のほかの類似の定式化をあたえるという点に優位性がある。この正弦・余弦から複素指数関数への移行にはフーリエ係数が複素数値であることを要する。この複素数は、関数に含まれる波動の振幅（あるいは大きさ）と、位相（あるいは初期角）の両方を与えているものと通常は解釈される。また、この移行に際して「負の周波数」も導入される。例えば、波動  および  はともに周期1を持つが、複素フーリエ級数においては別々の成分として取り扱われる。したがって、周波数を単純に周期の逆数と考えることはできなくなる。
フーリエ変換 導入
フーリエ級数を以下のようにしてフーリエ変換の動機付けに用いることができる。関数 ƒ をある区間 [−L/2, L/2] の外側で 0 となるようなものとすると、任意の T ≥ L に対して ƒ を区間 [−T /2, T /2] 上のフーリエ級数に拡張できる。ここで f のフーリエ級数に現れる波動  の係数となる  で表される「量」は
で与えられ、ƒ は公式
で与えられなければならない。ξn = n/T とおき、Δξ = (n + 1)/T − n/T = 1/T とおくと、最後の和をリーマン和
として考えることができる。T → ∞ とすることにより、このリーマン和は定義節で与えられるフーリエ逆変換（積分）に収束すると期待される。このように、フーリエ変換は、関数に含まれる個々の周波数がどの程度あるかを（スペクトル密度  として）測るものと考えることができ、それらの波動を積分（「連続和」）によって再結合して元の関数を復元する操作がフーリエ逆変換に対応する。
以下の画像はフーリエ変換が特定の関数に含まれる周波数を測る方法を視覚的に現したものである。関数として、（t が秒で測られる場合には）3 ヘルツで振動し、急速に 0 になる
フーリエ変換 導入
を描く。この関数は特に描画しやすい実フーリエ変換をもつものとして選ばれたものであり、最初の画像はそのグラフである。ˆf(3) を計算するために、e−2πi(3t)ƒ(t) を積分する。二枚目の画像はこの被積分関数の実部および虚部である。被積分関数の実部は殆ど常に正となる。これは ƒ(t) が負であるときには e−2πi(3t) の実部が同様に負となることによる。それらは同じ比率で振動するから、ƒ(t) が正であるときも同様に e−2πi(3t) の実部も正になる。
この結果、被積分関数の実部のを積分すれば、比較的大きな数値（ここでの場合 0.5）を得ることになる。
一方、（ˆf(5) を見る場合のように）含まれない周波数を測れば、被積分関数は十分に振動し、それゆえにその積分はとても小さい値となる。一般の設定ではこれよりは少し複雑になるが、それでもフーリエ変換は関数 ƒ(t) に含まれる個々の周波数がどれくらいあるかを測るものという考え方に変わりはない。
この例では、ではなく、と、不自然ながかかっているが、は、(−∞, ∞)で絶対可積分関数としてのフーリエ変換（積分）が定義できないためである。（前述の通り、超関数としては定義可能である。）一方、は、のため(−∞, ∞)で絶対可積分であり、 が成り立つ。よって、 は全体として絶対可積分関数となり、フーリエ変換（積分）が可能となっているものである。
フーリエ変換 フーリエ変換の性質
実数直線上で定義される関数 f が絶対可積分であるとは、
を満たすルベーグ可測関数であることをいう。
絶対可積分関数 f(x), g(x), h(x) が与えられたとき、これらのフーリエ変換をそれぞれ ˆf(ξ), ˆg(ξ), ˆh(ξ)で表す。フーリエ変換は以下の基本性質を満たす。
線型性
任意の複素数 a, b について h(x) = aƒ(x) + bg(x) であるならば
が成り立つ。
平行移動
任意の実数 x0 に対して h(x) = ƒ(x − x0) であるならば
が成り立つ。
変調
任意の実数 ξ0 に対して h(x) = e2πixξ0ƒ(x) ならば
が成り立つ。
定数倍
非零実数 a に対し、h(x) = ƒ(ax) ならば
が成り立つ。a = −1 つまり h(x) = ƒ(−x) の場合には、時間反転性 (time-reversal property)
が導かれる。
複素共役
f(x) の複素共役 f(x) について
が成り立つ。
微分
関数  が（ で 0 に収束するなどの条件を満たし） 回微分可能で、その導関数も絶対可積分であるならば、  が成り立つ。逆に、  も成り立つ。この性質は、微分方程式を代数方程式に変換する上で重要である。
畳み込み
h(x) = (f ∗ g)(x) ならば
フーリエ変換 フーリエ変換の性質
が成り立つ。
絶対可積分関数のフーリエ変換は、常に成り立つというわけではない性質も持っている。絶対可積分関数 ƒ のフーリエ変換は一様連続で
を満たす。絶対可積分関数のフーリエ変換は
であることを述べたリーマン・ルベーグの補題をも満足する。絶対可積分函数 f のフーリエ変換 ˆf は有界連続だが絶対可積分であるとは限らず、その逆変換をルベーグ積分として書くことは一般にはできない。しかしながら、ƒ および ˆf がともに絶対可積分ならば、反転公式
が殆ど全ての x において成り立つ。つまり、ƒ は右辺で定義される連続関数と殆ど至る所等しい。特に ƒ が実数直線上の連続関数として与えられたならば全ての x において等式が成り立つ。
前述の結果としてわかることは、フーリエ変換が L1(R) 上単射であることである。
f(x) および g(x) は絶対可積分であるとし、そのフーリエ変換をそれぞれ ˆf(ξ) および ˆg(ξ) と表す。f(x) および g(x) がともに自乗絶対可積分であるならばパーセバルの定理
が成立する。ここで上付きバーは複素共役を表す。
パーセバルの定理と同値なプランシュレルの定理によれば
フーリエ変換 フーリエ変換の性質
が成立する。プランシュレルの定理により、L2(R) に属する関数の後述する意味でのフーリエ変換を定義することが可能になる。プランシュレルの定理は、フーリエ変換はもとの量のエネルギーを保存するという自然科学における解釈を持つ。著者によってはこれらの定理のどちらともをプランシュレルの定理あるいはパーセバルの定理と呼んでいる場合があるので注意を要する。
局所コンパクトアーベル群に関する文脈におけるフーリエ変換の概念の一般の定式化についてはポントリャーギン双対の項を参照されたい。
一般的に言って、f(x) が凝縮されればされるほどそのフーリエ変換 ˆf はより拡散される。特に、フーリエ変換のスケール性からわかることとして、関数を x において「圧搾」するならば、そのフーリエ変換は ξ において「伸展」される。したがって、関数とそのフーリエ変換の両方ともを勝手に凝縮させることはできない。
関数とそのフーリエ変換のコンパクト化のあいだの得失評価は不確定性関係の形で定式化することができる。ƒ(x) は絶対可積分かつ自乗絶対可積分であると仮定する。一般性を失うことなく関数 ƒ(x) は
に正規化されているものと仮定してよい。このとき、プランシュレルの定理により ˆf(ξ) も同様に正規化される。
フーリエ変換 フーリエ変換の性質
x = 0 の周りでの拡散を
で定義される「0 の周りでの分散」(dispersion about zero) によって測ることにする。確率の言葉で言えば、これは |f(x)|2 の 0 の周りでの二次のモーメントである。
このとき不確定性原理は、関数 ƒ(x) が絶対連続で、関数 x·ƒ(x) および ƒ′(x) が自乗絶対可積分であるならば
が成り立つことを述べる。等式が成立するのは
したがって、
である場合に限る。ただし、定数 σ > 0 は任意であり、係数 C1 は ƒ を L2-正規化する定数である。言い換えれば、 ƒ は 0 を中心に持つ（正規化）ガウス関数のとき等号が成り立つ。
事実として、この不等式は任意の x0, ξ0 ∈ R について
が成立することをも含む。
量子力学において、運動量と位置の波動関数は（プランク定数を因子に持つ）フーリエ変換対である。プランク定数でスケールしなおせば、上述の不等式はロバートソンの不確定性関係を記述する。これは、ハイゼンベルグが構想した不確定性原理そのものではないが、深い関係がある。
ポアソン和公式はフーリエ変換とフーリエ級数の間の関連性を提供する。絶対可積分関数 ƒ ∈ L1(Rn) が与えられたとき、ƒ の周期化が
フーリエ変換 フーリエ変換の性質
によって与えられる。このとき、ポアソン和公式は f のフーリエ級数を ƒ のフーリエ変換に結びつけるもので、特に f のフーリエ級数は
で与えられることを述べるものである。ポアソン和公式を用いて、大きな次元のユークリッド球面における格子点の数に対するランダウの漸近公式を導出することができる。また、絶対可積分函数 f と ˆf がともにコンパクト台を持つならば ƒ = 0 を示すこともできる。
フーリエ変換は、関数の畳み込みと関数の（点毎の）積とを相互に変換する。ƒ(x) および g(x) が絶対可積分関数であるとし、そのフーリエ変換をそれぞれ ˆf(ξ) および ˆg(ξ) で表す。さらに ƒ と g との畳み込みが存在して絶対絶対可積分であるならば、この畳み込みのフーリエ変換はフーリエ変換 ˆf(ξ) と ˆg(ξ) との積で与えられる（ただし、フーリエ変換の定義の仕方によっては定数因子が現れる場合もある）。
これを式で表せば、∗ を畳み込みとして
と表されるとき、
が成立することを意味する。線型時不変 (LTI) 系理論において、f(x) を単位インパルスで置き換えたものが h(x) = g(x) を与えることから、通例 g(x) は、入力 ƒ(x) と出力 h(x) に関する LTI 系のインパルス応答として解釈される。この場合、ˆg(ξ) はこの系の周波数応答を表す。
フーリエ変換 フーリエ変換の性質
逆に、ƒ(x) がふたつの自乗絶対可積分函数 p(x) および q(x) の積に分解されるならば、 ƒ(x) のフーリエ変換は、各因子のフーリエ変換 ˆp(ξ) および ˆq(ξ) の畳み込みで与えられる。
同様の方法で、h(x) が ƒ(x) と g(x) との相互相関
であるならば h(x) のフーリエ変換が
で与えられることが示される。
L2(R) の正規直交基底の重要な一つはエルミート函数系
で与えられる。ここで Hn(x) は「確率論者の」エルミート多項式と呼ばれる、 で定義される関数である。この規約の下、フーリエ変換は
フーリエ変換 フーリエ変換の性質
で与えられる。言い換えれば、エルミート関数系は L2(R) 上のフーリエ変換の固有関数からなる完全正規直交系を成す。しかしながら、この固有関数系の選び方は一意ではなく、フーリエ変換の相異なる固有値は {±1, ±i} の 4 つしかなく、同じ固有値に属する固有関数の任意の線型結合はふたたび固有関数になる。この結果として L2(R) を 4 つの空間 H0, H1, H2, H3 で、フーリエ変換が Hk 上で単に ik-倍として作用するものの直和に分解することができる。この方法によるフーリエ変換の定義はウィーナーによる。エルミート関数を選ぶのが便利なのは、それらが周波数域と時間域の両方で指数関数的に局在することと、それゆえに時間周波数解析において用いられる非整数次フーリエ変換が得られることにある 。
で次数 k の斉次調和多項式全体の成す集合を表す。集合  は体球面調和関数系として知られる。高次元において体球面調和関数系はエルミート多項式と同様の役割を演じる。具体的には、 の適当な P(x) に対し、f(x) = e−π|x|2P(x) のフーリエ変換は
で与えられる。集合  を f(|x|)P(x) (P(x) ∈ ) の形の関数から作られる線型結合全体の成す集合の L2(Rn) における閉包とする。このとき、空間 L2(Rn) は空間  の直和に分解され、フーリエ変換は各空間  をそれ自身に移す。また、各空間  へのフーリエ変換の作用を特徴付けることができる。ƒ(x) = ƒ0(|x|)P(x) (P(x) ∈ ) と表される関数のフーリエ変換は
となる。ただし、
であり、J(n + 2k − 2)/2 は次数 (n + 2k − 2)/2 の第一種ベッセル関数である。k = 0 のとき、これは動径関数のフーリエ変換に対する有用な公式を与える。
フーリエ変換 一般化
フーリエ変換の定義を他の函数空間に対するものへ拡張することができる。コンパクト台を持つ滑らかな函数は絶対可積分で、その全体は L2(R) において稠密であるから、プランシュレルの定理を用いて、L2(R) の一般の函数にまで（コンパクト台をもつ滑らかな函数によって近似して）フーリエ変換の定義を拡張することができる。さらに
はユニタリ作用素である。フーリエ変換の多くの性質はこの場合にもそのまま成立する。ハウスドルフ・ヤング不等式を用いて 1 ≤ p ≤ 2 に対する Lp(R) の函数を含むようにフーリエ変換の定義を拡張することができる。
だが、さらなる拡張はもっと技巧的である。2 < p < ∞ の範囲でのLp に属する函数のフーリエ変換には超函数の研究が必要である。事実として、p > 2 に関する Lp に属する函数のフーリエ変換は函数としては定義できないことを示すことができる 。
フーリエ変換は勝手な次元 n において考えることができる。1-次元の場合と同様にさまざまな流儀があるが、本項では絶対可積分函数 ƒ(x) に対して、
をフーリエ変換の定義とする。ここで、x および ξ は n-次元ベクトルであり、x · ξ はベクトルの点乗積である。点乗積はしばしば <x, ξ> とも書き表される。
フーリエ変換 一般化
プランシュレルの定理やパーセバルの定理がそうであるように、上述の基本性質は n-次元フーリエ変換においても成立する。函数が絶対可積分であるとき、フーリエ変換はやはり一様連続であり、リーマン・ルベーグの補題が成立する。
より高い次元ではフーリエ変換の制限問題の研究が興味深いものになる。絶対可積分函数のフーリエ変換は連続で、この函数の任意の集合への制限が定義される。しかし自乗絶対可積分函数のフーリエ変換は自乗絶対可積分函数の一般の類を成す。そのような L2(Rn)-函数のフーリエ変換の制限は測度 0 の集合上では定義することができない。1 ≤ p ≤ 2 に対する Lp における制限問題の理解はいまだ活発な研究の行われる領域である。驚くべきことに、集合 S の曲率が非零であるようないくつかの場合には、フーリエ変換の S への制限を定義することができる。S が Rn における単位球面であるときが特に興味深い。この場合に、トマス-ステインの制限定理によれば、フーリエ変換の Rn における単位球面への制限は 1 ≤ p ≤ (2n + 2)/(n + 3) に対する Lp 上で有界作用素である。
1-次元の場合と多次元の場合とで、フーリエ変換の大きな違いは部分和作用素に関係する。与えられた絶対可積分函数 ƒ に対し
フーリエ変換 一般化
で定義される函数 ƒR を考える。さらに ƒ が Lp(Rn) に属すると仮定する。n = 1 で 1 < p < ∞ とし、SR = (−R, R) と置くと、ヒルベルト変換の有界性から ƒR は R を無限大に飛ばす極限で ƒ に Lp 内で収束する。素朴に n > 1 の場合にも同様であることを期待するかもしれない。SR を一辺の長さが R の立方体とするならば、確かに部分和作用素はもとの函数に収束する。別の自然な候補としてユークリッド球体 SR = {ξ : |ξ| < R} をとると、部分和作用素が収束するためには単位球体に対するマルチプライヤーが Lp(Rn) において有界である必要がある。n ≥ 2 に対しては、単位球体に対するマルチプライヤーは p = 2 でない限り有界にはならないというよく知られたチャールズ・フェファーマンの定理がある。事実として、p ≠ 2 のときには ƒR が ƒ に Lp 内で収束しないだけではなく、函数 ƒ ∈ Lp(Rn) であっても ƒR が Lp の元でさえないようなものまでが存在する。
Rn 上の有限ボレル測度 μ のフーリエ変換は
フーリエ変換 一般化
によって与えられる。この変換は絶対可積分函数のフーリエ変換がもつ多くの性質を引き続き満足する。大きな違いの一つに、測度に関してリーマン・ルベーグの補題が成り立たないことが挙げられる。dμ = ƒ(x)dx の場合には上述の定義式を f の通常のフーリエ変換の定義に簡約化することができる。
このフーリエ変換を用いて連続測度の特徴づけを与えることができる。ボホナーの定理はそのような函数を測度のフーリエ・スティルチェス変換として得られるものとして特徴付ける。
さらに言えば、ディラックのデルタ函数は函数ではないが有限ボレル測度であり、そのフーリエ変換は定数函数となる（特殊値は用いるフーリエ変換の形に依存する）。
フーリエ変換を任意の局所コンパクトアーベル群に対して一般化することができる。局所コンパクトアーベル群とは、抽象アーベル群であると同時に局所コンパクトなハウスドルフ空間であって、なおかつその位相に関して群演算が連続となるものである。G が局所コンパクトアーベル群ならば、G はハール測度と呼ばれる平行移動不変な測度 μ を持つ。また、局所コンパクトアーベル群 G に対して、その位相を指標全体の成す集合 ˆG へ移行することができて、ˆG 自身も局所コンパクトアーベル群の構造を持つ。L1(G) に属する函数 f に対して、そのフーリエ変換を
によって定義することができる。
この一般化を概周期函数に適用した理論や、準周期函数に適用した理論が知られている。
フーリエ変換 応用
フーリエ変換は、関数を周波数成分に分解するというその性質から、理論的な解析から実践的なデータ処理まで、科学・工学の極めて広い分野で応用されている。
フーリエ変換は、微分作用素を（周波数変数に関する）単純な掛け算に変換する性質を持つ。例えば、関数  の導関数  のフーリエ変換は  となる（定義による定数の違いあり）。この性質を利用することで、線型微分方程式を、周波数領域における代数方程式に変換して解くことができる。
特に、熱伝導方程式や波動方程式、シュレーディンガー方程式のような偏微分方程式の解法において強力な道具となる。フーリエがこの変換を導入した直接の動機も、熱伝導方程式の解析であった。
信号処理は、フーリエ変換の最も代表的な応用分野の一つである。
フィルタリング: 信号から特定の周波数成分を除去（例：ノイズ除去）したり、特定の周波数成分のみを通過させたりする操作（フィルタリング）は、周波数領域で容易に行うことができる。例えば、不要な高周波成分を除去するローパスフィルタは、周波数領域で  に特定の関数（高周波域で0になる関数）を掛け合わせ、それを逆フーリエ変換することで実現される。これは、畳み込み定理に基づいている。
フーリエ変換 応用
2次元フーリエ変換は、デジタル画像処理において広く用いられる。画像は空間的な輝度（または色）の分布であり、そのフーリエ変換は空間周波数（画像の模様の細かさや向き）のスペクトルを表す。
量子力学において、粒子の状態は波動関数  で記述される。位置  に関する波動関数  と、運動量  に関する波動関数  は、互いにフーリエ変換（の定数倍）の関係にある。
この関係は、粒子の位置と運動量を同時に正確に決定することはできないという不確定性原理の数学的な表現（不確定性関係）と密接に関連している。
フーリエ変換 離散フーリエ変換
現実の信号処理や画像処理では、コンピュータを用いて数値的にフーリエ変換を計算する必要がある。この目的で用いられるのが、連続的な関数ではなく、離散的な（サンプリングされた）データ列を扱う離散フーリエ変換（英: Discrete Fourier Transform, DFT）である。
DFTは、有限個のデータ点  から、有限個の周波数成分  を計算する変換であり、その計算を劇的に高速化するアルゴリズムが高速フーリエ変換（英: Fast Fourier Transform, FFT）である。
FFTの登場により、膨大なデータに対しても実用的な時間でフーリエ変換（およびその逆変換）が計算可能となり、上記のような信号処理や画像処理の応用が爆発的に普及する基盤となった。
フーリエ変換 フーリエ変換の定義域と値域のまとめ
フーリエ変換は、定義する関数の空間（定義域）によって、変換後の関数の属する空間（値域）が異なる。主な空間と変換の性質を以下にまとめる。
フーリエ変換 その他の記法
フーリエ変換の記法として ˆf(ξ) 以外によく用いられるものに
などがある。あるいはもっと他の記号を使うことも在りうる。たとえば、（f(x) と F(ξ) のように）もとの函数を表している文字の対応する大文字を用いてそのフーリエ変換を表すことは自然科学や工学においてとくによく用いられる記法である。
複素函数 ˆf(ξ) は、極座標に関してこれを表示することにより、振幅
および位相
と呼ばれるふたつの実函数 A(ξ) および φ(ξ) を用いて
なる形に解釈することができる。
このとき逆変換は ƒ(x) の周波数成分すべての再結合として
と書くことができる。各成分は振幅が A(ξ) で（x = 0 における）初期位相角が φ(ξ) であるような e2πixξ のかたちの複素正弦曲線である。
フーリエ変換 その他の記法
フーリエ変換は函数空間の間の写像として考えることもできる。この写像はここでは  で表し、函数 f のフーリエ変換には  が用いられる。この写像  は函数空間上の線型変換とみることができ、それによって  と書く代わりに、ベクトル（ここでは函数 f）の線型変換を表す線型代数学の標準的な記法で  と書くこともできる。函数にフーリエ変換を施した結果は再び函数となるから、この新たな函数の ξ における値というものには意味があり、それを  あるいは  などと表す。前者の場合には  はまず f に施されて、その後に得られた函数の ξ における値が評価されるものと暗黙に理解されているということに注意しなければならない。なお、混乱を防ぐため（そしてラプラス変換の記法と統一して）括弧の種類を変えてのように書く場合もある。
数学や多くの応用科学において、函数 f それ自身と函数 f の変数 x における値 f(x) とを峻別しなければならないことがしばしばある。このことが意味するのは、たとえば のような記法は、形式的には f の x における「値」のフーリエ変換と解釈できてしまうということである。このような不具合にもかかわらず、特定の函数あるいは特定の変数の函数を頻繁に変換しなければならないような場合には、このような記法はよく用いられる。たとえば
は矩形函数のフーリエ変換が sinc-函数であることを表すために用いられることがあり、またたとえば
はフーリエ変換のシフト性を表すのに用いられることがある。最後の例は、変換される函数 f をx0 のではなく x の函数であるという前提のもとでのみ正しいということに注意を要する。
フーリエ変換 主なフーリエ変換の一覧
以下にフーリエ変換の閉じた表示に関する表を掲げる（フーリエ変換はよく用いられる三種類を挙げてある）。函数 ƒ(x) , g(x), h(x) に対して、それらのフーリエ変換をそれぞれ ˆf, ˆg, ˆh で表す。
以下の表におけるフーリエ変換は (Erdélyi 1954) あるいは (Kammler 2000) の付録に見つけることができる。
以下の表におけるフーリエ変換は (Campbell & Foster 1948), (Erdélyi 1954) あるいは (Kammler 2000) の付録に見つけることができる。
以下の表におけるフーリエ変換は (Erdélyi 1954) あるいは (Kammler 2000) の付録に見つけることができる。
数学的帰納法
数学的帰納法（すうがくてききのうほう、英: mathematical induction）は、数学における証明の手法の一つである。
例えば自然数に関する命題 P(n) が全ての自然数 n に対して成り立つことを証明するために、次のような手続きを行う。
数学的帰納法 概要
自然数に関するペアノの公理の中に、ほぼ等価なものが含まれている。
なお、数学的「帰納」法という名前がつけられているが、数学的帰納法を用いた証明は帰納ではなく、純粋に自然数の構造に依存した演繹論理の一種である。2 により次々と命題の正しさが"伝播"されていき、任意の自然数に対して命題が証明されていく様子が帰納のように見えるためこのような名前がつけられた。ジョン・ウォリスによって、彼の著作Arithmetica Infinitorumの中で、この方法にinductionという名前が与えられたとされる。
数学的帰納法 直観的説明
高校の教科書等の初等的な解説書ではドミノ倒しに例えて数学的帰納法を説明しているものも多い。P(n) を「n 枚目のドミノが倒れる」の意味だとすれば、上の論法は以下のようになる：
数学的帰納法が成り立つ直観的理由は以下の通りである。まず1より
(a) P(1)
が正しいことが分かる。次に k = 1, 2, ... に対して 2 を適用することで、
(b) P(1) ⇒ P(2),
(c) P(2) ⇒ P(3),
…
が分かる。(a), (b) より、P(2) が成り立ち、この事実と (c) を組み合わせることにより P(3) が従う。以下同様に P(4), P(5), … も従い、結局3の
全ての自然数 n に対し P(n) が成り立つ
が結論づけられる。
ただし、以上の議論はあくまで数学的帰納法が成り立つ理由の直観的説明であって、1, 2 と 3 の間にはギャップがある。詳しくは後述の「数学的帰納法の形式的な取り扱い」の項目を参照されたい。
数学的帰納法 証明
数学的帰納法が成り立つことを数学的帰納法の原理といい、ペアノの公理Ⅴが数学的帰納法の原理そのものを表している。もし、公理Vを用いて、数学的帰納法をあえて証明するならば、以下のように示すことができる。
自然数の集合を  とし、命題  が成り立つ  の集合を  とする。
(1) 数学的帰納法の仮定により、 は  の要素である。
(2) 任意に自然数  をとる。 を仮定すると、 の定義によって  が成り立つ。このとき、数学的帰納法の手順より、 も成り立つ。ふたたび、 の定義によって  である。これにより  が示されたことになる。
(1) および (2) により、ペアノの公理Vによって  が得られる。部分集合の定義により、これは  であることを意味する。(証明終)
数学的帰納法 バリエーション
数学的帰納法には次のようなバリエーションもあり、場合によってはこれらを用いる必要がある。これらのバリエーションの正しさは、上で述べた標準的な形の数学的帰納法を用いて示すことができる。
変数変換によって明らかなように、変数 n が表す範囲は n → n + 1 という操作で閉じていれば {1, 2, ...} である必要はなく、0 を自然数に含めることにしたり、あるいは任意の整数 m に関する {m, m + 1, ...} という範囲でもよいことになる。
例えば n → n + 1 ではなく、n → n + 2 で証明し、開始点が P(2) であれば、全ての正の偶数で証明できる。バリエーションとしては、P(2) から n → n + 2 で正の偶数を証明し、P(1) から n → n + 2 で正の奇数を証明し、よって全ての自然数で成立するという証明方法もある。他にも、P(0) から n → n + 1 と n → n − 1 を両方証明し、全ての整数で成立することを証明するという場合もある。
数学的帰納法 バリエーション
仮定として P(k) だけでなく P(1) から P(k − 1) までのすべて（もしくは一部）を用いる。これを完全帰納法（英: complete induction、これは同じく完全帰納法と訳される perfect induction とは別物）もしくは累積帰納法（英: course of values induction）という。
任意の自然数 k をとったとき、k より真に小さなすべての自然数 m に対して P(m) が真であれば、P(k) も真である。
よって任意の自然数 n について P(n) は真である。
無限降下法とは、背理法を用いて  を証明する、次のようなパターンのことである。
が成立しないような自然数  が存在すると仮定し、その中で最小のものを  とする。次に、 を仮定すると、「ある自然数  が存在して  ではないこと」を導けることを示す。これは  の最小性に矛盾するから、背理法により、 が成立しないような自然数  は存在しない。すなわち、すべての自然数  に対して  が成り立つ。
この議論と前に述べた「先立つすべての結果を用いる」形の数学的帰納法の正しさは自然数全体の集合  が通常の大小関係  によって整列されていることによる。 が  上の整列順序であることは、最初に述べた標準的な形の数学的帰納法を用いることで証明される。
数学的帰納法は自然数に関する論法だが、自然数以外の集合に対しても、集合の元を適切に順序づけることで数学的帰納法を適用できることがある。例えば直積集合 N × N 上に辞書式順序
(x, y) > (x′, y′)
: ⇔ (x > x′) または (x = x′ かつ y > y′)
を入れることで N × N 上でも数学的帰納法が使える。
数学的帰納法 数学的帰納法の例
次の等式が成り立つという命題を P(n) とし、この命題が任意の自然数 n について成立することを数学的帰納法を用いて証明する。
まず、P(1) は右辺を計算することで、正しいことが確かめられる。
右辺 = (1(1+1))/2 = 1 = 左辺。
次に、任意の自然数 k をとる。P(k) は下記の通りであり、これが成立すると仮定する。
これが成立することを使い、 P(k + 1) の左辺を計算すると、P(k + 1) も成立することが分かる。
以上から、数学的帰納法により、任意の自然数 n について命題 P(n) が成立する。(証明終)
数学的帰納法 数学的帰納法の形式的な取り扱い
数学的帰納法の原理を説明する前に、まず前述した直観的説明のどこにギャップがあったのかを説明する。前述の説明では、まず我々は P(1) を結論づけ、次に (a), (b) から P(2) を結論づけ、さらにそれと (c) を組み合わせることで P(3) を結論づけ、さらにそれと(d)を組み合わせることで P(4) を結論づけた。以上の議論から分かるように、P(2) を結論づける為には2ステップの推論、P(3) を結論づけるには3ステップの推論、…、P(100) を結論づけるには100ステップの推論が必要となる。
従って有限回のステップでは有限個の n に対してしか P(n) を結論づけることができず、「無限個ある自然数全てに対して P(n) が成り立つ」という数学的帰納法の結論について無限の長さの証明が与えられたとはいえない。これが前述した直観的説明におけるギャップである。
そこで、ペアノ算術などの形式的な体系では、数学的帰納法を証明に用いてよいことが公理として仮定されるのが普通である。つまり、形式的には、自然数の性質から数学的帰納法の正しさが証明できるのではなく、逆に自然数の本質的な性質を与える推論規則として数学的帰納法が仮定される、ということになる。
数学的帰納法 数学的帰納法の形式的な取り扱い
集合論の枠組みでは、数学的帰納法の原理を次のように表すことができる。
自然数 N の部分集合 A が空でないとき、A に属する最小の自然数が存在する。
この原理からもともとの形の数学的帰納法が導かれることは，次のようにして示せる。帰納法の仮定 1., 2. を満たす論理式 P(n) が与えられたとする。自然数の部分集合 A を A = { n ∈ N: ¬ P(n) } によって定める。この A が空集合であるということを示したい。そうでないと仮定すると、Aに属する最小の自然数 a を取ることができるが、P(0)は成り立っていることから a は0でない。従って、ある自然数 b について a = b + 1となっているが、a は A に属する最小の自然数であったということから、b ∉ A であり、P(b) は成り立つことになる。帰納法の仮定から P(a) も成り立つことになり、これは矛盾である。
数学的帰納法 数学的帰納法の形式的な取り扱い
逆に、「n 以下の任意の自然数 k について k ∉ A」という形の命題 P(n) を考えることで、数学的帰納法から上の原理を導くことができる。A を自然数のある集合とし、A に属する最小の自然数が存在しないと仮定する。もし P (0) が成り立たないと、0 が A に属する最小の自然数となって仮定に反するから、P(0) は成り立つ。P(n) が成り立つとし、もし P (n + 1) が成り立たないとすると、n + 1 が A の最小の自然数となって仮定に反するから、P(n + 1) も成り立つ。よって数学的帰納法により A は空となる。
数学的帰納法 超限帰納法
上記の形で自然数について定式化された数学的帰納法は、任意の整列集合に対して次のように一般化することができる。この一般化を超限帰納法 (ちょうげんきのうほう、英: transfinite induction)という。数学的帰納法とは違い、順序数すべて（有限も無限も)を対象として構築できる。任意濃度の集合は選択公理と同値な整列可能定理により整列順序を持つとすることができるので、選択公理を含む公理系であれば超限帰納法は任意濃度の集合に対して成立すると主張できる。
超限帰納法
(A , ≤) を整列集合とし、P(x) を A 上で定義された命題関数とする。もし次の条件が成立するならば、任意の x ∈ A について P(x) は真である。
条件
a を A の任意の元とする。x < a を満たす A の全ての元 x について P(x) が真ならば、P(a) も真である。
ただし、"<" は a < b ⇔ ( a ≤ b ∧ a ≠ b) で定義される二項関係とする。
数学的帰納法 超限帰納法
A を全体集合とする。A の各元 a に対して A(a) = { x∈A  |  x < a } とし、A1 = { x∈A  |  P(x) } とする。そのとき、超限帰納法の条件は
と同値である。また、補集合に関する法則から (1) は
と同値である。これらの条件が満たされているという前提の下で、A1 = A すなわち A1c = ∅ が成り立つことを示せばよい。
いま、A1c ≠ ∅
と仮定して矛盾を導く。背理法の仮定と整列集合の定義より、min A1c = a が存在する。この a について、最小元の定義より A(a)∩A1c = ∅ が成り立つので、 (2) より a ∈ A1 もまた成り立つ。しかし、これは a ∈ A1c であることに反する。（証明終）
数学的帰納法 整礎帰納法
無限下降列が存在しない二項関係を整礎関係という。整礎関係が定義された集合に対して次が成り立つ。これを整礎帰納法（英: well-founded induction）という。
R を集合 A 上の整礎関係とし、P(x) を A の元 x に関する命題とする。もし次が成立するならば、任意の x ∈ A について P(x) は真である。
任意の a ∈ A をとる。x R a なる任意の A の元 x について P(x) が真ならば、P(a) も真である。
超限帰納法は整礎帰納法の特殊な場合である。特に、超限帰納法においては、任意の空でない部分集合に最小元が存在する、という性質が、整礎帰納法においては、任意の空でない部分集合に極小元が存在する、という性質に対応している。
数学的帰納法 ハゲ頭のパラドックス
数学的帰納法を意図的に誤用したジョークとして、次のようなものがある：
髪の毛が一本もない人はハゲである。ハゲの人に髪の毛を一本足してもやっぱりハゲである。よって数学的帰納法により、全ての人はハゲている。
もちろんこの「証明」には理論上の根本的な問題点がある。この「証明」の問題点は、「ハゲ」の定義を厳密に毛が何本以下であるかで与えることができない点、もしくは「ハゲ」を定義できたとして、任意の「ハゲ」に髪の毛を一本足したときに、必ず「ハゲ」になるわけではない点にある。以上のような論法の起源は、古代ギリシャの哲学者ミレトスのエウブリデス (en) が作ったとされるハゲ頭のパラドックス (Paradox of the Bald Man)に帰せられる。これは砂山のパラドックスの起源としても知られる。
前述のジョークにはさまざまなバリエーションがあるが、いずれも「少量の増加程度では大差ない。よって数学的帰納法より沢山の増加でも差はない」という誤謬を利用している。
数学的帰納法 歴史
初期の例としては、プラトンによるパルメニデス（紀元前 370年）において暗黙に帰納法を使用した証明がみられる。また数学的帰納法としての痕跡は、素数が無限個あることを示したユークリッドの証明や、バースカラ2世による "cyclic method" に見ることができる。通常とは逆に、パラメータとなる自然数が減少していく逐次的な論法は、砂山のパラドックスにみられる。つまり、10,000粒の砂粒が砂山を形成し、そこから一粒の砂を取り除いても砂山が残るならば、一粒だけ残った砂(或いは全ての粒を取り去った後)でもなお砂山を形成するといえる。
等差数列について暗黙に数学的帰納法を用いた証明は、紀元 1000年ごろにアル＝カラジによる "al-Fakhri" に扱われている。アル＝カラジは二項定理やパスカルの三角形を示すのに数学的帰納法を用いた。
数学的帰納法 歴史
しかし、これらの古代の数学者たちは帰納法の仮定を明示することはしていない。別の似た例としては(Freudenthal が注意深く示したように、Vacca が著したものとは対立するが)、フランチェスコ・マウロリコが 1575年の著作 "Arithmeticorum libri duo" にて最初の n 個の奇数の和が n2 に等しいことを示す際にこの技術を用いている。明示された形での数学的帰納法の原理はパスカルがその著作 "Traité du triangle arithmétique" (1655)にて与えた。フランス人フェルマーは、帰納法と関連する、無限降下法による間接的な証明をうまく使っている。帰納法の仮定はヤコブ・ベルヌーイによっても使われ、以後多少よく知られるようになった。現代的な厳密さをもち体系的な数学的帰納法の原理の扱いは 19世紀に入ってジョージ・ブール、オーガスタス・ド・モルガン、チャールズ・サンダース・パース、ジュゼッペ・ペアノ、 リヒャルト・デーデキントによって為された。
安定ソート
安定ソート（あんていソート、stable sort）とは、ソート（並べ替え）のアルゴリズムのうち、順位が同等な複数のデータのソート前の前後関係が、ソート後も保存されるものをいう。つまり、ソート途中の各状態において、常に順位の位置関係を保っていることをいう。
たとえば、学生番号順に整列済みの学生データを、テストの点数順で安定ソートを用いて並べ替えたとき、ソート後のデータにおいて、同じ点数の学生は学生番号順で並ぶようになっている。
安定でないソート法を用いる場合でも、整列したいデータに元のデータ列の順序を追加しておき、ソートする際にその情報を参照するようにすれば、安定ソートに変更できる。形式的には、ソートしたい項目と元の順番を表す項目のペアを辞書式順序でソートする、ということである。この方法は（入力データ自体が元々順番を表す項目を含んでいるのでない限り）元の順番を表す情報を記憶する必要がある。すなわち、長さ n の入力に対し、0 から n-1 までの連番を一時的に記憶するのだから、 の記憶容量を必要とする（必要となる一時変数の個数という意味では ）。したがって内部ソートが必要な場合には使えない。
階乗
数学において自然数 n の階乗（かいじょう、英: factorial）n ! とは、1 から n までの全ての自然数の積のことである。例えば、
である。空積の規約の下 0! = 1 と定義する。
階乗は数学の様々な場面に出現するが、特に組合せ論、代数学、解析学などが著しい。階乗の最も基本的な出自は n 個の相異なる対象を1列に並べる方法（対象の置換）の総数が n! 通りであるという事実である。
階乗の定義は、最も重要な性質を残したまま、非整数を引数とする函数に拡張することができる。そうすれば解析学における著しい手法などの進んだ数学を利用できるようになる。
階乗 定義
いくつか同値な条件により定義することが可能である。
上記の何れの定義においても、
となることが織り込み済みである（最初の定義では「 0 項の積は 1 と定める」という規約によって）。このように定義する理由は:
など様々に挙げることができる。
より進んだ数学においては、引数が非整数の場合にも階乗函数を定義することができる（後述）。そういった一般化された定義のもとでの階乗は関数電卓や、Maple や Mathematica などの数学ソフトウェアで利用できる。
多くのプログラミング言語において、再帰的な定義を利用し、プロシージャの再帰呼び出しを用いた階乗の実装が可能である。
以下はC言語での例である。例示するコードではunsigned long long型を使用しているが、unsigned long long型では小さな階乗（21!）でもオーバーフローしてしまうため、大きな階乗については任意精度演算による実装を検討すべきである。
階乗 組合せ論
階乗を含む公式は数学の多くの分野に現れるが、階乗のおおもとの出自は組合せ論にある。相異なる n 個の対象の順列（k-順列）の総数は n! 通りである。
階乗はしばしば「順番を無視する」という事実を反映するものとして分母に現れる。古典的な例としては n 個の元から k 個の元を選ぶ組合せ（k-組合せ）の総数が挙げられる。このような組合せは順列から得ることができる。実際、k-順列の総数
において、順番のみが違う（k-組合せでは違いが無視される）k-順列が k ! 通りずつ存在するから、k-組合せの総数は
となる。この数は、二項冪 (1 + X)n における Xk の係数となることから、二項係数  とも呼ばれる。
代数学に現れる階乗にはいくつも理由があるが、既述の如く二項展開の係数として現れたり、ある種の演算の対称化 において置換による平均化を行うなど、組合せ論的な理由で現れるものもある。
微分積分学においても階乗は例えばテイラー級数の分母として現れるが、これは冪函数 xn の n 階導函数が n ! であることを補正する定数である。確率論でも階乗は用いられる。
階乗は数式操作にも有効である。例えば n の k-順列の総数を
と書けば、（この数値を計算することを考えれば効率が悪くなるが）二項係数の対称性
を見るには都合がよい。
階乗 数論における階乗
階乗は数論にも多くの応用を持つ。特に n ! は n 以下の全ての素数で整除されねばならない。このことの帰結として、n ≥ 5 が合成数となる必要十分条件は
が満たされることである。より強い結果としてウィルソンの定理は
が p が素数であるための必要十分条件であることを述べる。
ルジャンドルの公式は n ! の素因数分解に現れる p の重複度が
であることを示す。これは
に等しくなる。ただし、sp(n) は n の p進展開の係数の和である。
n ! が素数となる n は 2 のみである。n! ± 1 の形の素数は階乗素数と呼ばれる。
1! より大きな階乗は全て偶数である（これらは明らかに因数 2 を持ち、2 の倍数である）。同様に、5! より後の階乗は 10 の倍数（2 と 5 を因数に持つ）であり、十進展開の末尾には 0 が並ぶ。
ブロカールの問題とは、
を満たす n, m は存在するか、という問題である。2015年9月現在、これを満たす (n, m) の組は
(4, 5), (5, 11), (7, 71)
しか見つかっていない。ABC予想が真であれば、解は有限個しかないことが、Marius Overholt により示されている。
階乗 階乗の解析学
階乗の逆数の総和は収束級数
を与える（ネイピア数を参照）。この和は無理数となるけれども、階乗に適当な正整数を掛けて和が有理数となるようにすることができる。例えば、
この級数の値が 1 となることを見るには、その部分和が 1 − 1/(n+2)! であることを確認すればよい。したがって、階乗数の全体は無理列を成さない。
n が増えるにつれて、階乗 n ! は n を変数とする任意の多項式函数あるいは指数函数よりも早く増加する（ただし、二重指数関数よりは遅い）。
n ! の近似式の多くは自然対数
であることを利用する。最も単純に得られる log(n!) の近似値を評価する式は、上記の式と以下の積分:
によって与えられる。積分を評価すれば
を得る。これは、ランダウの記号を用いれば log(n!) のオーダーは Θ(n log n) であることを言っているのであり、この結果はソートアルゴリズムの計算量を測るのに重要な役割を果たす。さて上記の log(n!) の評価から
階乗 階乗の解析学
が分かる。実用上はより弱い結果だがより評価のしやすいものを用いることもある。上記の式から簡単な評価をしてみると、任意の n に対して (n/3)n < n!  であり、また n ≥ 6 のとき n! < (n/2)n であることなどが分かる。
大きな n に対して n ! をよりよく評価するにはスターリングの公式
を利用する。（ここで  は両辺の比が 1 に収束することを表す。）実は任意の n に対して
であることが証明できる。
log(n !) の別な近似はシュリニヴァーサ・ラマヌジャンにより
したがって
と与えられている。この近似の誤差は、スターリングの公式よりも小さい。