Re: [代數] 問一題模考的多項式

[TimcApple (肥鵝)]

一部分原文刪除

: : Q1. 雖然可能的 a 只有一個，其它都不可能
: : 但要怎麼確定這個 a 真的是答案？
: 長除法、沒教的二次式綜合除法、用 x^2≡x-a 降次、代入 g 的根，四個選一個。
: 這應該是高中有超出範圍和沒超出範圍的範圍裡能用的招數了。

確實是這樣，目前試下來，先找出 a 之後，用二次綜合除法是最快的

: : Q2. 有沒有一個定理類似以下敘述，或是反例
: : 「設整係數多項式 f, g, 會有一個正整數 N = N(f, g) 使得
: : 若有 N 個相異 c 滿足 g(c) | f(c), 則 g(x) | f(x) in Q[x]」
: : 由於有 2 | n(n+1) 的情況，整除只能在有理數多項式內
: 如果要求兩多項式都 primitive 的話，整除就可以限制在 Z[x] 上了吧。

你說的對

: : Q3. 出題老師是怎麼知道，或是從哪裡知道
: : x^13 + x + 90 是 x^2 - x + a 的倍式的？
: 經驗或者前人的經驗吧？
: x^n+ax+b 這種長相的也算是比較單純的多項式了，
: 不知道有沒有資料庫在分類？

最近想到一個方法

考慮 x (cx+d) = cxx + dx = c(x-a) + dx = (c+d)x - ac

可以設矩陣 X =
[ 1 1]
[-a 0]

向量 1 = (0,1), x = (1,0), 設 x^n = (c_n, d_n), 則

(1) x^n = X x^(n-1)

(2) c_n = c_(n-1) - a c_(n-2)
    d_n = d_(n-1) - a d_(n-2)

(3) X^n = [x^n, x^(n-1)]

利用 (2), 使用 a = 2, 可以得到以下數列

0, 1,  1, -1, -3, -1, 5,   7,  -3, -17, -11, 23,  45,  -1
1, 0, -2, -2,  2,  6, 2, -10, -14,   6,  34, 22, -46, -90

在 n = 13 的時候冒出了一項特別小的 -1


如果只是要給出一組數值的話，在選完二次式之後

可以用這個遞迴去搜尋有沒有 +-1 的項出現

不過我是想知道，為什麼 n = 13 時會有一項很小的數字就是



另一方面，設 x^2 - x + a = 0 的兩根是 u, v

則 c_n = 1/(u-v) (   u^n -   v^n)
   d_n = 1/(u-v) (-v u^n + u v^n) = -a c_(n-1)

當 D = 1 - 4a < 0 時，u, v 可以寫成 r (cos t +- i sin t)

因此 c_n = r^(n-1) (sin nt)/(sin t)

有沒有什麼定理，可以討論 n 是多少的時候

r^(n-1) sin nt 會產生足夠小的數字，或是讓 c_n = +-1 這樣


: : g(c) | f(c) 是 in Z, 但 g(x) | f(x) 是 in Q[x]
: : 或者我應該寫 存在正整數 M 使得 g(x) | M f(x) in Z[x]
: : 我目前想一想 方向有兩個
: : (1) 有沒有可能 g(x) 不整除 M f(x)
: : 但是有無限多個 c 滿足 g(c) | f(c)
: : (2) N 能被控制到多小的範圍
: 我是想先從 f,g 都 primitive 下手，m = deg(f) 而且 n = deg(g)，當然 m≧n。
: 如果 g(c) 都不是 0，那 f(c)/g(c) 就都是整數。
: 要是 c 有 m+1 個，可以拿其中 m-n+1 個用拉格朗日插值插出一個 h(x) in Q[x]，
: 其中 h(c) = f(c)/g(c) for all c。
: 在這裡如果能確保 deg(h) = m-n、而且每組 c 都插出同一個 h 的話，
: 那 N 就是 m+1。
: 不過這個條件感覺用起來很麻煩，
: 所以也可以換成直接拿 m+1 個 c 去插，但要能確保插出一個 m-n 次的 h，
: 也就是 m-n+1 次以上的係數都要是 0（而且 m-n 次的係數不能是 0）。
: 這樣 f 和 gh 就在 m+1 個相異數字上等值，所以 f = gh in Q[x]。
: 但如果有某個 g(c) 是 0，那我們可能很難看出 f 和 g 中 x-c 的重數。
: 要是 g 的 x-c 比 f 的還多，那就怎樣都不能整除了。
: 不過這方面不用擔心，因為我們看這個 c 也只看一次（所有 c 都相異）。
: 至於要求 primitive 則是因為我想起了個叫做 numerical polynomial 的東西。
: F in Q[x]，當整數 n 超過某數後 F(n) 都是整數，
: 那 F(x) 就可以寫成 C(x,k) 的線性組合，而且係數都是整數。
: 所以即便上面那個 h 的圖形通過無限多個格子點，
: 那也很難保證 h 是整係數的，反例就是 x(x+1)/2 這種。
: （其實 numerical polynomial 代任何整數都會算出整數。）
: 但是如果要求 f 和 g 都 primitive，
: 那 h 的 primitive part 和 g 的乘積就會是 f，
: 但 f = gh，所以 h = h 的 primitive part，也就是一個整係數多項式。
: 所以就這題來說，隨便挑 14 個相異整數 c 去算 f(c)/g(c) 然後插出 h。
: c   │  f(c)/g(c)
: ──┴───────
: -6      -296833953
: -5      -38146970
: -4      -3050399
: -3      -113874
: -2      -1013
: -1      22
: 0       45
: 1       46
: 2       2071
: 3       199302
: 4       4793497
: 5       55486510
: 6       408146691
: 7       2202022966
: 然後插出來的是 x^11+x^10-x^9-3x^8-x^7+5x^6+7x^5-3x^4-17x^3-11x^2+23x+45。
: 的確 h 的 13、12 次係數是 0，而且 11 次係數不是 0。
: 又因為 f、g 都有係數 1 的項 => 都 primitive，
: 那就能知道 f = gh，而且 h 也的確是整係數多項式。
: 總之我覺得須要增加條件：
: f 和 g 都 primitive
: （不加這條的話，會有 g(c)|content(f) 的問題，那這樣我們會對 f 知之甚少。
:   又或者為了要把 g = content(f) 的因數的情況盡數排除，
:   只好在 N 上加上很多個 n，大概有 content(f) 的因數個數那麼多個 n。）
: 和 h 的高次項係數要 0 掉。
: 而第二個條件可以寫成
: Σf(c_i)/g(c_i) * c_i^k/d_i = 0, for k < n
: Σf(c_i)/g(c_i) * c_i^n/d_i ≠ 0        ，其中 d_i = Π_{j≠i} (c_i - c_j)
: 後半句應該是多餘的，因為多項式全等定理會保證 deg(h) = m-n，所以就不上色了。
: 此時 N = m+1。

primitive 很好，以下都會採取這個設定

不過我之前想歪了，往另一方面想去了

我是在想要怎麼否決掉 g(x), 也就是確認 f(x) 不是 g(x) 的倍式


考慮 f(x) = g(x) Q(x) + r(x), 其中 r(x) 不是 0

會有一個適合的 d 使得 d Q(x) 和 d r(x) 都是整係數

設 M = 2 * max{ g(x) 和 d r(x) 的係數的絕對值 } + 1

由於 deg g(x) > deg r(x) >= 0

容易得到 |g(M)| > |d r(M)| > 0

因此 d f(x)/g(x) = d Q(x) + d r(x)/g(x)

在代入 M 的時候, 右手邊一定不是整數, 因此可以捨去 g(x)


由於可以使用 f(x) 和 g(x) 的係數，估計 d r(x) 係數的大小

這代表如果 M 選得好，可以代一次就解決 f(x) 是不是 g(x) 倍式

但我希望的是任選數字，所以你的 N = m+1 應該是比較好的看法

畢竟即使 f(x)/g(x) 是有理多項式，在代完 m+1 個點後也強迫整係數了



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.10.106.171 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1638511459.A.D34.html
推 Vulpix      : 我那邊有洞，晚點補一補。
推 RicciCurvatu: 如果 r=N! g=x 那r/g 會有 2N 個正整數解以上 我有
→ RicciCurvatu: 點懷疑大N 只能被deg決定
推 Vulpix      : 矩陣那邊，前面那串就是Q的係數嘛！
→ Vulpix      : cd通式都有了，不是確認一下前幾項都是整數也就可
→ Vulpix      : 以了嗎？
推 cmrafsts    : 我覺得最簡單的檢驗a=2是解的方法是用快速冪。心情
→ cmrafsts    : 應該也比較愉快。
推 Vulpix      : c_n也可以寫成 √2^(n-1)*U_{n-1}(1/2√2)，或許也
→ Vulpix      : 可以從 Chebyshev polynomial 的性質去找 ±1 吧。