コラッツ予想がとけたらいいな その2
■ このスレッドは過去ログ倉庫に格納されています
自然数xに対してコラッツ展開に似た数列collatz_array(x)を次のようなrubyプログラムで定義する。
def collatz_array(x)
if(x==1)
then
return []
elsif(x%2==0)
return [0]+col(x/2)
else
return [1]+col((x*3+1)/2)
end
end
collaz_array(x)をビット列とみなして2進数の整数に直したものをcollatz_number(x)とする。
collatz_numberはrubyプログラムで次のように定義される。
def collatz_number(x)
res=0;
x.each_with_index{|v,i|res+=v*(2**i)}
return res
end
3の倍数でない、かつx==collatz_number(x)となるような自然数xは存在するか？ ちょっと言ってることがおかしいかもしれない。
ようするにコラッツ展開に対する不動点みたいなものはあるか？という話をしたいのだが 朝の6時にスレチェックかよｗすげえｗ
まあ俺も人のこと言えないけどｗお疲れ様です。 新たな不動点が見つかったら新たなループが見つかるみたいな方向に持っていけたらベストなんだけど。
まあまだぼんやりしたイメージがあるだけです。 うーん、collatz_arrayの停止条件がx==1だとあんまり意味のない議論になってしまうかもしれないorz x==collatz_number(x)をチェックすると
3*2^tは該当するみたい。そりゃそうか。
あと、「先頭nビットが一致する」だと意味ないかな？ >>679
意味ないかどうかはまだわかりませんが、先頭nビットについては>>528のような割とはっきりした規則性があるようなので、
規則性の見えなくなる後ろのほうのビットのふるまいを何とかできないかという思いはあります。 あ、でもnを増やしていったらなんか出てくるんだろうか？ ちなみに勢いで書いちゃったけど仮に不動点が見つかったとして、それをどう生かせばいいかまだ全然見えてませんｗ 不動点というキーワードでコラッツ展開をみたときに、
ちょうど3が不動点になっていたのでこれが1,4,2のループを表しているのでは？
という思い付きというか期待から書き込んでしまいました。 コラッツ展開は01の無限列なので2-進整数に対応させるのはどうだろう
整数は2-進整数に埋め込めるし、コラッツ展開は2-進整数に自然に拡張できる
以下、簡略表記として左を下位、繰り返しを()で括る、とすると
0=(0)…
-1=(1)…
はコラッツ展開が自身と一致する
1=1(0)… のコラッツ展開は (10)…
(10)…は×3で(11)… = -1 なので
(10)…のコラッツ展開は 1(0)… で元に戻る 見捨てられた過疎スレかと思ってたら
意外とそうでもないのか 2進整数とやらを標準ライブラリで持ってるプログラム言語はありますか？ >>686
Mapleにありそうだけど
Mapleってフリーじゃないもんね 無限桁の2進数みたいなものだから、プログラムで扱うのは難しいのでは？
有限桁以降が繰り返しのものに限定すれば扱えるのかな
(10)…と-1/3、(100)…と-1/7、みたいに、
理論上は(分母の素因数に2を含まない)有理数に対応するはず とりあえず、2-進整数の厳密な定義ってどこかにあります？
四則演算とかも含めて。 ハスケルは遅延評価があるんでしたっけ？
ルビーにもあったかな？ >>690
Haskellはデフォルトで遅延評価です。
Rubyも遅延評価がありそうですが、僕は詳しくないです。 2-進整数、使えそうなら使いたいですね
でも2-進整数にしちゃうと不動点のアイディアをどう扱えばいいかわからなくなるかなぁ？ とりあえずwikipediaよりp進数(p-adic number)
https://ja.m.wikipedia.org/wiki/P%E9%80%B2%E6%95%B0
「定義」の最後にあるp進整数環でpが2のものを考えてるんですが、付値やら完備化や、専門的過ぎてたぶんわけわからんと思います
計算だけなら「略式の解説」のこの辺
> 整数側に無限桁加えたもの、例えば …1246328.125 のようなものが p 進数であると解釈できる。
> p 進数の中でも、小数点以下がない …1246328 のようなものは p 進整数と呼ばれるものに対応する。
> p 進数同士の足し算、引き算、掛け算は、p 進表記の有理数における通常のアルゴリズムを自然に無限桁に拡張することで得られ、割り算は掛け算の逆演算として定義される。 まともにやるとクソ難しそうなのでとりあえずコラッツ展開を分数で表現してみた
def collatz_rational(x)
l=x.length
res=0r
x.reverse.each_with_index{|v,i|res+=v*(1/2r)**(i+1)}
res+=((1/2r)**l)*1/3r
return res
end
def collatz_rational_array(x,l)
res=[]
(0...l).each{|i|
if(x>=1/2r)
then
x-=1/2r
res<<1
else
res<<0
end
x*=2r
}
return res.reverse
end
(1..1000).each{|x|
a=collatz_array(x)
l=a.length
r=collatz_rational(a)
b=collatz_rational_array(r,l)
if(a!=b)
then
print "#{x} #{r} #{a} #{b}\n"
end
} でも分数にしたところで不動点のアイディアとどう結び付けていいかわからぬｗ
まあもともと不動点はそれほど目があるアイディアじゃないかもだけど スタートは不動点だったはずだが脱線してしまったなｗ
うーん、どうしよう 不動点ではないですが、
x == collatz_number(collatz_array(y))
y == collatz_number(collatz_array(x))
のように、相互に参照しあっているものを考え中です。
ちゃんとしたものは後日upします。
https://i.imgur.com/7VUP2CA.jpg 2-進整数の計算についての補足
桁が繰り返しである2-進整数に限ると、
繰り返しが1で埋まれば-1であることを利用して
以下のように有理数との対応がわかります
(1)…=-1/(2^1-1)
(10)…=-1/(2^2-1)
(100)…=-1/(2^3-1)
途中から繰り返す場合についても、例えば
1(100)…=1+2(-1/7)=5/7
のようになります
そして、このようなものに限ると有理数としての加減乗除でまったく問題なかったりします
循環小数=有理数、みたいなもんですね 不動点ということは繰り返し処理をかけても変わらないということですが、
コラッツ展開に対してさらにそのコラッツ展開を求めることに何の意味があるのかが不明瞭なのが現状痛いですね。
そこに何らかの意味が見いだせればもう少し面白くなるのですが 特に何か得られた訳ではないですが、upします。
https://github.com/righ1113/CollatzMod/tree/master/190421
気がついた事は、（不動点じゃないですが）
例えばxが17~31の奇数の区間で、コラッツ展開先頭5ビットが1~31の奇数を、
コラッツ3x+1と3x-1で分けあうことです。 >>705
書いてから思ったのですが、
>>528と関連があるのかどうか、というところですかね。 負数の3x+1問題は実質3x-1問題(x→-x)なので
負数側の結果がスライドしてきている、と考えればよいのかなと コラッツ展開が長さnの循環列
⇔xに対し「x→(3x+1)/2」または 「x→x/2」の変換をある順番でn回行ってxに等しくできる
⇔0≦∃k≦n, ∃y∈Z, ((3^k)x+y)/2^n=x.
これは有理数の範囲で一つの解をもつ すいません、不動点はあまり実りがなさそうなので撤退します。申し訳ない。
今1～2^nのコラッツ展開の先頭nビットを並べてコラッツ展開のkビット目にどのようなパターンが表れるかというのを見ようかと思ってます。 むむ、綺麗な周期が表れるかと思ったらそうでもない？ いや、周期になるみたい。
でもパターンは凄い複雑。 p進体Q_pにおいて、分母がpで割り切れない有理数はp進整数環Z_pに含まれることが知られている
(フェルマーの小定理より任意の素数q≠pに対してp^(q-1)≡0(mod q) なので、-1/qのp進展開がq-1桁の循環になる)
コラッツ問題の有理数への拡張は、Z_2への拡張と考えたほうが実は自然なのでは？
というところで2-進整数ネタも一休み
また週末かなー 繰り返したら元に戻るとか、そういうことはない感じですかね
フーリエ変換に対する逆変換みたいなものが見つからないか、というのは今のところ夢想かなあ >520
の補題を自分の中で整理してたらこうなった。
写像f: Z→Zを次で定義する.
x∈Z に対し,
f(x)=x/2 (x∈0+2Z)
f(x)=(3x+1)/2 (x∈1+2Z)
このとき, 0≦n∈Z, x, y∈Z に対して次が成り立つ.
x-y∈(2^n)Z ⇒ 0≦∃m≦n, s.t.
(2^n)(f^n(x)-f^n(y))=(3^m)(x-y).
(超略証)nに関する帰納法.
定義から0と1の場合がOK.
1とkをあわせてk+1の場合が示される. >>714
繰り返したら元に戻るとか、
小さくなる、とかだったら良かったですけどね。 >715 に引き続き, >521 を代数学風に整理.
前述(>715)のf, x∈Z, 0≦i∈Zに対し x_i=f^i(x)+2Z で定まる Z/2Zの列{x_i}(i≧0)を「xのコラッツ展開」と呼ぶことにする.
x,y∈Zとそのコラッツ展開{x_i},{y_i}について次が成り立つ.
x-y∈(2^n)Z⇔x_i=y_i (0≦∀i≦n).
系. コラッツ展開は単射. コラッツ展開はかなりいい線いってるとは思うが、次の一歩が難しい？ 例えばxのコラッツ展開のyビット目がxのサイズの多項式時間で求まれば大きな前進と言える？ ここでいうxのサイズっていうのは自然数xに対してそれを表すのに必要なビット数log(x)のことね >>719
入力サイズに対して、
コラッツ操作で何回2で割るかが分からないので、
難しいと思います。
特殊な場合だと、
2^n±1は、コラッツ展開のnビット目までを
多項式(定数?)時間で求められます。 個人的には
・Z(有理整数環)→(Z/2Z)の列 で単射になる
・>521の性質から、Z_2(2-進整数環)上にwell-definedに拡張できる
(環Zと素イデアル2Zの話が環Z_2と素イデアル2Z_2の話になるだけで、まったく同じロジックが展開できる)
・Z_2上全射(よって全単射)になる
ということでZ_2上で考えたらなんか出てこないかなー、とは。
コラッツ展開がループ
→一次方程式の解
→Q∩Z_2
とか。
なお、p-進整数環については、射影極限を経由するルートの方がわかりやすいかもしれません。 1ビットでも違うとそこから先は別物というか、カオス的な振る舞いをしますね
2で割ることで折りたたまれたフラクタル構造といいますか…… ところで、
>>684から書いている2-進整数とは少し違うものが英語版Wikipediaにあった。
https://en.wikipedia.org/wiki/Collatz_conjecture
の"Iterating with odd denominators or 2-adic integers"
例えば、コラッツ展開(1011001)のループを考える。
このコラッツ展開の長さn=7で、"1"の個数m=4。
"1"のビット位置k_0,...k_(m-1)は、0, 2, 3, 6。
これらを元に、
(3^(m-1)*2^k_0 + ... + 3^0*2^k_(m-1))/(2^n - 3^m)
を計算すると、151/47になる。
この数を分数でコラッツ操作すると、
151/47 → 250/47 → 125/47 → 211/47 → 340/47 → 170/47 → 85/47 → 151/47 → ...
となって、確かにループしている。偶奇のコラッツ展開とも一致している。
(10)からは1が得られるし、(110)からは-5が得られる。
一つのループから一つの有理数が得られるようだ。
これも2-進整数って言うのかなあ。 2-進整数環Z_2においては、2Z_2の元でなければ可逆元となるので、47の逆元が2-進整数として存在します。
151/47と書くより151・47^-1と書く方が実情を正しく表現しているかもしれません。
また、加法・乗法は有理整数環上のものが延長されているので、分母が奇数の有理数についてはそのまま有理数として計算しても問題が発生することはありません。 ありがとうございます。
よく分かってないですが……
精進しますm(_ _)m じゃあxのコラッツ展開のyビット目をもとめるのはNP困難か？
だったらどう？ 分母が47の2-進整数は、
2^23-1 = 8388607 = 47×178481
であることから、
47^-1 が繰り返しが23桁の2-進整数となることがわかります。
具体的には
23桁の (11…1) = -1
であることから、
23桁の (10…0) = -1 × 47^-1 × 178481^-1
両辺に -1, 178481 をかけるという手順で求まります。 NP困難がむりでも素因数分解とかグラフの同型問題とかに帰着出来たら一定の成果と言えると思う。 あれ、逆か？
素因数分解とかグラフの同型問題をコラッツに帰着できるか？
かな 自然数xのコラッツ展開のxビット目、すなわちコラッツ展開の対角線に着目したら何か出てこないだろうか？ 巨大数探索スレでは対角線というのは非常に注目されていて
ゲーデルの不完全性定理とかにもでてくる有用な概念らいしぞ。 例えば自然数xのコラッツ展開のyビット目をcollatz_bit(x,y)と置くとき、
collatz_bit(x,y)をxとyとcollatz_bit(z,z)で表すことが可能であれば、
本質的にコラッツの問題は対角線だけ着目すればいいという結論が出るかもわからない。
そうなったらちょっとすごい。 >>717 の x-y∈(2^n)Z という式をみて、ユークリッドの互除法みたいにどんどん小さくしていけないかなぁとふと思った。 さすがの>>1もここまで荒らされてしまってはギブアップか？ >>737
荒らされてる……?
証明はここにあります。
https://github.com/righ1113/collatzProof_DivSeq
割数列を使っています。
また、定理証明支援系Idrisを使用しています。 覗いてみたらコラッツ展開が注目されてて嬉しい。
コラッツ展開については私も色々考えていますが、>>544で書いた通り 3x+1 に限らず任意の px+q (p,q は奇数) で同様のことができるので、
3x+1 の特殊性をどう出すかが悩みどころ。
>>738
プログラムのことは良くわかりませんが、定理7-2 では 0 の全ての拡張完全割数列が有限項であることを示しているのですか？ >>740
お久しぶりです。
最近プログラムに大きく手を入れたのですが、そこちょっと引っかかっていました。
示せてないです…… 1つ前のバージョンでは、レベルというものを導入していて、
『レベル2の』0の全ての拡張完全割数列が有限項であること
は実際に計算できたので、それを証明としていました。 >>741
やはりそうですか…。
了解です。
ついでに添削
ch01
・コラッツ予想
＞コラッツ操作をおこなう数を 「コラッツ値」 と呼ぶことにする。
既に同じ意味で「初期値」という言葉が使われているので「初期値」で統一してはどうでしょうか。
「コラッツ値」を残すにしても、『初期値のことを「コラッツ値」とも呼ぶ』などと定義した方が意味がはっきりします。
・定義1-1
これも分かりにくいので、
自然数 n を初期値としてコラッツ操作を連続して行ったとき、各操作において 2 で割った回数を並べてできる数列を n の割数列と呼ぶ。
とか。
有限列になる場合、無限列になる場合もここではっきりさせておくべき。
また、「コラッツ列」が未定義なので付け加えるか表現を変えるか。
・定義1-2
＞初期値が3の倍数の…
上で提案した定義に則るなら「初期値が」は不要。
このままにしたければ定義1-1を「初期値が n の割数列」に変更。
・3の倍数だけ調べれば良い
「コラッツ逆操作」が未定義。
ch02
・定義2-1
＞A[6,-4] or B[1,-2]をつける
「つける」では通じないので、
有限または無限数列 [a_1, a_2, a_3, ...] を数列 [6, a_1-4, a_2, a_3, ...] に写す変換を A[6,-4] と書く。
とか。
また、この時点ではまだ完全割数列を完全割数列に写すことが示されていないので、
その旨を削るか、書くとすれば「すぐ後で示すが」などと書き加えた方がいいと思います。
(重要)
・全ての3の倍数の奇数は、完全割数列で表わされる
ある数が完全割数列で表わされる、という文言がそもそもおかしいですが、
なにより 3 の倍数の割数列が完全割数列であるというのは完全割数列の定義そのもので、ここで示されることではありません。。
タイトルを何かしら変えるべきでしょう。ここで示されているのは
「star変換は完全割数列を完全割数列に写す」
「任意の完全割数列は、ある完全割数列にstar変換を施したものとして得られる」
です。 >>743
添削ありがとうございます。
すごく有難いです。 (重要)
ch03
コラッツ値が非負整数にならないものは禁止するのかしないのかはっきりさせて下さい。
禁止するならば、定義3-1は
n≧0 を 3 の倍数とする。整数列 [a_1, a_2, ...] が n の拡張完全割数列であるとは、
ある 3 の倍数 n'≧0 が存在して
・n' の割数列に、0 や負数が現れることも許してstar変換を有限回施すと数列[a_1, a_2, ...] が得られ、かつ
・n' に対応するコラッツ値の変換を施すと n が得られる
を満たすことを言う。
ってところですかね。
(重要)
ch04
「拡張コラッツ予想」とありますが、これは操作を定義しているだけで予想になっていません。
「拡張コラッツ操作」などと呼ぶべきでしょう。また、ここでも「1回の操作」をはっきり定義しておくといいでしょう。
拡張コラッツ予想とは
任意の拡張完全割数列は有限項である。
とかでしょうか。
あとはプログラムが分からないのでパスで >>743
プログラムを変更して、
帰納法のbase caseは、『（拡張でない）完全割数列が有限項』を示せば良いようにしました。
0の完全割数列は[]と定義するので、有限項です。 GitHubのWikiとprogram3は直しかけです。
証明の流れは以下です。
①まず、二つの述語を用意します。
FirstLimited x ： xの完全割数列は有限長である
AllLimited x ： xの完全割数列および拡張完全割数列達は全て有限長である
示したい命題は、x -> FirstLimited x です。 ---(a)
②次に、パースの法則の述語論理版を用意します。
"∀x::nat. ￢(∀z::nat. (P z -> Q z))
-> (∀z::nat. (P z -> Q z) -> (∀n::nat. P n))
-> P x"
これは定理証明支援系Isabelleで自動証明したので間違いないと思います。
③(∀z::nat. (P z -> Q z) -> (∀n::nat. P n))
のP, QにFirstLimited, AllLimitedを代入したものを証明します。
無限降下法はやめて、整礎帰納法を使います。
④ (x -> FirstLimited x -> AllLimited x) は、排中律により真か偽のどちらかです。
・真の場合
これと③を使って(a)が証明できます。
・偽の場合
これと③とパースの法則を使って(a)が証明できます。 >>750
> 示したい命題は、x -> FirstLimited x です。 ---(a)
？？？
x は単なる自然数でしょ？ なのに、x -> ・・・ と含意命題の仮定部に出て来るとは？？？
示したい命題って、AllLimited x -> FirstLimited x ですか？ となると④の命題は
任意の自然数xに対して「FirstLimited x ならば AllLimited x」
ですか。
②は
命題 -> 命題 -> 命題
の形になってるけどどういう意味？ ②は
「任意の自然数xに対して、α -> β -> P x」
α：￢(∀z::nat. (P z -> Q z))
β：((∀z::nat. (P z -> Q z)) -> (∀n::nat. P n))
です。 ＞ 命題 -> 命題 -> 命題
は、
十分条件1 -> 十分条件2 -> 命題
と書いても良いと思います。 A -> B -> C は
・「A ならば B」かつ「B ならば C」
・「A ならば B」ならば C
・A ならば 「B ならば C」
のどれかかと思ったけど
・「A かつ B」ならば C
ってこと？ あ、それとも
・「A または B」ならば C
ですか？ >>756
・A ならば 「B ならば C」
です。
（右結合といいます） 分かりました。
あとは③の証明がちゃんとできてるかどうかですね。 >>752
はぁ～、依存型サポートしてる関数プログラミング言語のIdris独特の記法なのね、、、 >>754の記号を使うと、②は
α：￢A
β：A -> B
の形をしていて、α が真なら β も常に真、したがって β があってもなくても変わらない
となってしまっているように見えますが、これも括弧の書き方のせいですかね。 >>762
>>754は間違いでした。
自分が不用意に括弧を付け足したせいです。
(Isabelleも>>754にはNGを返します)
正しくは以下です。
「任意の自然数xに対して、α -> β -> P x」
α：￢(∀z::nat. (P z -> Q z))
β：(∀z::nat. (P z -> Q z) -> (∀n::nat. P n))
しかしこれだと、βに(∀z::nat. (P z -> Q z))を渡せないので、
コラッツ予想の証明には使えません。 ②のαを少し変えて
「任意の自然数xに対して、α -> β -> P x」
α：(∀z::nat. ￢(P z -> Q z))
β：((∀z::nat. (P z -> Q z)) -> (∀n::nat. P n))
とすると、IsabelleもOKを返します。
これを使って上手いこと出来ないか考え中です。 >>750の③からIdrisで直接(∀n::nat. FirstLimited n)を証明できる
目処が立ちました。
パースの法則は使わずに済みそうです。
Isabelleも使わずに済みそうです。
Idrisプログラムを書き上げる事とWikiを手直しする事が必要ですが、
3か月くらいかけてじっくり取り組もうと思います。 テレンスタオ氏によって
コラッツ予想に進展があったみたいですね。 ■ このスレッドは過去ログ倉庫に格納されています
