有關 Cyclotomic polynomial 的問題

[TimcApple (肥鵝)]

(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
推 Mathmaster  : Disprove. n=6, g(x)=(4,0,3,2,2,1).
→ Mathmaster  : 你研究的矩陣跟某一類矩陣很像，如果是算行列式，給
→ Mathmaster  : 你一個關鍵字：Hankel determinant
→ Mathmaster  : 不知道會不會有關係
→ TimcApple   : 感謝 循線找到了 Toeplitz 和 circulant matrix
→ TimcApple   : 我怎麼就沒有發現特徵值就是 DFT qw q
→ TimcApple   : 也沒發現所有 circulant matrix 有一樣的特徵向量
→ TimcApple   : 原題應該改成數個 nonnegative periodic 相加
→ TimcApple   : 例如 (403221) = (202020) + (201201)
→ TimcApple   : CRT 要上工了 能組合是一定沒問題
→ TimcApple   : 只是有沒有都是 nonnegative 而已
→ TimcApple   : 不過這其實就是 DFT 啊 有證跟沒證一樣...
→ TimcApple   : mmm 是不是 nonnegative 大概要證 而且好難qw q
→ TimcApple   : 等等 好像能證
→ TimcApple   : 但今天沒空寫 晚點來想怎麼處理ow o
→ TimcApple   : (202111) = (101010) + (101101)
→ TimcApple   : 不 還是會出問題 看來 GG 了qw q
→ hwanger     : 看不懂原po發現了什麼東西和原文有關 所以我還是照
→ hwanger     : 我原來想講的來回 XD
→ hwanger     : 關於原文problem的部份 已經有兩位能人給出反例了
→ hwanger     : 我想補充的是其實整個problem等價於在線性規劃中的
→ hwanger     : 所劃出來的區域中找整數解 如果其區域是unbounded的
→ hwanger     : 基本上就有無窮多組正整數解 舉個例子 考慮
→ hwanger     : (ax^3+bx^2+cx+d)(x^2-x+1) 我們希望其乘出來的多項
→ hwanger     : 式 係數都是正整數 所以我們只要找到正整數a,b,c,d
→ hwanger     : 滿足 a>0 b-a>=0 a-b+c>=0 b-c+d>=0 c-d>=0 d>=0即
→ hwanger     : 可
→ hwanger     : 接著就原PO真正想解的問題來看 看來似乎原po都是假
→ hwanger     : 設ai是正整數的樣子(如果只是假設實數的話 5*5的矩
→ hwanger     : 陣就有原po提到性質的反例了)
→ hwanger     : 我是將整個問題轉化成複數平面上向量相加為零的情況
→ hwanger     : det(M)為0的充要條件是至少一個eigenvalue為0
→ hwanger     : 所以根據複平面的向量加法 至少可以得到det=0的充分
→ hwanger     : 條件(雖然沒有仔細check過 我覺得應該可以推到充要
→ hwanger     : 條件) 例如說對6*6的情況而言 我們有下列det=0的充
→ hwanger     : 分條件 "a0+a1+a2+a3+a4+a5=0" 或者 "a0+a2+a4=0
→ hwanger     : and a1+a3+a5=0" 或者 "a0+a3=a1+a4=a2+a5" 或者
→ hwanger     : "a0+a2+a4=a1+a3+a5" 四個條件其中一個滿足就可以了
→ hwanger     : 比方說a0+a2+a4=a1+a3+a5 我們可以考慮(210100)
→ hwanger     : 而(210100)剛好就沒有辦法寫成nonnegative periodic
→ hwanger     : 的相加 所以原po假設的條件仍有點不足 (我目前是認
→ hwanger     : 為在6*6的情況中 前面4個式子應該就是充要條件 但還
→ hwanger     : 沒仔細check過就是了)
→ hwanger     : Ok 終於搞懂[22:27]和[22:28]間三行的回文在講什麼
→ hwanger     : 了 因為我是用symmetric group表現理論和可交換矩陣
→ hwanger     : 的eigenspace decomposition來證這三行所提到的結論
→ hwanger     : 壓根沒想過跟DFT的關係 XD
→ hwanger     : 冏 要修正一下前面6*6的條件 因為ai皆為正整數 所以
→ hwanger     : 充分條件(我認為是充要條件)只剩兩個
→ hwanger     : "a0+a3=a1+a4=a2+a5" 或者 "a0+a2+a4=a1+a3+a5"
→ hwanger     : 分析錯了 冏 6*6 det=0的充分條件應該是
→ hwanger     : "a0+a1+a2+a3+a4+a5=0" 或者
→ hwanger     : "a0=a2=a4 and a1=a3=a5" 或者
→ hwanger     : "a0+a3=a1+a4=a2+a5" 或者
→ hwanger     : "a0+a2+a4=a1+a3+a5"
→ hwanger     : 因ai至少一個大於0 所以剩下後三個這樣
→ hwanger     : 冏 還少一個條件 "a0=a3 and a1=a4 and a2=a5"
→ hwanger     : 可以理解為什麼原PO想把問題導到整係數多項式上了
→ hwanger     :   照原po的處理方式來看 原po只處理第一個eigenvalu
→ hwanger     : e為0的情況 似乎漏掉其他eigenvalue為0的情況(還是
→ hwanger     : 原po其實有注意到?)
→ hwanger     : 以6*6為例 令z為6次primitive root 原po好像只考慮
→ hwanger     : a0+a1z+a2z^2+a3z^3+a4z^4+a5z^5=0的情況 而似乎沒
→ hwanger     : 有處理到
→ hwanger     : (a0+a3)+(a1+a4)z^2+(a2+a5)z^4=0 和
→ hwanger     : (a0+a2+a4)+(a1+a3+a5)^z^3=0
推 hwanger     : 第一個式子給出了像
→ hwanger     : "a0=a2=a4 and a1=a3=a5" 或者
→ hwanger     :  "a0=a3 and a1=a4 and a2=a5" 這種看起來像cyclic
→ hwanger     : 的條件
→ hwanger     : 但第二式第三式卻給出了像
→ hwanger     : "a0+a3=a1+a4=a2+a5" 或者
→ hwanger     : "a0+a2+a4=a1+a3+a5"這種難以簡單描述的條件
推 hwanger     : 就算單純只考慮第一個eigenvalue為0的情況 也不總是
→ hwanger     : 會給出類似cyclic的條件 例如12*12的情況 我們可以
→ hwanger     : 有
→ hwanger     : "a0=a4=a8, a2=a6=a10, a1=a7, a3=a9, a5=a11"的條
→ hwanger     : 件
→ hwanger     : 講一下屁話 如果單純只是想要可以計算的充要條件 其
→ hwanger     : 實早就在前面有提到了 XD 令v1,v2,...,vn為n by n
→ hwanger     : circulant matrix的eigenvectors 則det(M(a))=0 若
→ hwanger     : 且唯若 a至少和其中一個vi垂直 若且唯若 a是S的線性
→ hwanger     : 組合 其中S是{v1,v2,...,vn}的nontrivial porper
→ hwanger     : subset 若且唯若 a落在union of span{v1,...v(i-1),
→ hwanger     : v(i+1),...,vn}, i runs over 1,2,...,n
→ hwanger     : XD 找到這篇文章 https://shorturl.at/pDU48 進一步
→ hwanger     : 推廣上面的"屁話"結論成輾轉相除法的運算 並且可以
→ hwanger     : 再進一步推成"若且唯若 f(x)是phi_m(x)的倍數 for
→ hwanger     : some m|n"
→ hwanger     : 太久沒碰circulant matrix 感覺都鈍了 冏
→ TimcApple   : 連結掛了qw q
→ hwanger     : 電腦開沒問題 可是手機開不了 冏 重新給一個
→ hwanger     : https://reurl.cc/0OXOZx
→ hwanger     : 以下是基於"f(x)是phi_m(x)的倍數"的程式(SageMath)
→ hwanger     : https://paste.ofcode.org/yZAXLtP9vGdv8UvbJFCXB5
→ hwanger     : 其中n你可以設成你想要的size 而程式會打印出一堆多
→ hwanger     : 項式 則det(M)=0若且唯若其中一個多項式為零多項式
→ hwanger     : 比如就程式裡的例子 當n=6時 det(M)=0 若且唯若
→ hwanger     : "a0+a1+a2+a3+a4+a5=0" 或者
→ hwanger     : "a0+a2+a4=a1+a3+a5" 或者
→ hwanger     : "a0+a3=a1+a4=a2+a5" 或者
→ hwanger     : "a1+a2=a4+a5 and a0+a5=a2+a3"
→ hwanger     : 而(ababab)或(abcabc)只是上面式子的特例
→ hwanger     : 又或者改n=7時 det(M)=0 若且唯若
→ hwanger     : "a0+a1+a2+a3+a4+a5+a6=0" 或者
→ hwanger     : "a0=a1=a2=a3=a4=a5=a6"
→ hwanger     : 現在比較麻煩的是程式僅針對ai是整數的情況(不過T大
→ hwanger     : 好像也只關注這個情形)