すっきりと解決したのでメモ. {-1,0,+1}要素のランダムなn次元ベクトル (c_0,...,c_{n-1}) を考えて対応する巡回行列を確率変数としてP_nとおく. l_2-ノルムに対応する作用素ノルムの上限は固有値の絶対値の上限に等しい. (n次正方行列を考えるので.) 巡回行…

格子点の個数がわからない 僕は組合せの話は知らない／分からないのですが、なぜか次のタイプの問題にしばしば遭遇します； R^nの第1象限 {(x_1, ..., x_n)∈R^n | x_1≧0, ..., x_n≧0 } の範囲で、非負整数kに対して、 方程式 x_1 + ... + x_n = k 不等式 x_1…

コンピュータ代数ハンドブック作者: J.フォンツァガテン,J.ゲルハルト,山本慎,三好重明,原正雄,谷聖一,衛藤和文出版社/メーカー: 朝倉書店発売日: 2006/06メディア: 単行本 クリック: 28回この商品を含むブログ (2件) を見る Modern Computer Algebra作者: J…

既存の論文（主要な著者は4-5人程度) だと記号の使い方が引き継がれているのだが, 場合によって新しく記号をつけ直したりすると読み辛くてしょうがない. 数学系から格子に入ると横ベクトル主体で書く. 2000年以降の暗号から入ると縦. 符号も元々横ベクトルで…

2^{2n}回のZ_q上の操作または集合演算を, qn^2回の実数演算に落とせた. フーリエ変換は偉大である. これでn=1024でもテストできるようになった. 今までn=8でしか出来てなかったことに比べれば進歩だな. (nが大きければ大きい分だけ桁落ちが起きそうで, それ…

面倒臭くってリンクする気が起きない. 非ゼロの整数に関しては素因数分解した結果の指数の列を無限次元ベクトルと考えると一意性が楽に示せますねと思いました. を 2^{Z^+}みたいに考えるというのが数学的には単純で宜しいと. 1は(0,0,...)と対応して良いと.…

n=2^k,q:素数かつ2n|q-1,D={0,1}とする. wはZ_q^*の位数2nの部分群を生成するものとする. 簡単のためにn=4,q=17とする. このときw=2が取れる. さらにZ_q[X]/X^n+1を考える. X^n+1=(X-2)(X-8)(X-15)(X-9)となり, この環のイデアルはこの4つの1次多項式の積で…

何か適当に考えていたら相反多項式に当たったのでメモ. 以下, とする.を考える. これとを同一視する. について, (縦ベクトル) と対応付ければ良い. 次にと関数rを定義する. 一回だけ回すイメージ. 更に関数Rをとして定義する. R(a)はfがのとき巡回行列. fが…

Wikipediaの日本語版だと無かったので適当に英語版にリンク. Carmichael number - Wikipedia, the free encyclopedia. 奇合成数nについて, 任意の1以上n-1以下の整数aに対してa^n≡a (mod n)が成立するとき, そのnをカーマイケル数と呼ぶ. (今日の説明では互…

フィボナッチ数の話をしていて話題に出たのでメモ. 絶対誰かしら書いているだろうと思ったら, 青空学園数学科にあった. 数学対話 - 数列と行列の中でも二次行列と漸化式の辺りを参照のこと.

Structure and Randomness: pages from year one of mathematical blog « What’s new 2007年分が本になったらしい. 講義用の資料とかも全部載っている筈. 28ドルと安いだから買おうかな.

格子の話があるので行ってみようかとも思ったが遠い(;´Д｀) ちょっとした旅行気分ですよ千葉とか (出不精).関係ない話ですが, ( ´ん｀)とするとちゃんと鼻があっていいですね.

ref 2の100乗の階乗が何桁になるかを暗算で計算するにはどうするか - きしだのはてな 2の100乗の桁数 - odz buffer 適当に近似してみましょう. とおく. Stirlingの近似式より. よって, . 細かい項を無視して, . () って感じですかね. 暗算だと.

(k:0以上の整数) はF_3上でに因数分解でき, それぞれ既約な気がする. d次の多項式fのF_3上の既約性を判断するには, F_3のd次拡大を考えてやる. すると多項式がd次以下のdの約数の次数を持つモニックかつ既約な多項式の積になっている. なので最初に rem f = …

平均が存在しないことで有名な分布. それはさておき, Cy(m,s)をコーシー分布とする. 確率密度関数はである. 0<e<1かつs>1についてCy(m,s)とCy(m,s+e)と2つ考えたときに統計的距離は2eで抑えられる.真面目に積分した. arctanとか久しぶりに見たよ(;´Д｀) 以下証明. Δを</e<1かつs>…

メモ. パラメータが(k,n-k+1)のベータ分布を考える. 確率密度関数はである. が成立する. binom出すのが面倒臭いので高校の記法で. (部分積分を順次適用することで得られる.)

q : 素数, n, m : 整数 のとき、 を示せ。0 < n < q^m とします。 逆にした方が分かり易いんじゃないでしょうか. 証明 Z/qZ上で, 恒等式が成立すれば題意が言える.まずZ/qZでを示す. これは割と簡単に言えて, の係数は. 0 < a < qについてとなるのでOK. (\bi…

p:素数, p|nとする. を示せ. 某講義ノートに証明無しで書かれていて困った. p≠nは必要ない. イコールの場合は両辺ともに1なので問題なし Hさんの解答 である. もしpがnの最小の素因数であれば, 右側のn/p以外の項の分子からnを除いても良い (modulo nで考え…

A remark on primality testing and the binary expansion « What’s new 論文の方を読む気はしないが面白い結果だなー. 十分大きなnについてnビットの素数pが存在し, i=0,...,n-1についてp \pm 2^iは全て合成数. 決定的な素数判定では全ビット読む必要があり…

ref:わたしが知らないスゴ本は、きっとあなたが読んでいる: 数学ぎらいは幸せになれないか? 「生き抜くための数学入門」のコメント欄.簡便のため, Nは0を含むとする. 数学的な記法で表すと以下になる. 証明 任意の自然数について, であることは明らか. 以下,…

Computational Complexity: An Open Problem wiki!からOpen Problem GardenをたどってLonely Runner Conjectureというのを見つけた. 詳細は以下. 長さ1のトラックがある. このトラックの上をk人のランナーr_1,...,r_kがスタート地点から一斉にそれぞれ一定の…

漸化式に落とせる点、好感度高し。ベータ関数とガンマ関数大活躍。 何回か書いた気がするが、未だに微積の単位は無い。ましてや実解析や複素解析なんて。