コラッツ予想がとけたらいいな　その2

コラッツ予想がとけたらいいな　その2 at MATH

718:righ1113
19/04/26 22:52:24.34 edmDBtkV.net
>>716
繰り返したら元に戻るとか、
小さくなる、とかだったら良かったですけどね。

719:１３２人目の素数さん
19/04/27 17:46:18.20 PhPZ0MkR.net
>717 に引き続き, >523 を代数学風に整理.
前述(>717)の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).
系. コラッツ展開は単射.

720:１３２人目の素数さん
19/05/08 21:48:28.23 U/58yMQ3.net
コラッツ展開はかなりいい線いってるとは思うが、次の一歩が難しい？

721:１３２人目の素数さん
19/05/08 22:07:04.85 U/58yMQ3.net
例えばxのコラッツ展開のyビット目がxのサイズの多項式時間で求まれば大きな前進と言える？

722:１３２人目の素数さん
19/05/08 22:10:31.84 U/58yMQ3.net
ここでいうxのサイズっていうのは自然数xに対してそれを表すのに必要なビット数log(x)のことね

723:righ1113
19/05/09 06:34:48.07 ysyHHFnM.net
>>721
入力サイズに対して、
コラッツ操作で何回2で割るかが分からないので、
難しいと思います。
特殊な場合だと、
2^n±1は、コラッツ展開のnビット目までを
多項式(定数?)時間で求められます。

724:１３２人目の素数さん
19/05/09 07:08:14.74 +tHX/zWL.net
個人的には
・Z(有理整数環)→(Z/2Z)の列で単射になる
・>523の性質から、Z_2(2-進整数環)上にwell-definedに拡張できる
(環Zと素イデアル2Zの話が環Z_2と素イデアル2Z_2の話になるだけで、まったく同じロジックが展開できる)
・Z_2上全射(よって全単射)になる
ということでZ_2上で考えたらなんか出てこないかなー、とは。
コラッツ展開がループ
→一次方程式の解
→Q∩Z_2
とか。
なお、p-進整数環については、射影極限を経由するルートの方がわかりやすいかもしれません。

725:１３２人目の素数さん
19/05/09 08:06:12.63 +tHX/zWL.net
1ビットでも違うとそこから先は別物というか、カオス的な振る舞いをしますね
2で割ることで折りたたまれたフラクタル構造といいますか……

726:righ1113
19/05/09 08:26:35.55 c2RXSWlw.net
ところで、
>>686から書いている2-進整数とは少し違うものが英語版Wikipediaにあった。
URLﾘﾝｸ(en.wikipedia.org)
の"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-進整数って言うのかなあ。

727:１３２人目の素数さん
19/05/09 18:33:29.57 +tHX/zWL.net
2-進整数環Z_2においては、2Z_2の元でなければ可逆元となるので、47の逆元が2-進整数として存在します。
151/47と書くより151・47^-1と書く方が実情を正しく表現しているかもしれません。
また、加法・乗法は有理整数環上のものが延長されているので、分母が奇数の有理数についてはそのまま有理数として計算しても問題が発生することはありません。

728:righ1113
19/05/09 18:39:46.62 ysyHHFnM.net
ありがとうございます。
よく分かってないですが……
精進しますm(_ _)m

729:１３２人目の素数さん
19/05/09 19:13:07.75 yA5UfL3f.net
じゃあxのコラッツ展開のyビット目をもとめるのはNP困難か？
だったらどう？

730:１３２人目の素数さん
19/05/09 19:57:09.94 +tHX/zWL.net
分母が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 をかけるという手順で求まります。

731:727
19/05/09 20:16:04.29 19c66qNB.net
NP困難がむりでも素因数分解とかグラフの同型問題とかに帰着出来たら一定の成果と言えると思う。

732:１３２人目の素数さん
19/05/09 20:21:22.85 19c66qNB.net
あれ、逆か？
素因数分解とかグラフの同型問題をコラッツに帰着できるか？
かな

733:１３２人目の素数さん
19/05/09 21:52:30.09 19c66qNB.net
自然数xのコラッツ展開のxビット目、すなわちコラッツ展開の対角線に着目したら何か出てこないだろうか？

734:１３２人目の素数さん
19/05/09 22:16:54.60 19c66qNB.net
巨大数探索スレでは対角線というのは非常に注目されていて
ゲーデルの不完全性定理とかにもでてくる有用な概念らいしぞ。

735:１３２人目の素数さん
19/05/09 22:21:31.00 19c66qNB.net
例えば自然数xのコラッツ展開のyビット目をcollatz_bit(x,y)と置くとき、
collatz_bit(x,y)をxとyとcollatz_bit(z,z)で表すことが可能であれば、
本質的にコラッツの問題は対角線だけ着目すればいいという結論が出るかもわからない。
そうなったらちょっとすごい。

736:１３２人目の素数さん
19/05/09 23:11:30.02 19c66qNB.net
すまん、また先走ってしまったかもｗ

737:１３２人目の素数さん
19/05/11 00:46:16.20 fcymDsY6.net
>>719 の x-y∈(2^n)Z　という式をみて、ユークリッドの互除法みたいにどんどん小さくしていけないかなぁとふと思った。

738:１３２人目の素数さん
19/05/14 16:53:13.29 8Q7VJT2b.net
藁