数学
pocky氏から前に聞いた問題
問題
非負整数係数多項式fがある。
fの具体的な式は分からないが、整数xに対してf(x)を求める事はできる。
fの具体的な式を特定するためにはf(x)を何度求めればよいか？
例えば
f(0)=1、f(2)=1ならf(x)=1
f(0)=0、f(1)=1、f(2)=4ならf(x)=x^2
とそれぞれ特定できる
答え
f(1)とf(f(1)+1)を求めれば良い
f(x)=Σai*x^iとおくと任意のnに対しan≦Σai=f(1)となる
よってf(f(1)+1)の値を(f(1)+1)進法の数値として解釈すると(f(1)+1)^nの位の数としてanが得られる
問題
非負整数係数多項式fがある。
fの具体的な式は分からないが、整数xに対してf(x)を求める事はできる。
fの具体的な式を特定するためにはf(x)を何度求めればよいか？
例えば
f(0)=1、f(2)=1ならf(x)=1
f(0)=0、f(1)=1、f(2)=4ならf(x)=x^2
とそれぞれ特定できる
答え
f(1)とf(f(1)+1)を求めれば良い
f(x)=Σai*x^iとおくと任意のnに対しan≦Σai=f(1)となる
よってf(f(1)+1)の値を(f(1)+1)進法の数値として解釈すると(f(1)+1)^nの位の数としてanが得られる
LTEの補題
Lifting The Exponent Lemmaというものを知った。
ざっとググった限り、二項定理を用いた証明がなさそうだったのでメモ。
定理の主張はこちらのpdf（英語）を参照したが証明は読んでいない
（このpdfの方針に忠実な(?)日本語の説明がこちらのサイトにある）
何やら魔術的な式変形が多く、二項定理を使ったほうが簡単なのではないかなあと思う。
定理1
pを奇素数とし、p進付値をvとする。
x,y∈Zpに対し次が成立
v(x)=v(y)=0かつv(x-y)≧1⇒任意のn≧0に対しv(x^n-y^n)=v(x-y)+v(n)
系1
v(x)=v(y)=0かつv(x+y)≧1⇒任意の奇数n≧0に対しv(x^n+y^n)=v(x+y)+v(n)
定理2
vを2進付値とするとき、x,y∈Z2に対し次が成立
v(x)=v(y)=0かつv(x-y)≧2⇒任意のn≧0に対しv(x^n-y^n)=v(x-y)+v(n)
系2
v(x)=v(y)=0かつv(x-y)≧1⇒任意の偶数n≧0に対しv(x^n-y^n)=v(x-y)+v(n)+v(x+y)-1
整数の範囲で言い直すとこうなる
定理1（整数版）
pを奇素数とし、整数xに対し「xがp^kで割り切れる最大のk」をv(x)とする。
x,y∈Zに対し次が成立
v(x)=v(y)=0かつv(x-y)≧1⇒任意のn≧0に対しv(x^n-y^n)=v(x-y)+v(n)
以下証明
ざっとググった限り、二項定理を用いた証明がなさそうだったのでメモ。
定理の主張はこちらのpdf（英語）を参照したが証明は読んでいない
（このpdfの方針に忠実な(?)日本語の説明がこちらのサイトにある）
何やら魔術的な式変形が多く、二項定理を使ったほうが簡単なのではないかなあと思う。
定理1
pを奇素数とし、p進付値をvとする。
x,y∈Zpに対し次が成立
v(x)=v(y)=0かつv(x-y)≧1⇒任意のn≧0に対しv(x^n-y^n)=v(x-y)+v(n)
系1
v(x)=v(y)=0かつv(x+y)≧1⇒任意の奇数n≧0に対しv(x^n+y^n)=v(x+y)+v(n)
定理2
vを2進付値とするとき、x,y∈Z2に対し次が成立
v(x)=v(y)=0かつv(x-y)≧2⇒任意のn≧0に対しv(x^n-y^n)=v(x-y)+v(n)
系2
v(x)=v(y)=0かつv(x-y)≧1⇒任意の偶数n≧0に対しv(x^n-y^n)=v(x-y)+v(n)+v(x+y)-1
整数の範囲で言い直すとこうなる
定理1（整数版）
pを奇素数とし、整数xに対し「xがp^kで割り切れる最大のk」をv(x)とする。
x,y∈Zに対し次が成立
v(x)=v(y)=0かつv(x-y)≧1⇒任意のn≧0に対しv(x^n-y^n)=v(x-y)+v(n)
以下証明
けもフレ
「アラフェネは役割を交代しながら一方ずつ世代交代している」という電波を受信したのでメモ。
SSにでも仕上げるだけの能力があればよかったのだけど、ないので受信した内容だけざっくり。
・作中現代の偶数周期前
アライさんが転生(再フレンズ化)する
"今"のフェネアラのような関係性
アライさんは何も考えずにのほほんと生きてる
・奇数周期前
フェネックが転生する
かつての自分にとってのフェネックの役割を、今度は自分が果たすのだ、と柄にもなくちょっと無理をして頑張るアライさん。自分がしっかりしていればもう二度とフェネックを失うことはないのだと。
一方フェネックは、アライさんが自分のために無理をして頑張っていることを察していて、そんなアライさんの姿にちょっと憧れる。そして、いつか自分がもっとしっかりすれば、アライさんが無理をすることもなくなるだろうとも。
・偶数周期前再
アライさんが転生する
自分のために頑張っていたアライさんを見ていたからこそ、自由奔放に活動するいまのアライさんに過度に干渉せず、少しのノスタルジーとともに眺めるフェネック。
互いに"昔"からの付き合いであるからこそ、ふたりは決して離れない、離れることができないのだ。
(2021/07/14追記)
イメージにかなり近い作品があった。
https://www.pixiv.net/artworks/61916949
SSにでも仕上げるだけの能力があればよかったのだけど、ないので受信した内容だけざっくり。
・作中現代の偶数周期前
アライさんが転生(再フレンズ化)する
"今"のフェネアラのような関係性
アライさんは何も考えずにのほほんと生きてる
・奇数周期前
フェネックが転生する
かつての自分にとってのフェネックの役割を、今度は自分が果たすのだ、と柄にもなくちょっと無理をして頑張るアライさん。自分がしっかりしていればもう二度とフェネックを失うことはないのだと。
一方フェネックは、アライさんが自分のために無理をして頑張っていることを察していて、そんなアライさんの姿にちょっと憧れる。そして、いつか自分がもっとしっかりすれば、アライさんが無理をすることもなくなるだろうとも。
・偶数周期前再
アライさんが転生する
自分のために頑張っていたアライさんを見ていたからこそ、自由奔放に活動するいまのアライさんに過度に干渉せず、少しのノスタルジーとともに眺めるフェネック。
互いに"昔"からの付き合いであるからこそ、ふたりは決して離れない、離れることができないのだ。
(2021/07/14追記)
イメージにかなり近い作品があった。
https://www.pixiv.net/artworks/61916949
フィボナッチ数列 mod n
以下の内容は、だいたいwikipediaのリライトです。Pisano period（英語）
フィボナッチ数列の第k項をF[k]と表し、F[0]=1、F[1]=1とする。
mod n でのフィボナッチ数列の周期を考える。これをσ(n)とおく。（一般的な記号ではない）
例えばmod 7で考えると
0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,1,1,…
となり、σ(7)=16が確かめられる。
・簡単のため、漸化式を行列で扱う考え方を用いる
(0 1)
(1 1) という2×2行列をA
(F[k] F[k+1])を転置した縦ベクトルをv[k]とする。
任意のa,bに対して
(A^a)v[b]=v[a+b]と
(F[a-1] F[a ])
(F[a ] F[a+1])=A^a
が成立する。
（これらはaに関する帰納法を用いればすぐわかる）
・F[σ(n)]=0、F[σ(n)]=1
（つまり、「途中からループ」となることはなく、必ず最初に戻るということ）
（a,b）→（b,a+b）という遷移が全単射であることから明らか。
（途中から合流することはありえない）
このことと上で求めたA^aより、A^σ(n)がmod nで単位行列となることがわかる。
（また、σ(n)はAのGL(Z/nZ)における位数であることもわかる）
・互いに素なa,bに対しσ(ab)=LCM(σ(a),σ(b))
（中国剰余定理から明らか）
よって、素数べきのときだけ考えれば良い
・素数pとk≧1に対しσ(p^(k+1))はp^k*σ(p)の約数
σ(p^(k+1))がp*σ(p^k)の約数であることを言えば帰納法からわかる。
A^σ(p^k)がmod p^kで単位行列となるので、mod p^(k+1)ではあるa,b,cを用いて
(a*p^k+1 b*p^k )
(b*p^k c*p^k+1) とかける。ここでこの行列のm乗はmod p^(k+1)で
(a*m*p^k+1 b*m*p^k )
(b*m*p^k c*m*p^k+1) となることが計算で確かめられるので、
A^(p*σ(p^k))はmod p^(k+1)で単位行列。よってσ(p^(k+1))はp*σ(p^k)の約数
・で、σ(p^(k+1))≠p^k*σ(p)になる素数pって知られてるの？
1つも知られていない。存在するかどうかも不明。
そのようなものは存在しないだろうという予想が「Wall予想」と呼ばれており、これは未解決問題。
以上から、（Wall予想を認めれば）あとは素数pに対してσ(p)がわかれば良い
・p=2のとき0,1,1,0,1,1,0,1,1,…となるのでσ(2)=3
・p=5のとき0,1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0,1,1,…となるのでσ(5)=20
残りの素数については、(★) F[n]=(φ^n-(-φ^(-1))^n)/(2φ-1)という式を用いて、有限体Fp上で考える
・p=5k±1のとき
このとき平方剰余の相互法則から、√5∈Fpであるからφ∈Fpとなり、★式はFp上で意味を持つ。
φはFpの元であるから(p-1)乗すると1となることを用いてF[p-1]=0、F[p]=1がわかる。
よってσ(p)は(p-1)の約数
・p=5k±2、(p≠2)のとき
このとき平方剰余の相互法則から、√5がFpの元でないのでφはFpの元でない。
Fpにφを添加した体Fp(φ)上で考えると★式はFp(φ)上で意味を持つ。
φはx^2-x-1の根なので、Fp(φ)はFpの2次拡大。共役なものは-φ^(-1) （根と係数の関係）
ここで、フロベニウス写像x→x^pを考えると、これはAut(Fp(φ)/Fp)の自明でない元なので、φを-φ^(-1)にうつす。
つまりφ^p=-φ^(-1)となるので、φ^(2p+2)=1
このことを使いFp(φ)上で★式を考えるとF[2p+2]=0、F[2p+3]=1がわかる。
よってσ(p)は(2p+2)の約数
・で、σ(p)≠p-1、2p+2になる素数pって知られてるの？
たくさんある。
前者ならσ(29)=14、σ(61)=30、σ(199)=22、σ(9349)=38など
後者ならσ(47)=32、σ(107)=72、σ(307)=88、σ(2207)=64など
以上の結果をまとめると
a,bが互いに素ならσ(ab)=LCM(σ(a),σ(b))
素数pとk≧1に対しσ(p^(k+1))はp^k*σ(p)の約数
σ(2)=3、σ(5)=20
p=5k±1のときσ(p)は(p-1)の約数
p=5k±2のときσ(p)は(2p+2)の約数
フィボナッチ数列の第k項をF[k]と表し、F[0]=1、F[1]=1とする。
mod n でのフィボナッチ数列の周期を考える。これをσ(n)とおく。（一般的な記号ではない）
例えばmod 7で考えると
0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,1,1,…
となり、σ(7)=16が確かめられる。
・簡単のため、漸化式を行列で扱う考え方を用いる
(0 1)
(1 1) という2×2行列をA
(F[k] F[k+1])を転置した縦ベクトルをv[k]とする。
任意のa,bに対して
(A^a)v[b]=v[a+b]と
(F[a-1] F[a ])
(F[a ] F[a+1])=A^a
が成立する。
（これらはaに関する帰納法を用いればすぐわかる）
・F[σ(n)]=0、F[σ(n)]=1
（つまり、「途中からループ」となることはなく、必ず最初に戻るということ）
（a,b）→（b,a+b）という遷移が全単射であることから明らか。
（途中から合流することはありえない）
このことと上で求めたA^aより、A^σ(n)がmod nで単位行列となることがわかる。
（また、σ(n)はAのGL(Z/nZ)における位数であることもわかる）
・互いに素なa,bに対しσ(ab)=LCM(σ(a),σ(b))
（中国剰余定理から明らか）
よって、素数べきのときだけ考えれば良い
・素数pとk≧1に対しσ(p^(k+1))はp^k*σ(p)の約数
σ(p^(k+1))がp*σ(p^k)の約数であることを言えば帰納法からわかる。
A^σ(p^k)がmod p^kで単位行列となるので、mod p^(k+1)ではあるa,b,cを用いて
(a*p^k+1 b*p^k )
(b*p^k c*p^k+1) とかける。ここでこの行列のm乗はmod p^(k+1)で
(a*m*p^k+1 b*m*p^k )
(b*m*p^k c*m*p^k+1) となることが計算で確かめられるので、
A^(p*σ(p^k))はmod p^(k+1)で単位行列。よってσ(p^(k+1))はp*σ(p^k)の約数
・で、σ(p^(k+1))≠p^k*σ(p)になる素数pって知られてるの？
1つも知られていない。存在するかどうかも不明。
そのようなものは存在しないだろうという予想が「Wall予想」と呼ばれており、これは未解決問題。
以上から、（Wall予想を認めれば）あとは素数pに対してσ(p)がわかれば良い
・p=2のとき0,1,1,0,1,1,0,1,1,…となるのでσ(2)=3
・p=5のとき0,1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0,1,1,…となるのでσ(5)=20
残りの素数については、(★) F[n]=(φ^n-(-φ^(-1))^n)/(2φ-1)という式を用いて、有限体Fp上で考える
・p=5k±1のとき
このとき平方剰余の相互法則から、√5∈Fpであるからφ∈Fpとなり、★式はFp上で意味を持つ。
φはFpの元であるから(p-1)乗すると1となることを用いてF[p-1]=0、F[p]=1がわかる。
よってσ(p)は(p-1)の約数
・p=5k±2、(p≠2)のとき
このとき平方剰余の相互法則から、√5がFpの元でないのでφはFpの元でない。
Fpにφを添加した体Fp(φ)上で考えると★式はFp(φ)上で意味を持つ。
φはx^2-x-1の根なので、Fp(φ)はFpの2次拡大。共役なものは-φ^(-1) （根と係数の関係）
ここで、フロベニウス写像x→x^pを考えると、これはAut(Fp(φ)/Fp)の自明でない元なので、φを-φ^(-1)にうつす。
つまりφ^p=-φ^(-1)となるので、φ^(2p+2)=1
このことを使いFp(φ)上で★式を考えるとF[2p+2]=0、F[2p+3]=1がわかる。
よってσ(p)は(2p+2)の約数
・で、σ(p)≠p-1、2p+2になる素数pって知られてるの？
たくさんある。
前者ならσ(29)=14、σ(61)=30、σ(199)=22、σ(9349)=38など
後者ならσ(47)=32、σ(107)=72、σ(307)=88、σ(2207)=64など
以上の結果をまとめると
a,bが互いに素ならσ(ab)=LCM(σ(a),σ(b))
素数pとk≧1に対しσ(p^(k+1))はp^k*σ(p)の約数
σ(2)=3、σ(5)=20
p=5k±1のときσ(p)は(p-1)の約数
p=5k±2のときσ(p)は(2p+2)の約数
