1
未解決問題解説
文献あり

【改訂版】「くどー問題」の解決に向けて 第1部:J-λ 理論

36
0
$$\newcommand{Hom}[0]{\mathrm{Hom}} \newcommand{id}[0]{\mathrm{id}} \newcommand{ilim}[1]{\displaystyle \lim_{\stackrel{\longrightarrow}{#1}}} \newcommand{qinteg}[0]{\displaystyle \:\cancel{^{}}\!\!\!\:\:\:\llap{\int}} \newcommand{spec}[0]{\mathrm{spec}} $$

初めに

有限集合$B\subset\mathbb Z_{>0}$で$S=\sum b$が$C=\sum b^3$を割るものを状態と呼ぶ.
「くどー問題」とは ku_do_ 氏が提唱し, bisaitama 氏によって名付けられた問であり,状態$N_n=\{1,2,\dots,n\}$から状態だけを通って1つずつ数を除去し,$\{1,n\}$に至れるかを問う問題である.J-λ 理論は,この「1手」と「連続する2手」を,1つの状態に対する2つの量$S$と$k=C/S$だけで記述する理論であり,bisaitama 氏の「定理1」( 理論的にわかること ),Y.K. 氏の「$\Delta$連鎖定理」( くどー問題の定理たち ),ku_do_ 氏の「正準削除」( そろそろ誰かに解いてほしい自作問題【続】(未解決)(5年振り) )の一般化にあたる.
なお,本記事の作成の過程で,証明方針の探索および途中段階の議論の補助としてClaude Opus 5.5(Anthropic)を利用した.また,本記事に記載したすべての証明と計算は著者自身が独立に検証した.

前回の記事は混み合っていたため,書き直したものとなっています.

くどー問題

くどー問題を形式化しますが,記号の定義はまた載せますので, ku_do_ 氏の記事「 そろそろ誰かに解いてほしい自作問題(未解決) 」「 そろそろ誰かに解いてほしい自作問題【続】(未解決)(5年振り) 」を見てもらえれば,この節は飛ばしても良いです.

くどー問題

$n$を$3$以上の整数とし,$N_n=\{1,2,\dots,n\}$とする.空でない有限な整数集合$X$に対して $$S(X)=\sum_{x\in X}x,\qquad C(X)=\sum_{x\in X}x^3$$と定義する.$N_n$の部分集合の列$B_0,B_1,\dots,B_{n-2}$であって,次の2条件 (i), (ii) を満たすものを除去列と呼ぶ.

  1. $B_0=N_n$,$B_{n-2}=\{1,n\}$であり,各$j\in\{0,1,\dots,n-3\}$について,ある$y_j\in B_j$により$B_{j+1}=B_j\setminus\{y_j\}$と書ける.
  2. 任意の$j\in\{0,1,\dots,n-2\}$に対して,$S(B_j)\mid C(B_j)$である.

このとき,除去列が存在するような整数$n\geq3$は$n=3,6$のみである.

(i) より$\{1,n\}=B_{n-2}\subset B_j$がすべての$j$で成り立つので,$1$と$n$は除去されない.したがって除去列は,$\{2,\dots,n-1\}$の並べ替え$(y_0,\dots,y_{n-3})$と1対1に対応する.また,$j=0$と$j=n-2$では (ii) が常に成り立つ($C(N_n)=S(N_n)^2$,$C(\{1,n\})=(n+1)(n^2-n+1)$).よって (ii) で実際に条件となるのは$1\le j\le n-3$の場合だけである.

$n=6$では,$3,4,5,2$の順に除去する列$$\{1,\dots,6\}\supset\{1,2,4,5,6\}\supset\{1,2,5,6\}\supset\{1,2,6\}\supset\{1,6\}$$が除去列であり,$C/S$の値は順に$21,23,25,25,31$となる.

J-λ 理論

導入

状態

空でない有限集合$B\subset\mathbb Z_{>0}$に対して
$$S=S(B):=\sum_{v\in B}v,\qquad C=C(B):=\sum_{v\in B}v^3,\qquad k=k(B):=\frac CS\in\mathbb Q$$
とおく.$S\mid C$,すなわち$k\in\mathbb Z$のとき$B$を状態と呼ぶ.
状態$B$と$y\in B$($\lvert B\rvert\ge2$)について,$B\setminus\{y\}$が状態であるとき,$y$を$B$から除去できるという.

$\lvert B\rvert\ge2$なら$S^3>C$であることに注意する.

標準的な削除

整数$\rho,x$と$x\in B$($\lvert B\rvert\ge2$)について$k(B)=\rho S(B)+x(x-\rho)$が成り立つとき,$B$は$x$で公差$\rho$の標準形であるという.
このとき$B'=B\setminus\{x\}$は$x'=x+\rho$で公差$\rho$の標準形であり,特に$B$と$B'$はともに状態である.

$C=Sk=\rho S^2+Sx^2-\rho Sx$なので
$$C-x^3=(S-x)(\rho S+x^2)=(S-x)\bigl(\rho(S-x)+x(x+\rho)\bigr).$$
よって両辺を$S(B')=S-x$で割ればよい.

$N_{26}$から$13$を除去すると$S=338$,$k=358=S+5\cdot(5-1)$となる.すなわち,$\rho=1,\ x=5$の形なので,
$$N_{26}\setminus\{13\},N_{26}\setminus\{5,13\},N_{26}\setminus\{5,6,13\},\dots,N_{26}\setminus\{5,6,\dots,12,13\}$$
は全て状態になる.

$k$がこの形からどれだけずれているかを測る量として次を導入する.

空でない有限集合$B\subset\mathbb Z_{>0}$と整数$\rho,x$に対して
$$J_{\rho,x}(B):=C-\rho S^2-x(x-\rho)S=C-S\bigl(\rho S+x(x-\rho)\bigr)\in\mathbb Z$$
と定める.$\rho$を公差と呼ぶ.

$J$と状態

空でない有限集合$B\subset\mathbb Z_{>0}$と整数$\rho,x$に対して
$$S(B)\mid C(B)\iff S(B)\mid J_{\rho,x}(B)$$

$J$の基本恒等式

$B\subset\mathbb Z_{>0}$を空でない有限集合とし,$\rho,\rho',x,x'$を整数とする.

  1. $J_{\rho,x'}(B)-J_{\rho,x}(B)=-S\,(x'-x)(x'+x-\rho)$.
  2. $J_{\rho,\rho-x}(B)=J_{\rho,x}(B)$.
  3. $J_{\rho',x}(B)-J_{\rho,x}(B)=-(\rho'-\rho)\,S\,(S-x)$.
  4. $y\in B$,$\lvert B\rvert\ge2$に対して$B'=B\setminus\{y\}$と置くとき$$J_{\rho,x}(B')=J_{\rho,x}(B)+y\,(x-y)(x+y-\rho)+2\rho\,y\,(S-y).$$
  5. $J_{S,0}(B)=C-S^3$

(1)(2) $x'(x'-\rho)-x(x-\rho)=(x'-x)(x'+x-\rho)$より.
(3) $\bigl(\rho'S+x(x-\rho')\bigr)-\bigl(\rho S+x(x-\rho)\bigr)=(\rho'-\rho)(S-x)$より.
(4) $S(B')=S-y$,$C(B')=C-y^3$を代入すると$$J_{\rho,x}(B')-J_{\rho,x}(B)=y\bigl(x(x-\rho)-y^2-\rho y+2\rho S\bigr)$$となることから従う.
(5) 定義から明らか.

補題3

$x\neq S$を満たす整数$x$に対し,$J_{\rho,x}(B)=0$となる整数$\rho$は高々1つである.

補題($J$の基本恒等式)(3) より,$\rho\neq\rho'$なら$J_{\rho',x}(B)-J_{\rho,x}(B)\neq0$であることから従う.

1手の判定と整数公差の連鎖

除去判定

$y\in B$,$\lvert B\rvert\ge2$とする.次は同値である.

  1. $y$は$B$から除去できる.すなわち,$B'=B\setminus\{y\}$は状態である.
  2. 任意の整数$\rho,x$に対して$$(S-y)\ \Big|\ J_{\rho,x}(B)+y\,(x-y)(x+y-\rho).$$
  3. $(S-y)\mid S^3-C$.

特に,整数$\rho,x$について$J_{\rho,x}(B)=0$ならば,(1) は次と同値である.
$$(S-y)\ \Big|\ y\,(y-x)(y+x-\rho).$$

命題($J$と状態)を$B'$($S(B')=S-y$)に用いると,(1)は$(S-y)\mid J_{\rho,x}(B')$と同値である.補題($J$の基本恒等式)(4) より
$$J_{\rho,x}(B')\equiv J_{\rho,x}(B)+y\,(x-y)(x+y-\rho)\pmod{S-y}$$
なので,各整数$\rho,x$について (1) と (2) の条件は同値である.
$(\rho,x)=(S,0)$ととると,補題($J$の基本恒等式)(5) より$J_{S,0}(B)+y(-y)(y-S)\equiv C-S^3\pmod{S-y}$なので,(3) を得る.最後の主張は$(x-y)(x+y-\rho)=-(y-x)(y+x-\rho)$より従う.

整数公差の連鎖

整数$\rho,x$について$J_{\rho,x}(B)=0$とする.$x_j=x+j\rho$とおき,$x_0,\dots,x_{r-1}$は$B$の相異なる元で,$B\neq\{x_0,\dots,x_{r-1}\}$とする.$B_0=B$,$B_{j+1}=B_j\setminus\{x_j\}$とおくと,$0\le j\le r$のすべてについて
$$J_{\rho,x_j}(B_j)=0$$
であり,特に$B_j$は状態である.さらに$k(B_j)+\rho\,S(B_j)$は$j$によらず一定.この除去の列を,公差$\rho$の連鎖と呼ぶ.
$x_r\notin B_r$のとき連鎖は$B_r$で止まり,$x_r$を$B_r$の穴と呼ぶ.このとき$B_r$から$y$を除去できることは,$(S(B_r)-y)\mid y\,(y-x_r)(y+x_r-\rho)$と同値である.

$j\le r-1$では$B_j$は$x_j$と$B\setminus\{x_0,\dots,x_{r-1}\}$の元を含むので,$\lvert B_j\rvert\ge2$である.よって命題(標準的な削除)を$j$について帰納的に用いればよい.$k_j=k(B_j)$,$S_j=S(B_j)$とおくと$k_j=\rho S_j+x_j(x_j-\rho)$なので
$$k_{j+1}+\rho S_{j+1}=2\rho(S_j-x_j)+(x_j+\rho)x_j=2\rho S_j+x_j(x_j-\rho)=k_j+\rho S_j.$$
最後の主張は定理(除去判定)による.

連続する2手

連続する2手

$B$を$\lvert B\rvert\ge2$を満たす有限集合,$a\ge1$を$a\notin B$を満たす整数,$b\in B$とし,
$$\rho=b-a,\qquad J=J_{\rho,b}(B),\qquad M=\mathrm{lcm}(S-b,\,S,\,S+a),\qquad G=\frac{(S-b)\,S\,(S+a)}{M}$$
とおく.

  1. $J=(S-b)\,S\,(S+a)-(S^3-C)=J_{\rho,a}(B\cup\{a\})$.
  2. $B\setminus\{b\}$,$B$,$B\cup\{a\}$がすべて状態であることは,$M\mid J$と同値である.
  3. (2)の条件のもとで$J=mM$($m\in\mathbb Z$)と書くと$m< G$であり,次のどちらか一方だけが成り立つ.
  • (I) $m=0$.このとき$B\cup\{a\}$は$a$で,$B$は$b$で,ともに公差$\rho$の標準形である.
  • (II) $m\neq0$.このとき$\lvert J\rvert\ge M$.
  1. $(S-b)S(S+a)=S^3-\rho S^2-abS$であり,$b(b-\rho)=ab$より$J=C-\rho S^2-abS$なので,第1の等号を得る.第2の等号は補題($J$の基本恒等式)(4) を$B\cup\{a\}$から$a$を除去する場合に基準$(\rho,a)$で用いると$J_{\rho,a}(B)=J_{\rho,a}(B\cup\{a\})+2\rho aS$.同じ補題の (1) と$b+a-\rho=2a$より$J_{\rho,b}(B)=J_{\rho,a}(B)-2\rho aS$.
  2. (1)より,$S-b$と$S+a$を法として$J\equiv C-S^3$である.よって
    $$J\equiv C\pmod S,\qquad J\equiv C-b^3\pmod{S-b},\qquad J\equiv C+a^3\pmod{S+a}.$$
    $S(B\setminus\{b\})=S-b$,$C(B\setminus\{b\})=C-b^3$,$S(B\cup\{a\})=S+a$,$C(B\cup\{a\})=C+a^3$なので,3つの集合が状態であることは,それぞれ$S$,$S-b$,$S+a$が$J$を割ることと同値である.
  3. $(S-b)S(S+a)=GM$と$S^3-C>0$より$J< GM$,すなわち$m< G$.(I) は (1) の$J_{\rho,b}(B)=J_{\rho,a}(B\cup\{a\})=0$による.(II) は$\lvert m\rvert\ge1$による.

状態の列$B_0\supset B_1\supset\cdots$で$B_{j+1}=B_j\setminus\{y_j\}$とする.$j\ge1$について,$(B,a,b)=(B_j,y_{j-1},y_j)$に定理(連続する2手)を用いたとき (I) が成り立つことを,「$j$で (I)」と呼ぶ.

  1. $j$と$j+1$でともに (I) ならば,$y_{j+1}-y_j=y_j-y_{j-1}$である.
  2. $j_0< j\le j_1$のすべてで (I) ならば,$\rho=y_{j_0+1}-y_{j_0}$について$y_{j_0},y_{j_0+1},\dots,y_{j_1}$は公差$\rho$の等差数列であり,これは$B_{j_0}$から$x=y_{j_0}$で始まる公差$\rho$の連鎖である.

特に,除去列の$1\le j\le n-3$ではこの定理が適用でき,除去列は (II) の起こる$j$で区切られた整数公差の連鎖の列に分かれる.

  1. $j$で (I) なので,$\rho_j=y_j-y_{j-1}$について$J_{\rho_j,y_j}(B_j)=0$.$j+1$で (I) なので,$\rho_{j+1}=y_{j+1}-y_j$について定理(連続する2手)(1)より$J_{\rho_{j+1},y_j}(B_j)=0$.$y_j\in B_j$,$\lvert B_j\rvert\ge2$より$y_j\neq S(B_j)$なので,補題3の系より$\rho_j=\rho_{j+1}$.
  2. (1)を繰り返すと等差数列であることがわかる.$j_0+1$で (I) なので$J_{\rho,y_{j_0}}(B_{j_0})=0$であり,定理(整数公差の連鎖)の状況になる.

定理(連続する2手)(2) の条件のもとで,$G=1$かつ$S>2b$ならば (I) が成り立つ.

$m< G=1$より$m\le0$.$m\le-1$とすると,$G=1$より$M=(S-b)S(S+a)$なので$S^3-C=(S-b)S(S+a)-mM\ge2(S-b)S(S+a)$.$S>2b$より$2(S-b)(S+a)\ge2S(S-b)>S^2$なので$S^3-C>S^3$となるが,これは矛盾.

定理(連続する2手)(2) の条件のもとで,$L=M/S$,$R=G-m$とおく.

  1. $R$は正の整数で,$S^2-k=RL$,かつ$$R< G\cdot\frac{S^2}{(S+a)(S-b)}.$$
  2. $G=\gcd(S,b)\cdot\gcd\bigl(\mathrm{lcm}(S-b,S),\,S+a\bigr)\le ab(a+b)$.
  3. $S^2-k$の素因数$p$で$p>S+a$を満たすものは$R$を割る.特に$p\le R$である.
  4. 除去列の途中の状態$B_j$($1\le j\le n-3$)について$S=S(B_j)$とする.$S(B_j)^2-k(B_j)$は
    $$p>S+n-1\qquad\text{かつ}\qquad p\ge\frac{2n^3\,S}{S-n+1}$$
    を満たす素因数$p$をもたない.
  1. $S^3-C=GM-mM=RM$より$S^2-k=RL$.$S^2-k>0$より$R\ge1$.$k>0$であることに注意すると,$L=\frac{(S-b)(S+a)}G$から不等式を得る.
  2. $u=S-b$,$v=S$,$w=S+a$とおくと,$\mathrm{lcm}(u,v,w)=\frac{\mathrm{lcm}(u,v)\,w}{\gcd(\mathrm{lcm}(u,v),w)}$,$\mathrm{lcm}(u,v)=\frac{uv}{\gcd(u,v)}$なので等式を得る.$\gcd(S-b,S)=\gcd(b,S)\le b$.また$\gcd(\mathrm{lcm}(u,v),w)$は$\gcd(uv,w)$を割り,$\gcd(uv,w)$は$\gcd(u,w)\gcd(v,w)=\gcd(S-b,a+b)\gcd(S,a)$を割るので,$(a+b)a$以下である.
  3. $L$の素因数は$S-b$,$S$,$S+a$のどれかを割るので$S+a$以下である.よって$p\nmid L$であり,$p\mid S^2-k=RL$より$p\mid R$.
  4. $a,b\le n-1$は相異なるので,(2) より$G\le ab(a+b)<2n^3$.また$\frac{S^2}{(S+a)(S-b)}<\frac S{S-b}\le\frac S{S-n+1}$.よって (1) より$R<\frac{2n^3S}{S-n+1}$.$p>S+n-1\ge S+a$を満たす素因数があれば (3) より$p\le R$なので,$p\ge\frac{2n^3S}{S-n+1}$はありえない.

$n=6$の除去列($3,4,5,2$の順)では,次のようになる.

$B_j$$a$$b$$S$$J$$M$$m$$G$
$\{1,2,4,5,6\}$$3$$4$$18$$-126$$126$$-1$$42$
$\{1,2,5,6\}$$4$$5$$14$$-126$$126$$-1$$18$
$\{1,2,6\}$$5$$2$$9$$378$$126$$3$$7$

3つとも (II) である.
一方,$N_{26}\setminus\{13\}$の$5,6,\dots,12$を除去する列(命題(標準的な削除)の例)では,すべて (I) である.

公差関数

$n=6$の除去列の初手$y=3$について,補題($J$の基本恒等式)(3) より$J_{\rho,3}(N_6)=252-378\rho$である.これは整数$\rho$では$0$にならず,$\rho=\frac23$で$0$になる.すなわち$N_6$は$3$で公差$\frac23$の標準形であるといえる.そこで,有理数に拡張した形を考える.

2次式 $Q_B$,候補点,基点

空でない有限集合$B\subset\mathbb Z_{>0}$と$\rho,x\in\mathbb Q$に対して
$$Q_B(\rho,x):=x^2-\rho x+\rho S-k=(x^2-k)+\rho\,(S-x)$$
と定め,$\rho$を同様に公差と呼ぶ.整数$\rho,x$では$J_{\rho,x}(B)=-S\,Q_B(\rho,x)$である.
$Q_B(\rho,x)=0$,すなわち$k=\rho S+x(x-\rho)$となる$x\in\mathbb Q$を,$B$の公差$\rho$の候補点と呼び,組$(\rho,x)$を$B$の基点と呼ぶ.
有理数$\rho$についても,$k=\rho S+x(x-\rho)$のとき$B$は$x$で公差$\rho$の標準形であるという.

公差関数

$x\in\mathbb Q$,$x\neq S$に対して
$$c_B(x):=\frac{k-x^2}{S-x},\qquad \mu_B(x):=x\,c_B(x)$$
と定める.$c_B$を公差関数と呼ぶ.

$Q_B$の基本恒等式

$\rho,\rho',x,x'\in\mathbb Q$とする.

  1. $Q_B(\rho,x')-Q_B(\rho,x)=(x'-x)(x'+x-\rho)$.
  2. $Q_B(\rho',x)-Q_B(\rho,x)=(\rho'-\rho)(S-x)$.
  3. $x\neq S$ならば$Q_B(\rho,x)=(S-x)\bigl(\rho-c_B(x)\bigr)$.
  4. $Q_B(\rho,S)=S^2-k$.

(1)(2)(4) は定義から直ちに従う.(3) は$Q_B(c_B(x),x)=(x^2-k)+(k-x^2)=0$と (2) による.

候補点の構造
  1. $x\neq S$が公差$\rho$の候補点であることは,$\rho=c_B(x)$と同値である.すなわち,$x\neq S$はちょうど1つの公差$c_B(x)\in\mathbb Q$の候補点である.
  2. 公差$\rho$を固定すると,候補点は2次方程式$x^2-\rho x+(\rho S-k)=0$の根であり,高々2個である.2根の和は$\rho$,積は$\rho S-k$である.特に,$x$が候補点なら$\rho-x$も候補点である(共役).
  3. 整数の組$(\rho,x)$が基点であることは,$J_{\rho,x}(B)=0$と同値である.
  1. は補題($Q_B$の基本恒等式)(3) から,(2) は定義から,(3) は$J_{\rho,x}(B)=-S\,Q_B(\rho,x)$と$S>0$から従う.

1手の公式と判定(公差版)

除去の公式
  1. $y\in B$,$\lvert B\rvert\ge2$について$B'=B\setminus\{y\}$と置くとき, $$k(B')=k+\mu_B(y),\qquad c_B(y)=\frac{k(B')-y^2}{S}.$$
  2. $a\ge1$,$a\notin B$について $$k(B\cup\{a\})=k-a\,c_B(-a),\qquad c_B(-a)=\frac{k-a^2}{S+a}.$$
  3. $y\in B$,$\lvert B\rvert\ge2$と$\rho,x\in\mathbb Q$について$B'=B\setminus\{y\}$と置くとき, $$Q_{B'}(\rho,x)=Q_B(\rho,x)-y\,\bigl(\rho+c_B(y)\bigr).$$
  1. $C-y^3=k(S-y)+y(k-y^2)$を$S-y$で割ると前半を得る.これより $$k(B')-y^2=(k-y^2)\Bigl(1+\frac y{S-y}\Bigr)=\frac{S(k-y^2)}{S-y}.$$
  2. $C+a^3=k(S+a)-a(k-a^2)$を$S+a$で割る.
  3. $Q_{B'}(\rho,x)=x^2-\rho x+\rho(S-y)-\bigl(k+\mu_B(y)\bigr)$.
基点の公式
  1. $(\rho_0,x_0)$を$B$の基点とする.$z\neq S$に対して $$c_B(z)=\rho_0-\frac{(z-x_0)(z+x_0-\rho_0)}{S-z}.$$
  2. $z\neq S$に対して $$c_B(z)=z+S-\frac {S^2-k}{S-z}.$$
  1. 補題($Q_B$の基本恒等式)(1)(3) より$(S-z)\bigl(\rho_0-c_B(z)\bigr)=Q_B(\rho_0,z)=Q_B(\rho_0,x_0)+(z-x_0)(z+x_0-\rho_0)$.
  2. $k-z^2=(S^2-z^2)-(S^2-k)$を$S-z$で割る.
除去判定(公差版)

状態$B$と$y\in B$($\lvert B\rvert\ge2$)について,次は同値である.

(a) $B'=B\setminus\{y\}$は状態である.
(b) $\mu_B(y)\in\mathbb Z$.
(c) $S\,c_B(y)\in\mathbb Z$.
(d) $c_B(y)=r/s$(既約分数,$s\ge1$)とすると,$s\mid y$.

(a)⇔(b):定理(除去の公式)(1) と$k\in\mathbb Z$による.
(b)⇔(c):$(S-y)\,c_B(y)=k-y^2\in\mathbb Z$であり,$S\,c_B(y)=(S-y)\,c_B(y)+\mu_B(y)$.
(b)⇔(d):$\mu_B(y)=yr/s$で$\gcd(r,s)=1$.

$n=6$の除去列($3,4,5,2$の順)では次のようになる.

除去する数 $y$$3$$4$$5$$2$
$(S,k)$(除去前)$(21,21)$$(18,23)$$(14,25)$$(9,25)$
$c_B(y)$$\frac23$$\frac12$$0$$3$
$\mu_B(y)$$2$$2$$0$$6$

最後の状態は$(S,k)=(7,31)$である.

輸送と前進

$x$を$B$の公差$\rho\in\mathbb Q$の候補点とし,$y\in B$($\lvert B\rvert\ge2$)を除去する.このとき
$$Q_{B'}(\rho,\,x+\rho)=\frac{(x-y)\bigl(2\rho S-y\,(x+y+\rho)\bigr)}{S-y}.$$
特に,$x+\rho$が$B'=B\setminus\{y\}$の公差$\rho$の候補点となるのは,次のどちらかの場合に限る.

  • $y=x$(輸送)
  • $2\rho S=y\,(x+y+\rho)$(前進)

補題($Q_B$の基本恒等式)(1) より$Q_B(\rho,x+\rho)=Q_B(\rho,x)+2\rho x=2\rho x$.定理(基点の公式)(1) を基点$(\rho,x)$に用いると$c_B(y)=\rho-\frac{(y-x)(y+x-\rho)}{S-y}$.これと定理(除去の公式)(3) より
$$Q_{B'}(\rho,x+\rho)=2\rho x-y\rho-y\,c_B(y)=(x-y)\Bigl(2\rho-\frac{y\,(x+y-\rho)}{S-y}\Bigr)$$
であり,$2\rho(S-y)-y(x+y-\rho)=2\rho S-y(x+y+\rho)$である.

状態$B$から$y\in B$を除去できるとする.

  1. $(c_B(y),y)$は$B$の基点であり,$y+c_B(y)$は$B'=B\setminus\{y\}$の公差$c_B(y)$の候補点である.
  2. $y+c_B(y)$が整数であることは,$c_B(y)\in\mathbb Z$と同値である.$c_B(y)\in\mathbb Z$なら,定理(整数公差の連鎖)が$\rho=c_B(y)$,$x=y$で適用できる.$c_B(y)\notin\mathbb Z$なら,公差$c_B(y)$の連鎖は$y$の1手で終わる.
  1. 命題(候補点の構造)(1) と定理(輸送と前進)($y=x$の場合)による.(2)$y\in\mathbb Z$による.$c_B(y)\in\mathbb Z$のとき,命題(候補点の構造)(3) より$J_{c_B(y),y}(B)=0$である.
共役と逆の手

$x$を状態$B$の公差$\rho$の候補点とし,$a=x-\rho$が$a\ge1$,$a\notin B$を満たすとする.

  1. $-a=\rho-x$も公差$\rho$の候補点であり,$c_B(-a)=\rho$である.
  2. $B''=B\cup\{a\}$では,$a$が公差$\rho$の候補点である.$B''$から$a$を除去すると$B$に戻り,候補点は$x=a+\rho$に輸送される.
  3. $B''$が状態であることは,$a\rho\in\mathbb Z$と同値である.
  1. 命題(候補点の構造)(2) と (1) による.$a\ge1$より$-a\neq S$.
  2. 定理(除去の公式)(2) と (1) より$k(B'')=k-a\rho$なので,$Q_{B''}(\rho,a)=Q_B(\rho,a)+a\rho+a\rho=Q_B(\rho,a)+2\rho a$.補題($Q_B$の基本恒等式)(1) より$Q_B(\rho,a)=Q_B(\rho,x)+(a-x)(a+x-\rho)=-\rho\cdot2a$なので,$Q_{B''}(\rho,a)=0$.後半は定理(輸送と前進)による.
  3. $k(B'')=k-a\rho$による.
連続する2手の公差による表示

定理(連続する2手)の記号で,(2) の条件が成り立つとする.

  1. $J=S\,(S-b)\bigl(c_B(b)-(b-a)\bigr)$であり, $$G\bigl(c_B(b)-(b-a)\bigr)=m\,(S+a),\qquad \frac {S^2-k}{(S+a)(S-b)}=1-\frac{c_B(b)-(b-a)}{S+a}.$$
  2. (I) が成り立つことは,$c_B(b)=b-a$とも,$c_{B\cup\{a\}}(a)=b-a$とも同値である.
  3. (II) が成り立つならば,$G\,\bigl\lvert c_B(b)-(b-a)\bigr\rvert\ge S+a$である.
  1. 補題($Q_B$の基本恒等式)(3) より$J=-S\,Q_B(b-a,b)=S(S-b)\bigl(c_B(b)-(b-a)\bigr)$.$J=mM$,$M=\frac{(S-b)S(S+a)}G$を代入すると第1式を得る.第2式は$S^2-k=(S-b)(S+a)-\frac JS$を$(S+a)(S-b)$で割ればよい.
  2. 第1の同値は (1) による.また定理(連続する2手)(1) と補題($Q_B$の基本恒等式)(3) を$B\cup\{a\}$($S(B\cup\{a\})-a=S$)に用いると$J=J_{b-a,a}(B\cup\{a\})=S(S+a)\bigl(c_{B\cup\{a\}}(a)-(b-a)\bigr)$.
  3. (1)の第1式で$\lvert m\rvert\ge1$.

ファイバー

ここまでで,各手$y$にはその公差$c_B(y)$が対応し,手が合法かどうかは$c_B(y)$の分母で(定理11),公差$c_B(y)$の連鎖が続くかどうかは$c_B(y)$が整数かどうかで決まる(定理12 系5)ことを見た.この節では,同じ公差をもつ点をまとめて扱う.

ファイバー

$x\in\mathbb Q$,$x\neq S$に対して
$$\lambda_B(x):=1-c_B(x)=\frac{Q_B(1,x)}{S-x},\qquad \kappa_B(x):=x\,\lambda_B(x)=x-\mu_B(x)$$
と定める.$x$が整数なら$\lambda_B(x)=-\dfrac{J_{1,x}(B)}{S\,(S-x)}$である.
$\lambda_0\in\mathbb Q$に対して
$$\mathfrak F_{\lambda_0}(B):=\{x\in\mathbb Q:\ x\neq S,\ \lambda_B(x)=\lambda_0\}$$
を$B$の$\lambda_0$のファイバーと呼ぶ.これは,$S$以外の公差$1-\lambda_0$の候補点の集合である.

$$P=P(B):=k-S=-Q_B(1,0)=\frac{J_{1,0}(B)}S,\qquad \Phi=\Phi(B):=2k-S=-2\,Q_B\bigl(\tfrac12,0\bigr)$$
とおく.また三角数を$T_m=\frac{m(m+1)}2$と書く.

ファイバーの構造
  1. $x\in\mathfrak F_{\lambda_0}(B)$であることは,$x\neq S$かつ $$x(x-1)-P=\lambda_0\,(S-x)$$と同値である.$\mathfrak F_{\lambda_0}(B)$は高々2個の元からなり,2個あればその和は$1-\lambda_0$である.
  2. $\mathfrak F_{\lambda_0}(B)\cap B$は高々2個の元からなる.$\lambda_0\notin\mathbb Z$なら高々1個である.相異なる$z_1,z_2\ge2$を含むなら$\lambda_0=1-z_1-z_2\le-4$である.
  1. $\lambda_B(x)=\frac{x(x-1)-P}{S-x}$による.後半は命題(候補点の構造)(2) を$\rho=1-\lambda_0$に用いる.
  2. (1)による.2個の整数の和$1-\lambda_0$は整数である.
ファイバーの方程式

$\lambda_0=r/s$(既約分数,$s\ge1$)とする.状態$B$と$y\in B$($\lvert B\rvert\ge2$)について,「$y\in\mathfrak F_{\lambda_0}(B)$かつ$B'=B\setminus\{y\}$は状態である」ことは,次と同値である.
$$s\,y(y-1)+r\,y=s\,k-(s-r)\,S\qquad\text{かつ}\qquad s\mid y.$$

前半の式は,命題(ファイバーの構造)(1) の式に$s$を掛けたものである.$c_B(y)=1-\frac rs=\frac{s-r}s$も既約分数なので,後半は定理(除去判定(公差版))(d) による.

特別なファイバー

状態$B$と$y\in B$($\lvert B\rvert\ge2$)について,次が成り立つ.

$\lambda_0$公差 $1-\lambda_0$$y\in\mathfrak F_{\lambda_0}(B)$の条件除去できる条件除去の後
$0$$1$$y(y-1)=P$常に公差 $1$の連鎖 $y,y+1,\dots$
$\frac12$$\frac12$$y(2y-1)=\Phi$$y$が偶数次の候補点 $y+\frac12$は整数でない
$1$$0$$y^2=k$常に$k$は変わらない
$2$$-1$$y(y+1)=S+k$常に公差 $-1$の連鎖 $y,y-1,\dots$
$\Phi$と公差$\frac12$
  1. $Q_B\bigl(\frac12,x\bigr)=\frac12\bigl(x(2x-1)-\Phi\bigr)$.したがって,$\Phi=T_m$であることと,$\frac{m+1}2$が公差$\frac12$の候補点であることは同値である.
  2. $y\in B$を除去するとし,$B'=B\setminus\{y\}$と置く.この時,$$\Phi(B')=\Phi(B)+y\bigl(1+2c_B(y)\bigr)=\Phi(B)+y\bigl(3-2\lambda_B(y)\bigr).$$
  3. $\Phi(B)=T_m$とする.$y\in B$について$B'=B\setminus\{y\}$と置くとき,$\Phi(B')=T_{m+1}$となるのは,$y=\frac{m+1}2$のとき,または$2S=y\,(2y+m+2)$のときに限る.
  1. $x=\frac{m+1}2$のとき$x(2x-1)=T_m$より従う.
  2. 定理(除去の公式)(1) より$\Phi(B')=2\bigl(k+y\,c_B(y)\bigr)-(S-y)$.
  3. (1)より$\Phi(B')=T_{m+1}$は$\frac{m+2}2=\frac{m+1}2+\frac12$が$B'$の公差$\frac12$の候補点であることと同値である.$\frac{m+1}2$は$B$の公差$\frac12$の候補点なので,定理(輸送と前進)を$\rho=\frac12$,$x=\frac{m+1}2$に用いる.前進の条件は$S=y\bigl(y+\frac{m+2}2\bigr)$である.
符号の補題

状態$B$から$y\in B$($y\ge2$)を除去できるとする.

  1. $\lambda_B(y)<0$なら$S-y\le y\bigl(P-y(y-1)\bigr)$である.特に$S<(\sqrt P+1)(P-1)$.
  2. $\lambda_B(y)>0$なら$S-y\le y\bigl(y(y-1)-P\bigr)$である.
    したがって$S\ge(\sqrt P+1)(P-1)$ならば,除去できる$y\ge2$はすべて$\lambda_B(y)\ge0$を満たす.

定理(除去判定(公差版))(b) より$\kappa_B(y)=y-\mu_B(y)$は整数であり,$\kappa_B(y)=\frac{y\,(y(y-1)-P)}{S-y}$.$\lambda_B(y)\neq0$ならこれは$0$でないので,絶対値は$1$以上である.これで (1)(2) の前半が従う.(1) では$y(y-1)< P$より$(y-1)^2< P$,すなわち$y<\sqrt P+1$である.また$y\ge2$より$P-y(y-1)\le P-2$.よって
$$S\le y\bigl(P-y(y-1)\bigr)+y\le y\,(P-1)<(\sqrt P+1)(P-1).$$

定理(連続する2手)の記号で,(2) の条件が成り立ち,$b\ge2$,$S\ge(\sqrt{P}+1)(P-1)$($P=P(B)$)とする.このとき$$-\frac{b^2}{S-b}< c_B(b)\le1$$であり,(II) が成り立つならば$$G\Bigl(\lvert b-a\rvert+\max\Bigl\{1,\ \frac{b^2}{S-b}\Bigr\}\Bigr)\ \ge\ S+a.$$
特に除去列の途中では$\lvert b-a\rvert\le n-3$なので,$b^2\le S-b$のとき,(II) は$G\ge\frac{S+a}{n-2}$を要求する.

$B\setminus\{b\}$は状態なので,定理(符号の補題)より$\lambda_B(b)\ge0$,すなわち$c_B(b)\le1$.$k>0$より$c_B(b)=\frac{k-b^2}{S-b}>-\frac{b^2}{S-b}$.よって$\lvert c_B(b)-(b-a)\rvert\le\lvert b-a\rvert+\max\{1,\frac{b^2}{S-b}\}$であり,命題(連続する2手の公差による表示)(3) から主張を得る.

まとめ

第1部では,状態$B$を2つの量$S$,$k$で記述し,除去の「1手」と「連続する2手」を調べた.

整数の基準

状態の条件$S\mid C$は,整数の基準$(\rho,x)$をとると$S\mid J_{\rho,x}(B)$と書け,$J_{\rho,x}(B)=0$は$B$が$x$で公差$\rho$の標準形であることを表す.基準を標準形にとれば,1手の判定は$(S-y)\mid y(y-x)(y+x-\rho)$という小さな整除になり(定理4),公差が整数なら手は自動的に続く(定理5).連続する2手$a,b$については,基準$(b-a,b)$によって3つの状態の条件が1つの整除$M\mid J$にまとまり,$m=0$か$\lvert J\rvert\ge M$のどちらかになる(定理6).この結果,除去列は,(II) の起こる位置で区切られた整数公差の連鎖の列に分かれる(定理6 系2).

有理数の公差

$J$を$-S$で割った$Q_B$は公差$\rho$について1次式なので,各手$y$にただ1つの公差$c_B(y)\in\mathbb Q$が定まる.手が合法かどうかは$c_B(y)$の分母で決まり(定理11),連鎖が続くのは$c_B(y)$が整数のときに限る(定理12 系5).
(II) が起こる位置では,次の手の公差と差$b-a$のずれが$G\,\lvert c_B(b)-(b-a)\rvert\ge S+a$を満たさなければならない(命題14).

ファイバー

手を公差ごとに分類すると,各ファイバーは高々2点で,合法な手はディオファントス方程式で記述される(定理16).さらに$S$が$P$に比べて大きい状態では,継ぎ目は$G\ge\frac{S+a}{n-2}$を要求する(定理18 系6).例えば,3つの連続する和$S-b$,$S$,$S+a$が,$S/n$程度の大きさの公約数の積をもたなければならない.


$n=6$の除去列では,常に(II)が起こり,$G=42,18,7$である(例3).一般の$n$で除去列が存在しないことを示すには,「すべての(II)の起こる位置で,このgcdの条件が満たされ続けることが不可能」と言う必要がある.
第2部では,状態を$n$についての多項式族としてまとめて扱い,$J$,$M$,$G$を多項式とみなすことで,この条件を$\mathbb Q[t]$での整除と次数の条件に書き換える.そこでファイバーは,ある曲面上の曲線として現れる.

参考文献

投稿日:19日前
数学の力で現場を変える アルゴリズムエンジニア募集 - Mathlog served by OptHub

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

「ツクツクボーシ、ツクツクボーシ」 ほら、カエルが鳴いてるよ 春の訪れを感じながら 落ち葉で黄色くなった道を歩いてく

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中