[代數] 有關 Cyclotomic polynomial 的問題

看板Math作者 (肥鵝)時間3年前 (2020/09/09 17:59), 編輯推噓3(3推 0噓 105→)
留言108則, 3人參與, 3年前最新討論串1/2 (看更多)
(Def) Let zeta_n = exp(i 2pi/n), n-root of unity Let Phi_n(x) be the minimum poly of zeta_n over Q (Problem) Prove or disprove: Let g(x) in Z[x], deg(g) = n-1, with all coefficient nonnegative, n > 1. If g(zeta_n) = 0, then g(x) have periodic coefficient, which means g(x) = h(x) (1 + x^T + ... x^(kT)) for some k, T in N. Ex: Write (a_0, a_1, a_2, ...) instead of a_0 + a_1 x + a_2 x^2 + ... n = 6, g(x) = (1,2,3,1,2,3), g(zeta_6) = 0 (Remark) This problem holds for p-power n = p^c, since Phi_n(x) is of degree p^(c-1) (p-1) and already periodic with T = p^(c-1) (In fact, Phi_n(x) = 1 + x^T + ... + x^((p-1)T). ) For n not p-power, Phi_n(x) would have negative coefficient. Note that Phi_n(1) = 1 in this case. 沒什麼頭緒qw q 這個問題是在研究矩陣 M = [ a1 a2 a3 ... an ] [ an a1 a2 ... an-1 ] [ an-1 an a1 ... an-2 ] [ ... [ a2 a3 a4 ... a1 ] 的時候出現的, all ai nonnegative M 的特徵值是 a1 + a2 zeta_n^k + ... an zeta_n^(k(n-1)) k = 0, 1, ..., n-1 我想知道 det(M) 什麼時候不是 0 懷疑就是 ai not periodic 的時候 但做不出來ow o 畢竟 periodic 的時候明顯 det(M) = 0 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.130.155 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1599645556.A.987.html
推
09/09 20:07, 3年前 , 1F
Disprove. n=6, g(x)=(4,0,3,2,2,1).
09/09 20:07, 1F
→
09/09 20:12, 3年前 , 2F
你研究的矩陣跟某一類矩陣很像，如果是算行列式，給
09/09 20:12, 2F
→
09/09 20:12, 3年前 , 3F
你一個關鍵字：Hankel determinant
09/09 20:12, 3F
→
09/09 20:13, 3年前 , 4F
不知道會不會有關係
09/09 20:13, 4F
→
09/09 22:27, 3年前 , 5F
感謝 循線找到了 Toeplitz 和 circulant matrix
09/09 22:27, 5F
→
09/09 22:27, 3年前 , 6F
我怎麼就沒有發現特徵值就是 DFT qw q
09/09 22:27, 6F
→
09/09 22:28, 3年前 , 7F
也沒發現所有 circulant matrix 有一樣的特徵向量
09/09 22:28, 7F
→
09/09 22:31, 3年前 , 8F
原題應該改成數個 nonnegative periodic 相加
09/09 22:31, 8F
→
09/09 22:31, 3年前 , 9F
例如 (403221) = (202020) + (201201)
09/09 22:31, 9F
→
09/09 22:32, 3年前 , 10F
CRT 要上工了 能組合是一定沒問題
09/09 22:32, 10F
→
09/09 22:32, 3年前 , 11F
只是有沒有都是 nonnegative 而已
09/09 22:32, 11F
→
09/09 22:33, 3年前 , 12F
不過這其實就是 DFT 啊 有證跟沒證一樣...
09/09 22:33, 12F
→
09/09 22:36, 3年前 , 13F
mmm 是不是 nonnegative 大概要證 而且好難qw q
09/09 22:36, 13F
→
09/09 22:37, 3年前 , 14F
等等 好像能證
09/09 22:37, 14F
→
09/09 22:38, 3年前 , 15F
但今天沒空寫 晚點來想怎麼處理ow o
09/09 22:38, 15F
→
09/09 22:40, 3年前 , 16F
(202111) = (101010) + (101101)
09/09 22:40, 16F
→
09/09 22:47, 3年前 , 17F
不 還是會出問題 看來 GG 了qw q
09/09 22:47, 17F
→
09/09 22:52, 3年前 , 18F
看不懂原po發現了什麼東西和原文有關 所以我還是照
09/09 22:52, 18F
→
09/09 22:52, 3年前 , 19F
我原來想講的來回 XD
09/09 22:52, 19F
→
09/09 22:55, 3年前 , 20F
關於原文problem的部份 已經有兩位能人給出反例了
09/09 22:55, 20F
→
09/09 22:56, 3年前 , 21F
我想補充的是其實整個problem等價於在線性規劃中的
09/09 22:56, 21F
→
09/09 22:58, 3年前 , 22F
所劃出來的區域中找整數解 如果其區域是unbounded的
09/09 22:58, 22F
→
09/09 23:00, 3年前 , 23F
基本上就有無窮多組正整數解 舉個例子 考慮
09/09 23:00, 23F
→
09/09 23:02, 3年前 , 24F
(ax^3+bx^2+cx+d)(x^2-x+1) 我們希望其乘出來的多項
09/09 23:02, 24F
→
09/09 23:04, 3年前 , 25F
式 係數都是正整數 所以我們只要找到正整數a,b,c,d
09/09 23:04, 25F
→
09/09 23:06, 3年前 , 26F
滿足 a>0 b-a>=0 a-b+c>=0 b-c+d>=0 c-d>=0 d>=0即
09/09 23:06, 26F
→
09/09 23:06, 3年前 , 27F
可
09/09 23:06, 27F
→
09/09 23:10, 3年前 , 28F
接著就原PO真正想解的問題來看 看來似乎原po都是假
09/09 23:10, 28F
→
09/09 23:11, 3年前 , 29F
設ai是正整數的樣子(如果只是假設實數的話 5*5的矩
09/09 23:11, 29F
→
09/09 23:13, 3年前 , 30F
陣就有原po提到性質的反例了)
09/09 23:13, 30F
→
09/09 23:15, 3年前 , 31F
我是將整個問題轉化成複數平面上向量相加為零的情況
09/09 23:15, 31F
→
09/09 23:21, 3年前 , 32F
det(M)為0的充要條件是至少一個eigenvalue為0
09/09 23:21, 32F
→
09/09 23:24, 3年前 , 33F
所以根據複平面的向量加法 至少可以得到det=0的充分
09/09 23:24, 33F
→
09/09 23:25, 3年前 , 34F
條件(雖然沒有仔細check過 我覺得應該可以推到充要
09/09 23:25, 34F
→
09/09 23:26, 3年前 , 35F
條件) 例如說對6*6的情況而言 我們有下列det=0的充
09/09 23:26, 35F
→
09/09 23:27, 3年前 , 36F
分條件 "a0+a1+a2+a3+a4+a5=0" 或者 "a0+a2+a4=0
09/09 23:27, 36F
→
09/09 23:29, 3年前 , 37F
and a1+a3+a5=0" 或者 "a0+a3=a1+a4=a2+a5" 或者
09/09 23:29, 37F
→
09/09 23:31, 3年前 , 38F
"a0+a2+a4=a1+a3+a5" 四個條件其中一個滿足就可以了
09/09 23:31, 38F
→
09/09 23:34, 3年前 , 39F
比方說a0+a2+a4=a1+a3+a5 我們可以考慮(210100)
09/09 23:34, 39F
還有 29 則推文
→
09/10 06:22, 3年前 , 69F
"a0=a3 and a1=a4 and a2=a5" 這種看起來像cyclic
09/10 06:22, 69F
→
09/10 06:22, 3年前 , 70F
的條件
09/10 06:22, 70F
→
09/10 06:22, 3年前 , 71F
但第二式第三式卻給出了像
09/10 06:22, 71F
→
09/10 06:22, 3年前 , 72F
"a0+a3=a1+a4=a2+a5" 或者
09/10 06:22, 72F
→
09/10 06:22, 3年前 , 73F
"a0+a2+a4=a1+a3+a5"這種難以簡單描述的條件
09/10 06:22, 73F
推
09/10 06:31, 3年前 , 74F
就算單純只考慮第一個eigenvalue為0的情況 也不總是
09/10 06:31, 74F
→
09/10 06:31, 3年前 , 75F
會給出類似cyclic的條件 例如12*12的情況 我們可以
09/10 06:31, 75F
→
09/10 06:31, 3年前 , 76F
有
09/10 06:31, 76F
→
09/10 06:31, 3年前 , 77F
"a0=a4=a8, a2=a6=a10, a1=a7, a3=a9, a5=a11"的條
09/10 06:31, 77F
→
09/10 06:31, 3年前 , 78F
件
09/10 06:31, 78F
→
09/10 07:33, 3年前 , 79F
講一下屁話 如果單純只是想要可以計算的充要條件 其
09/10 07:33, 79F
→
09/10 07:34, 3年前 , 80F
實早就在前面有提到了 XD 令v1,v2,...,vn為n by n
09/10 07:34, 80F
→
09/10 07:37, 3年前 , 81F
circulant matrix的eigenvectors 則det(M(a))=0 若
09/10 07:37, 81F
→
09/10 07:39, 3年前 , 82F
且唯若 a至少和其中一個vi垂直 若且唯若 a是S的線性
09/10 07:39, 82F
→
09/10 07:40, 3年前 , 83F
組合 其中S是{v1,v2,...,vn}的nontrivial porper
09/10 07:40, 83F
→
09/10 07:42, 3年前 , 84F
subset 若且唯若 a落在union of span{v1,...v(i-1),
09/10 07:42, 84F
→
09/10 07:43, 3年前 , 85F
v(i+1),...,vn}, i runs over 1,2,...,n
09/10 07:43, 85F
→
09/10 08:23, 3年前 , 86F
XD 找到這篇文章 https://shorturl.at/pDU48 進一步
09/10 08:23, 86F
→
09/10 08:26, 3年前 , 87F
推廣上面的"屁話"結論成輾轉相除法的運算 並且可以
09/10 08:26, 87F
→
09/10 08:27, 3年前 , 88F
再進一步推成"若且唯若 f(x)是phi_m(x)的倍數 for
09/10 08:27, 88F
→
09/10 08:27, 3年前 , 89F
some m|n"
09/10 08:27, 89F
→
09/10 08:40, 3年前 , 90F
太久沒碰circulant matrix 感覺都鈍了 冏
09/10 08:40, 90F
→
09/10 09:44, 3年前 , 91F
連結掛了qw q
09/10 09:44, 91F
→
09/10 11:05, 3年前 , 92F
電腦開沒問題 可是手機開不了 冏 重新給一個
09/10 11:05, 92F
→
09/10 11:07, 3年前 , 93F
09/10 11:07, 93F
→
09/10 11:12, 3年前 , 94F
以下是基於"f(x)是phi_m(x)的倍數"的程式(SageMath)
09/10 11:12, 94F
→
09/10 11:12, 3年前 , 95F
09/10 11:12, 95F
→
09/10 11:14, 3年前 , 96F
其中n你可以設成你想要的size 而程式會打印出一堆多
09/10 11:14, 96F
→
09/10 11:15, 3年前 , 97F
項式 則det(M)=0若且唯若其中一個多項式為零多項式
09/10 11:15, 97F
→
09/10 11:17, 3年前 , 98F
比如就程式裡的例子 當n=6時 det(M)=0 若且唯若
09/10 11:17, 98F
→
09/10 11:18, 3年前 , 99F
"a0+a1+a2+a3+a4+a5=0" 或者
09/10 11:18, 99F
→
09/10 11:18, 3年前 , 100F
"a0+a2+a4=a1+a3+a5" 或者
09/10 11:18, 100F
→
09/10 11:19, 3年前 , 101F
"a0+a3=a1+a4=a2+a5" 或者
09/10 11:19, 101F
→
09/10 11:21, 3年前 , 102F
"a1+a2=a4+a5 and a0+a5=a2+a3"
09/10 11:21, 102F
→
09/10 11:24, 3年前 , 103F
而(ababab)或(abcabc)只是上面式子的特例
09/10 11:24, 103F
→
09/10 11:29, 3年前 , 104F
又或者改n=7時 det(M)=0 若且唯若
09/10 11:29, 104F
→
09/10 11:29, 3年前 , 105F
"a0+a1+a2+a3+a4+a5+a6=0" 或者
09/10 11:29, 105F
→
09/10 11:30, 3年前 , 106F
"a0=a1=a2=a3=a4=a5=a6"
09/10 11:30, 106F
→
09/10 11:33, 3年前 , 107F
現在比較麻煩的是程式僅針對ai是整數的情況(不過T大
09/10 11:33, 107F
→
09/10 11:34, 3年前 , 108F
好像也只關注這個情形)
09/10 11:34, 108F
‣ 更多 TimcApple 的文章
文章代碼(AID): #1VMATqc7 (Math)
‣ 更多 TimcApple 的文章
文章代碼(AID): #1VMATqc7 (Math)