絶対値の場合分けを減らしたい
はじめに
どうもこんにちは、🐟️🍊みかん🍊🐟️です。今回は絶対値について喋ってみようと思います。今回のテーマは「検証時の場合分け回数の最小化を図る」です。実は場合分けしなくても絶対値式同士の相当は示せる場合が多いのですが、結局のところ計算量を増大させることも多いのであまり意味がありません。さて、絶対値関数$\lvert x\rvert$は、皆さんがご存じのように
$$ \lvert x\rvert:=\operatorname{max}(x,-x)=\begin{cases}x&x\ge0\\-x&x<0\end{cases} $$
で定義される関数で、特にこれは実数体のノルムであることはよく知られています。よく習う記号$\left\lvert x\right\rvert$はWeierstrassが考案したもので広く用いられていますが、括弧の形が開きも閉じも全く同じであるという害悪極まらない形をしていて、例えばTeXの仕様を知らないなら次の2つの式を識別することは困難です。(できない方はTeXコードを参照してみましょう)
\begin{aligned} &\lvert x\lvert x\rvert-1\rvert \\ &\lvert x\rvert x\lvert-1\rvert \end{aligned}
普段手書きするときには非対称的な別の括弧を使うことでごまかしていますが、TeXに読み込ませるのが面倒なのでlvertとrvertで書いています。(といっても見た目上同じ記号...)
ざっくりといえば絶対値を含む多項式を絶対値式といいますが、多変数の場合も含めそれなりに僕によって研究されていて、そこそこ著しい結果が得られています。なお、この記事では略記のため他変数に対しては
$$ \bm X=(X_1, X_2, \dots, X_n) $$
のような多重指数的な記法を用いることがあります。また、この記事での等号は点ごとでの一致としておきます。
独自定義
この章では僕が新しく定義したものを書いていきます。最初の定義は読まなくてもどうにかなります(そういう風に記事を作ってあります)。とりあえず考える対象を明確化させている、と捉えていただければ構いません。
まず$\mathbb R[\bm X]$を実数係数の多項式として
$$
\mathbb{A}_{\mathbb{R}_0}[\bm X]=\mathbb R[\bm X]
$$
とする。さらに一般の$n\in\mathbb{N}^\times$に対して
$$
\mathbb{A}_{\mathbb{R}_{n+1}}[\bm X]=\left\{f\lvert g\rvert+h:f,g,h\in\mathbb{A}_{\mathbb{R}_n}[\bm X]\right\}
$$
として全ての自然数$n$に対して$\mathbb{A}_{\mathbb{R}_n}[\bm X]$を定義する。この集合の元を速度$n$の絶対値式という。また集合
$$
\mathbb{A_R}[\bm X]=\left\{h:\exists n\in\mathbb{N}\left[h\in\mathbb{A}_{\mathbb{R}_n}[\bm X]\right]\right\}
$$
の元を絶対値式という。
この定義では分かりにくいかもしれませんが、実は「多項式を含み、(有限回の)和と積と絶対値を取る動作それぞれについて閉じている最小の集合である」という性質を満たすことが知られています。なので、こちらを元に定義しても構いません。絶対値式全体が集合になるかどうか不安に思う方もいるでしょうが、これは(選択公理とは独立に)ZFの公理をみたす「もの」なので、集合とよぶことができます。
勿論色々な解釈がありますが、 Periodさんの記事 にも書いてあるようにZermero--Frankelの集合系は集合に関する定義を直接行っているわけではなく、対象に対する制約を課しているだけです。仮にZF公理系上で「集合」を定義するなら、全ての対象ということになります。そのため、文脈で対象と判定できるものであるから本稿では「ZFの公理をみたす対象」ではなく「ZFの公理をみたすもの」という(多少曖昧な)表現を使用しました。集合論に関してあまり詳しくないので、より適切な表現が存在するのであれば教えていただけると助かります。
本題
考える対象を明確化して色々なことを演繹していくのも楽しいかもしれませんが、この記事は「絶対値の面白味を知らせたい」というのと、「場合分けが面倒」という固定観念を打ち破るために書いているので、もう少し分かりやすい話題をしていきましょう。というか、まともな絶対値研究者が存在しない中でガチの記事を書いても誰も読まないと思います。(というか、それは論文の仕事だと思います。)
まず、(非常に絶対値界隈では有名な)次のような初見では非自明な等式を見ていきます。
$$ \lvert\lvert x\rvert-1\rvert=\lvert x+1\rvert+\lvert x-1\rvert-\lvert x\rvert-1 $$
これを証明せよ、と言われたらみなさんどうしますか。恐らく多くの人が試みる$x<-1,-1< x<0,0< x<1,x>1$での場合分けは絶対値界隈的には 悪手 です。この方法では$4$つもの方法に分けなければなりません。そこで、次のような方法を考えます。
任意の絶対値式は連続であるから、$x>0,x<0$それぞれに分けて一致することがみれればよい。$x>0$のときは
\begin{aligned}
\mathrm{LHS}&=\lvert x-1\rvert,\\
\mathrm{RHS}&=(x+1)+\lvert x-1\rvert-x-1\\
&=\lvert x-1\rvert
\end{aligned}
より成立する。$x<0$のときも同様に
\begin{aligned}
\mathrm{LHS}&=\lvert x+1\rvert,\\
\mathrm{RHS}&=\lvert x+1\rvert-(x-1)+x-1\\
&=\lvert x+1\rvert
\end{aligned}
となって両辺一致するから、正しい。従って上記公式を得る。
これで労力が半減、というか多分それ以上にしました。どうやって上記公式を見つけたかなどについては、様々な方法がありますが、 このpdf の定理2.15に従う方法などがあります。構成的な証明なので証明方法が分かれば似たような等式は一変数に限ればいくらでも得られます。もちろんもっと効率的な、例えば場合分けに頼らない方法なも幾つか発見されています。基本的な恒等式なので、色々いじって遊びやすいですね。
現在の絶対値研究の目標の一つに、先の例も含めて非常に多くあると考えられる絶対値式同士の等式を非常に多く作ることができる理論を構築する、というものがあります。
さて、場合分け最短化の練習問題を一つつけておきます。どうすれば最も簡単にできるでしょうか。
任意の実数$x,y$に対して次の等式が成立することを示せ。
$$
2\lvert\lvert x+y+\lvert x\rvert\rvert -x\rvert=\lvert x-y+\lvert x+y\rvert\rvert-\lvert x+y+\lvert 3x+y\rvert\rvert+\lvert 3x+y\rvert+\lvert x+y\rvert+2y
$$
出典はあるとすれば彳亍さんの某吹き出しです。閉じと開きが分かりにくいので、確認したければ次のコードを参照してみてください。
2\lvert\lvert x+y+\lvert x\rvert\rvert -x\rvert=\lvert x-y+\lvert x+y\rvert\rvert-\lvert x+y+\lvert 3x+y\rvert\rvert+\lvert 3x+y\rvert+\lvert x+y\rvert+2y
よく高等学校の定期試験に出題されるような、方程式を解く際も公式を天下りして解く方が簡単です。(慣れてないと厳しいでしょう)この記事が好評だったら今度、既知の絶対値の恒等式(の一部)を纏めた記事を作ろうと思っていますが、使いやすいものだけは先に紹介しておこうと思います。この式を適当に変数変換したりすると楽しいです。
次の公式がなりたつ。
\begin{aligned}
\lvert x\lvert x\rvert-1\lvert&=-x\lvert x\rvert+(x+1)\lvert x-1\rvert+x^2\\
\lvert(x+1)(x-1)\rvert&=-(x-1)\lvert x+1\rvert+(x+1)\lvert x-1\rvert+x^2-1
\end{aligned}
証明は演習問題とします。
さて、質問が来そうなので先に述べておくと、先の練習問題の絶対値式はより一般的な結果を用いることで絶対値の中に絶対値が入っていない形式(少しくだけた表現を用いるとネストされた最小回数が$2$になるということ)に、絶対値式の範囲では変形できないことが分かっています。似たようなものとして次の絶対値式などがあります。
$$ \lvert\lvert x\rvert+\lvert y\rvert -1\rvert $$
興味があればこの事実を証明してみましょう。もし良かったら一緒に絶対値研究しませんか。
おわりに
今回は僕が高校生活で一番時間を費やした研究対象である絶対値について、できるだけ身近に語ってみました。もう少し語りたいので、あと一つだけ。絶対値式全体の集合の全商環(要するに零因子以外で割れるようにしたもの)を$\mathbb{A_R}(\bm X)$で表し、その元を有理絶対値式といいます。この世界では必ずネストされた回数を$1$まで下げることができます。大まかに理由をいうと、定義関数に殆ど至るところ等しい連続関数
$$ f(x)=\frac12\left(\frac{\lvert x\rvert}x+1\right) $$
のようなものが作れてしまうので、適当に場合分けしてあげればネストされた回数を$1$まで下げることができるからですね。僕の絶対値研究のうち、一変数の場合の一般論を一番詳しく語ったのが このpdf で、整域でないにも関わらず除法の原理の類似が構成できた、というあまり見たことがない結果を導き出すことができたりします(これも今度記事に書きたいと思っています)。このように絶対値一つを取ってもかなり面白い対象であるにも関わらず、いつも解析でも代数でも土方役をさせられていて、そのせいか研究例が非常に少ないんですよね。本当に共同研究者を欲しているので、興味があれば声をかけて欲しいです。
最後まで読んでいただきありがとうございました。