2021-04-20 (火)

数学

p を奇素数とする。多項式 mod p の素因数分解について、A(X) = A_1(X) A_2(X), A_1(X) と A_2(X) は異なる d 次式としたとき、T(X) を 2d - 1 次以下の一様ランダムな多項式とすれば A_1 と A_2 が T(X)^{(p^d-1)/2} ± 1 の異なる方の約数になる確率は 1/2 程度以上という命題 (?) について、中国剰余定理から 2d-1 次までみないといけなそうなのは納得。そもそも mod A_1(X) と mod A_2(X) でそれぞれ d-1 次以下の多項式 p^d 個の中から一様ランダムに選ぶのは、mod A(X) で 2d-1 次以下の多項式 p^{2d} 個の中から一様ランダムに選ぶのと同値。A_1(X) が T(X), T(X)^{(p^d-1)/2} + 1, T(X)^{(p^d-1)/2} - 1 の約数になる確率はそれぞれ 1/p^d, (p^d-1)/2p^d, (p^d-1)/2p^d であり、A_2(X) についても同様だから、両方とも同じ因子の約数になってしまう確率は c := p^d として (1/c)^2 + 2((c-1)/2c)^2 = (2c^2-4c+6) / 4c^2 < 1/2 である。(c = p^d >= 3 なので)
やっと理解できた。


これの文脈で、n 状態の DFA A に対して L(A)^{rev} を受理する o(2^n) 状態の DFA が存在しないようなものが存在するか疑問に思った。存在した https://twitter.com/Mi_Sawa/status/1384424446916583424