作者TimcApple (肥鹅)
看板Math
标题有关 Cyclotomic polynomial 的问题
时间Wed Sep 9 17:59:14 2020
(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://webptt.com/cn.aspx?n=bbs/Math/M.1599645556.A.987.html
1F：推 Mathmaster : Disprove. n=6, g(x)=(4,0,3,2,2,1). 09/09 20:07
2F：→ Mathmaster : 你研究的矩阵跟某一类矩阵很像，如果是算行列式，给 09/09 20:12
3F：→ Mathmaster : 你一个关键字：Hankel determinant 09/09 20:12
4F：→ Mathmaster : 不知道会不会有关系 09/09 20:13
5F：→ TimcApple : 感谢 循线找到了 Toeplitz 和 circulant matrix 09/09 22:27
6F：→ TimcApple : 我怎麽就没有发现特徵值就是 DFT qw q 09/09 22:27
7F：→ TimcApple : 也没发现所有 circulant matrix 有一样的特徵向量 09/09 22:28
8F：→ TimcApple : 原题应该改成数个 nonnegative periodic 相加 09/09 22:31
9F：→ TimcApple : 例如 (403221) = (202020) + (201201) 09/09 22:31
10F：→ TimcApple : CRT 要上工了 能组合是一定没问题 09/09 22:32
11F：→ TimcApple : 只是有没有都是 nonnegative 而已 09/09 22:32
12F：→ TimcApple : 不过这其实就是 DFT 啊 有证跟没证一样... 09/09 22:33
13F：→ TimcApple : mmm 是不是 nonnegative 大概要证 而且好难qw q 09/09 22:36
14F：→ TimcApple : 等等 好像能证 09/09 22:37
15F：→ TimcApple : 但今天没空写 晚点来想怎麽处理ow o 09/09 22:38
16F：→ TimcApple : (202111) = (101010) + (101101) 09/09 22:40
17F：→ TimcApple : 不 还是会出问题 看来 GG 了qw q 09/09 22:47
18F：→ hwanger : 看不懂原po发现了什麽东西和原文有关 所以我还是照 09/09 22:52
19F：→ hwanger : 我原来想讲的来回 XD 09/09 22:52
20F：→ hwanger : 关於原文problem的部份 已经有两位能人给出反例了 09/09 22:55
21F：→ hwanger : 我想补充的是其实整个problem等价於在线性规划中的 09/09 22:56
22F：→ hwanger : 所划出来的区域中找整数解 如果其区域是unbounded的 09/09 22:58
23F：→ hwanger : 基本上就有无穷多组正整数解 举个例子 考虑 09/09 23:00
24F：→ hwanger : (ax^3+bx^2+cx+d)(x^2-x+1) 我们希望其乘出来的多项 09/09 23:02
25F：→ hwanger : 式 系数都是正整数 所以我们只要找到正整数a,b,c,d 09/09 23:04
26F：→ hwanger : 满足 a>0 b-a>=0 a-b+c>=0 b-c+d>=0 c-d>=0 d>=0即 09/09 23:06
27F：→ hwanger : 可 09/09 23:06
28F：→ hwanger : 接着就原PO真正想解的问题来看 看来似乎原po都是假 09/09 23:10
29F：→ hwanger : 设ai是正整数的样子(如果只是假设实数的话 5*5的矩 09/09 23:11
30F：→ hwanger : 阵就有原po提到性质的反例了) 09/09 23:13
31F：→ hwanger : 我是将整个问题转化成复数平面上向量相加为零的情况 09/09 23:15
32F：→ hwanger : det(M)为0的充要条件是至少一个eigenvalue为0 09/09 23:21
33F：→ hwanger : 所以根据复平面的向量加法 至少可以得到det=0的充分 09/09 23:24
34F：→ hwanger : 条件(虽然没有仔细check过 我觉得应该可以推到充要 09/09 23:25
35F：→ hwanger : 条件) 例如说对6*6的情况而言 我们有下列det=0的充 09/09 23:26
36F：→ hwanger : 分条件 "a0+a1+a2+a3+a4+a5=0" 或者 "a0+a2+a4=0 09/09 23:27
37F：→ hwanger : and a1+a3+a5=0" 或者 "a0+a3=a1+a4=a2+a5" 或者 09/09 23:29
38F：→ hwanger : "a0+a2+a4=a1+a3+a5" 四个条件其中一个满足就可以了 09/09 23:31
39F：→ hwanger : 比方说a0+a2+a4=a1+a3+a5 我们可以考虑(210100) 09/09 23:34
40F：→ hwanger : 而(210100)刚好就没有办法写成nonnegative periodic 09/09 23:35
41F：→ hwanger : 的相加 所以原po假设的条件仍有点不足 (我目前是认 09/09 23:36
42F：→ hwanger : 为在6*6的情况中 前面4个式子应该就是充要条件 但还 09/09 23:37
43F：→ hwanger : 没仔细check过就是了) 09/09 23:37
44F：→ hwanger : Ok 终於搞懂[22:27]和[22:28]间三行的回文在讲什麽 09/09 23:45
45F：→ hwanger : 了 因为我是用symmetric group表现理论和可交换矩阵 09/09 23:47
46F：→ hwanger : 的eigenspace decomposition来证这三行所提到的结论 09/09 23:48
47F：→ hwanger : 压根没想过跟DFT的关系 XD 09/09 23:48
48F：→ hwanger : 冏 要修正一下前面6*6的条件 因为ai皆为正整数 所以 09/09 23:56
49F：→ hwanger : 充分条件(我认为是充要条件)只剩两个 09/09 23:57
50F：→ hwanger : "a0+a3=a1+a4=a2+a5" 或者 "a0+a2+a4=a1+a3+a5" 09/09 23:58
51F：→ hwanger : 分析错了 冏 6*6 det=0的充分条件应该是 09/10 00:12
52F：→ hwanger : "a0+a1+a2+a3+a4+a5=0" 或者 09/10 00:13
53F：→ hwanger : "a0=a2=a4 and a1=a3=a5" 或者 09/10 00:14
54F：→ hwanger : "a0+a3=a1+a4=a2+a5" 或者 09/10 00:15
55F：→ hwanger : "a0+a2+a4=a1+a3+a5" 09/10 00:16
56F：→ hwanger : 因ai至少一个大於0 所以剩下後三个这样 09/10 00:19
57F：→ hwanger : 冏 还少一个条件 "a0=a3 and a1=a4 and a2=a5" 09/10 01:23
58F：→ hwanger : 可以理解为什麽原PO想把问题导到整系数多项式上了 09/10 06:15
59F：→ hwanger : 照原po的处理方式来看 原po只处理第一个eigenvalu 09/10 06:15
60F：→ hwanger : e为0的情况 似乎漏掉其他eigenvalue为0的情况(还是 09/10 06:15
61F：→ hwanger : 原po其实有注意到?) 09/10 06:15
62F：→ hwanger : 以6*6为例 令z为6次primitive root 原po好像只考虑 09/10 06:15
63F：→ hwanger : a0+a1z+a2z^2+a3z^3+a4z^4+a5z^5=0的情况 而似乎没 09/10 06:15
64F：→ hwanger : 有处理到 09/10 06:15
65F：→ hwanger : (a0+a3)+(a1+a4)z^2+(a2+a5)z^4=0 和 09/10 06:15
66F：→ hwanger : (a0+a2+a4)+(a1+a3+a5)^z^3=0 09/10 06:15
67F：推 hwanger : 第一个式子给出了像 09/10 06:22
68F：→ hwanger : "a0=a2=a4 and a1=a3=a5" 或者 09/10 06:22
69F：→ hwanger : "a0=a3 and a1=a4 and a2=a5" 这种看起来像cyclic 09/10 06:22
70F：→ hwanger : 的条件 09/10 06:22
71F：→ hwanger : 但第二式第三式却给出了像 09/10 06:22
72F：→ hwanger : "a0+a3=a1+a4=a2+a5" 或者 09/10 06:22
73F：→ hwanger : "a0+a2+a4=a1+a3+a5"这种难以简单描述的条件 09/10 06:22
74F：推 hwanger : 就算单纯只考虑第一个eigenvalue为0的情况 也不总是 09/10 06:31
75F：→ hwanger : 会给出类似cyclic的条件 例如12*12的情况 我们可以 09/10 06:31
76F：→ hwanger : 有 09/10 06:31
77F：→ hwanger : "a0=a4=a8, a2=a6=a10, a1=a7, a3=a9, a5=a11"的条 09/10 06:31
78F：→ hwanger : 件 09/10 06:31
79F：→ hwanger : 讲一下屁话 如果单纯只是想要可以计算的充要条件 其 09/10 07:33
80F：→ hwanger : 实早就在前面有提到了 XD 令v1,v2,...,vn为n by n 09/10 07:34
81F：→ hwanger : circulant matrix的eigenvectors 则det(M(a))=0 若 09/10 07:37
82F：→ hwanger : 且唯若 a至少和其中一个vi垂直 若且唯若 a是S的线性 09/10 07:39
83F：→ hwanger : 组合 其中S是{v1,v2,...,vn}的nontrivial porper 09/10 07:40
84F：→ hwanger : subset 若且唯若 a落在union of span{v1,...v(i-1), 09/10 07:42
85F：→ hwanger : v(i+1),...,vn}, i runs over 1,2,...,n 09/10 07:43
87F：→ hwanger : 推广上面的"屁话"结论成辗转相除法的运算 并且可以 09/10 08:26
88F：→ hwanger : 再进一步推成"若且唯若 f(x)是phi_m(x)的倍数 for 09/10 08:27
89F：→ hwanger : some m|n" 09/10 08:27
90F：→ hwanger : 太久没碰circulant matrix 感觉都钝了 冏 09/10 08:40
91F：→ TimcApple : 连结挂了qw q 09/10 09:44
92F：→ hwanger : 电脑开没问题 可是手机开不了 冏 重新给一个 09/10 11:05
94F：→ hwanger : 以下是基於"f(x)是phi_m(x)的倍数"的程式(SageMath) 09/10 11:12
96F：→ hwanger : 其中n你可以设成你想要的size 而程式会打印出一堆多 09/10 11:14
97F：→ hwanger : 项式 则det(M)=0若且唯若其中一个多项式为零多项式 09/10 11:15
98F：→ hwanger : 比如就程式里的例子 当n=6时 det(M)=0 若且唯若 09/10 11:17
99F：→ hwanger : "a0+a1+a2+a3+a4+a5=0" 或者 09/10 11:18
100F：→ hwanger : "a0+a2+a4=a1+a3+a5" 或者 09/10 11:18
101F：→ hwanger : "a0+a3=a1+a4=a2+a5" 或者 09/10 11:19
102F：→ hwanger : "a1+a2=a4+a5 and a0+a5=a2+a3" 09/10 11:21
103F：→ hwanger : 而(ababab)或(abcabc)只是上面式子的特例 09/10 11:24
104F：→ hwanger : 又或者改n=7时 det(M)=0 若且唯若 09/10 11:29
105F：→ hwanger : "a0+a1+a2+a3+a4+a5+a6=0" 或者 09/10 11:29
106F：→ hwanger : "a0=a1=a2=a3=a4=a5=a6" 09/10 11:30
107F：→ hwanger : 现在比较麻烦的是程式仅针对ai是整数的情况(不过T大 09/10 11:33
108F：→ hwanger : 好像也只关注这个情形) 09/10 11:34