_ プレプリント確認状況：arXiv:math 7月31日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/044まで
_ （2/5記：SCIS2012最終日、なのだが、雪の影響で交通機関に運休や遅れが続発し、会場で足止めをくらってもう一泊する羽目になる参加者が何人も出てしまったらしい。私は何とか帰ってこられたが、それでも予定より２時間ぐらい遅くなってしまった。）
_ （2/6記：宿泊出張の翌日に朝早く（注：本人比）から打ち合わせという無謀（注：本人比）なスケジュールだったが、出張の時差ぼけ（注：研究集会期間中に午前中から発表があるため規則正しい起床時間になること）の後遺症で遅刻せずに済んだ。）
_ プレプリント確認状況：arXiv:math 8月3日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/048まで
_ "prisoners and hats puzzle"と呼ばれているらしい問題を某所で知った。曰く、
無限の人数の囚人たちがそれぞれ赤か白の帽子を被らされ、各々は自分の被っている帽子を見ることはできないが、他の囚人の帽子の色は全て把握することができるとする。囚人たちは、帽子を被らされる前には互いに相談が可能だが、帽子を被った後には互いに相談できない。この状況で、囚人たちが一斉に自分の被った帽子の色を答えて、間違えた人数が有限であれば囚人たちの勝ちとなる。さて、どのように帽子を被らされたとしても必ず囚人たちが勝てるような戦略は存在するだろうか？詳細は上のリンク先などにあるので省くけれども、選択公理を仮定すると（囚人の集合の濃度の如何に関わらず）必勝法の存在を示すことができる。さて、ではこのゲームの必勝法の存在は選択公理と同値だろうか？私は答えを知らないので、後で考えてみたい。
_ プレプリント確認状況：arXiv:math 8月10日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/056まで
_ ↑上のarXivチェックでThe Probability that a Pair of Elements of a Finite Group are Conjugate
（arXiv:1108.1784）という論文を見つけた。曰く、
Let \(G\) be a finite group, and let \(\kappa(G)\) be the probability that elements \(g\), \(h\in G\) are conjugate, when \(g\) and \(h\) are chosen independently and uniformly at random. The paper classifies those groups \(G\) such that \(\kappa(G) \geq 1/4\), and shows that \(G\) is abelian whenever \(\kappa(G)|G| < 7/4\). It is also shown that \(\kappa(G)|G|\) depends only on the isoclinism class of \(G\). Specialising to the symmetric group \(S_n\), the paper shows that \(\kappa(S_n) \leq C/n^2\) for an explicitly determined constant \(C\). This bound leads to an elementary proof of a result of Flajolet \emph{et al}, that \(\kappa(S_n) \sim A/n^2\) as \(n\rightarrow \infty\) for some constant \(A\). The same techniques provide analogous results for \(\rho(S_n)\), the probability that two elements of the symmetric group have conjugates that commute.対称群のネタを見るとCoxeter群に一般化できるか気になってしまう病なので今回も例に漏れずということなのだが、具体的に何か面白いことができるかどうかは知らない。
_ プレプリント確認状況：arXiv:math 8月16日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/056まで
_ ↑今日のarXivチェックで気になった論文：Palindromic richness and Coxeter groups
（arXiv:1108.3042）
For a given finite group \(G\) consisting of morphisms and antimorphisms of a free monoid \(\mathcal{A}^*\), we study infinite words with language closed under the group \(G\). We focus on words rich in generalized palindromic factors, i.e., in factors \(w\) satisfying \(\Theta(w) = w\) for some non-identical element \(\Theta \in G\). We give several equivalent descriptions of rich words and show the role Coxeter groups play in the generalized notion of palindromic richness.論文中の議論においてCoxeter群が役立ってるらしいのだが、まだ中身を読んでいないのでどう役立っているのかはわからない。
_ プレプリント確認状況：arXiv:math 8月30日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/056まで
_ （2/11記：妻と一緒に「ジュエルズ」というバレエのDVDを鑑賞した。
私は今まで（少なくともクラシックバレエでは）物語風のバレエしか観たことがなかったのだが、この作品は物語風の筋書きがあるというわけではなく、純粋に音楽を表現するものとなっている（多分）。で、観て感じたこととして、今までに観た他のバレエ作品（まぁ、そんなに多くの作品を観たわけではないのだけど…）と比べて、ダンサーの動きの拍子が早く、激しい。普段のバレエ作品が陸上競技の長距離走だとしたら、この作品からは（時間が短めなこともあり）中距離走を思わせる印象を受けた。個人的には、今まで知らなかったバレエの新たな魅力を教えてもらった気持ちがしている。）
_ Twitterで教えてもらった「エミール・ゾラの肖像」という絵画。
_ プレプリント確認状況：arXiv:math 9月4日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/061まで
_ （2/13記：「数学セミナー」３月号のエレガント欄第２問が面白かった。問題自体も面白かったし、問題の背景が想像できる場合には記号の選び方一つにも出題者の意図を感じる事ができてまた面白い。自分の出題のときもあれくらい面白い問題を出題できたらなぁ。）
_ プレプリント確認状況：arXiv:math 9月6日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/061まで
_ arXivよりGroups of Order 2048 with Three Generators and Three Relations
（Shirin Fouladi, Reza Orfi, arXiv:1109.0754）
It is shown that there are exactly seventy-eight 3-generator 2- groups of order 2^11 with trivial Schur multiplier. We then give 3-generator, 3-relation presentations for forty-eight of them proving that these groups have deficiency zero.なぜ2048なんだろう…
_ プレプリント確認状況：arXiv:math 9月6日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/064まで
_ IACR ePrintの2012/064の表題が（少なくとも、これを書いている時点では）Ron was wrong, Whit is right
となっているのだけど、論文の内容の推測し易さを無視して見掛け上のキャッチーさだけを追究した悪い表題の見本だと思う。どうしてあっちの分野にはそういう表題を付けたがる人が多いんだろう。
_ ↑よく考えると「なまけもの暗号」や「エンターテイメントセキュリティ」だってよくわからないといえばわからない表題なのだが、そちらは悪い表題だと思わなかったなぁ。一体どこに境目があるのだろう。
_ とある事情で複数ファイルの画像を並べて一つの画像ファイルとして繋げ合わせる必要が生じたのでそれができるソフトを探したところ、ImageMergeというソフトが使いやすかった（Windows 7の環境）のでメモ。
_ プレプリント確認状況：arXiv:math 9月11日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/064まで
_ プレプリント確認状況：arXiv:math 9月13日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/064まで
_ さっき見つけた論文：Isomorphism versus commensurability for a class of finitely presented groups
（Goulnara Arzhantseva, Jean-Francois Lafont, Ashot Minasyan, arXiv:1109.2225）
We construct a class of finitely presented groups where the isomorphism problem is solvable but the commensurability problem is unsolvable. Conversely, we construct a class of finitely presented groups within which the commensurability problem is solvable but the isomorphism problem is unsolvable. These are first examples of such a contrastive complexity behaviour with respect to the isomorphism problem.
_ プレプリント確認状況：arXiv:math 9月19日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/064まで
_ さっき見つけた「入試問題に解答うっかり明記…名古屋市立大ミス」という記事について。
名古屋市立大（名古屋市瑞穂区）は１７日、今月４日に実施した大学院人間文化研究科博士前期課程の入学試験の「英語」で出題ミスがあり、受験した４人全員を正解として得点を与える措置を取ったと発表した。問題が簡単すぎたという点で間違いなく出題ミスなのだろうけど、通常の出題ミス（正解が存在しない、問題が曖昧で正解が定まらない、など）と違って問題を解こうとした受験者が不利になる類のミスではないと思うので、別に特別措置は必要なかったんじゃないかなぁ…。
発表によると、出題ミスがあったのは、長文を読ませて適切なタイトルを選択する問題。解答が問題の下に明記してあったという。
（2012年2月18日16時42分 読売新聞）
_ プレプリント確認状況：arXiv:math 9月21日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/064まで
_ プレプリント確認状況：arXiv:math 9月25日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/064まで
_ 一昨日入った飲食店で、店員さんに外国人と間違われたらしく、しばらく英語で話しかけられていた。そのときはしばらく思案した挙句日本人であることを伝えて一件落着したのだが、今までにも何度か似た経験をしたので、これからは店員さんの気遣いを無にしないために英語で通すか、もしくは片言の日本語でも練習しておいた方がよいのだろうか。（←間違った気遣いの例）
_ ↑今日も出張先の大学職員さんから１回、懇親会会場の店員さんから１回英語で話しかけられた。国際化が進んだ街なのだ、と解釈しておく。
_ （2/25記：日本数学会のウェブサイトに「「大学生数学基本調査」に基づく数学教育への提言」という文章が掲載されていた。後で何か書くかもしれないけど、とりあえずメモのみ。）
_ 昨日書いた日本数学会「「大学生数学基本調査」に基づく数学教育への提言」の件について感じたことをいくつか。
問1-1(2)は「ある中学校の三年生の生徒100人の身長を測り、その平均を計算すると163.5cmになりました。」という前提から「100人の生徒全員の身長をたすと、163.5cm×100=16350cmになる。」が「確実に正しいと言える」かどうか判定する問題である。正解は「○」なのだが、有効数字の扱いを気にして「×」と答えることがあり得るのではないかという指摘をTwitterで目にした（確かに、現実世界で100人の身長の（誤差を含む）計測値の平均が163.5cmになったとしても、身長の真の値の和がその100倍になるとは限らない。「身長の真の値」という概念が気持ち悪いとしても、仮に100人を横にして直列繋ぎにして全長を（元々の計測値と同じ精度で）測定したとしたら結果が元の平均値の100倍になるとは限らない）。「平均」の概念の無理解に基づく誤答と、このように有効数字まで考慮した「考えすぎの誤答」は、同じ誤答だとしても明らかに性質が異なる。両者の切り分けを行うためにも、問2-1だけでなくこの問題も記述式（理由を書く欄を設ける）にしたらよかったのではないかなと思う。
問題2-2は、ある具体的な2次関数が提示され、「…のグラフは、どのような放物線でしょうか。重要な特徴を、文章で3つ答えてください。」という問題である。私は（「3つ」ではなく「三つ」だろう、という点は置いといて）「重要な特徴」という表現に引っ掛かりを覚えたのだが、添付文書の「大学生数学基本調査報告書（FAQ）」に関連する項目があったので引用してみる。
Ｑ１１．問２－２について，グラフの「重要な特徴」という，価値観を問うようなたずね方は不適切なのではありませんか？「本調査は，成績や進路に関係するものではありません．ですから，設問の妥当性は調査目的に合致しているかどうかによって判断されるべきだと考えます」という点には同意するものの、それでもやはり問題の「重要な特徴」という表現が適切であったかどうか疑問が残る。何故なら、一つの2次関数が持つ性質のうちどの性質が重要であるかは状況に依存するからである。（例えば、2次関数をShamirの秘密分散法に応用する場合、指定したいくつかのx座標における放物線上のy座標の値が何であるかという性質こそが重要であり、放物線の頂点の位置はどうでもいい性質である。）というわけで、「どのような観点から」重要な特徴を答えるべきかをもっと明確にした方が望ましかったと思う。回答者の無用な混乱を避ける問題文を作成することは、「調査目的」にとっても有益なことだと思うのだが。
Ａ１１．本調査は，成績や進路に関係するものではありません．ですから，設問の妥当性は調査目的に合致しているかどうかによって判断されるべきだと考えます．「個別の操作（計算等）は比較的よくできるが，その操作の意味がわかっていない・考えない大学生が増えた」という意見が，これまで日本数学会会員から多数寄せられてきました．そこで，「できる」と「わかる」の乖離を調べるために，あえてこのような設問を設定しました．本設問では，二次関数に関して学ぶ操作（例：x軸やy軸との交点を求める，頂点の座標を求める，等）がどのような意味を持つかを理解しているかを調査しています．これにより，二次関数のイメージが根本からずれてしまっている層や，自分が受けた印象と客観的であるべき特徴との違いを認識できていない層が存在し，また，それが無視できないほど大きな割合になることが明らかになりました．
_ プレプリント確認状況：arXiv:math 9月28日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/096まで
_ IACR ePrintで気になった論文２編。まずはPublic Key Cryptosystems Constructed Based on Reed-Solomon Codes, K(XV)SE(2)PKC, Realizing Coding Rate of Exactly 1.0
（Masao KASAHARA, 2012/079）
In this paper, we present a new class of public-key cryptosystems, K(XV)SE(2)PKC realizing the coding rate of exactly 1.0, based on Reed-Solomon codes(RS codes). We show that K(XV)SE(2)PKC is secure against the various attacks including the attacks based on the Gröbner basis calculaｔion (Gröbner basis attack, GB attack) and a linear transformation attack.
もう一つは、Collision Bounds for the Additive Pollard Rho Algorithm for Solving Discrete Logarithms
（Joppe W. Bos and Alina Dudeanu and Dimitar Jetchev, 2012/087）
We prove collision bounds for the Pollard rho algorithm to solve the discrete logarithm problem in a general cyclic group $G$. Unlike the setting studied by Kim et al. we consider additive walks: the setting used in practice to solve the elliptic curve discrete logarithm problem. Our bounds differ from the birthday bound $O(\sqrt{|G|})$ by a factor of $\sqrt{\log{|G|}}$ and are based on mixing time estimates for random walks on finite abelian groups due to Hildebrand.
_ プレプリント確認状況：arXiv:math 10月2日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/096まで
_ 見つけた論文：The ElGamal cryptosystem over circulant matrices
（Ayan Mahalanobis, arXiv:1109.6416）
Can one use the discrete logarithm problem in matrix groups, to build a better and secure cryptosystem? We argue, it is indeed the case. This makes the group of circulant matrices suitable and attractive for lightweight cryptography.
（追記：IACR ePrintにも同じ論文が上がっていた。ちなみに中身はまだ読んでいない。）
_ ↑ざっと読んでみたが、Theorem 1（暗号方式の一方向性が考えている群上のDH問題と等価だと主張している定理）の証明が怪しいように見えてしまう。本当に大丈夫なんだろうか。
_ ついでに見つけた別の論文：Homomorphic encryption from codes
（Andrej Bogdanov and Chin Ho Lee, IACR ePrint 2011/622）。
Abstract: We propose a new homomorphic encryption scheme based on the hardness of decoding under independent random noise from certain affine families of codes. Unlike in previous lattice-based homomorphic encryption schemes, where the message is hidden in the noisy part of the ciphertext, our scheme carries the message in the affine part of the transformation and applies noise only to achieve security. Our scheme can tolerate noise of arbitrary magnitude, as long as the noise vector has sufficiently small hamming weight (and its entries are independent).
Our design achieves "proto-homomorphic" properties in an elementary manner: message addition and multiplication are emulated by pointwise addition and multiplication of the ciphertext vectors. Moreover, the extremely simple nature of our decryption makes the scheme easily amenable to bootstrapping. However, some complications are caused by the inherent presence of noticeable encryption error. Our main technical contribution is the development of two new techniques for handling this error in the homomorphic evaluation process.
We also provide a definitional framework for homomorphic encryption that may be useful elsewhere.
STOC 2012の採録論文リストに同じ名前と同じ著者の論文があったので、それのプレプリント版ということなのだろう。
1-1 カードが100枚あり、それぞれ1から9までの整数のどれかが書かれています。カードに書かれた数字の平均を計算すると、ちょうど5になりました。この結果から確実に正しいといえることには○を、そうでないものには×を記入し、そう考えた理由を下の空欄で説明して下さい。（記入欄は省略。以下同様。）そこまで精読していないので誤字などはご容赦ください（ご指摘いただければ直します）。
(1) 数字が5より小さいカードと5より大きいカードは同じ枚数だけある。
(2) カード100枚の数字の合計は、5 × 100 = 500 に等しい。
(3) カード100枚を、書かれた数字によって「1か2か3」「4か5か6」「7か8か9」の三つの組に分けると、「4か5か6」の組のカードが最も多い。
1-2 次の報告から確実に正しいといえることには○を、そうでないものには×を記入して下さい。（追記）また、そう考えた理由を空欄で説明して下さい。（追記終わり）
「教室の中の男の子たちと女の子たちが、それぞれ前か後ろを向いて座っています。後ろを向いている子供はみんな女の子です。そして、本を読んでいる男の子は一人もいません。」
(1) 男の子はみんな前を向いている。
(2) 前を向いている女の子はいない。
(3) 前を向いていて、しかも本を読んでいる子供は、一人もいない。
2-1 偶数と奇数を一つずつたすと、答えはどうなるかを考えます。
(1) 偶数や奇数とはどのような数でしょうか。それぞれ、定義を空欄に記入して下さい。
(2) 偶数と奇数を一つずつたすと、答えはどうなるでしょうか。次の選択肢のうち正しいものに○を記入し、そうなる理由を空欄で説明して下さい。
(a) いつも必ず偶数になる。
(b) いつも必ず奇数になる。
(c) 偶数になることも奇数になることもある。
2-2 2次関数 $y = -x^2 + 6x - 8$ のグラフを、なるべくその形や位置関係がわかりやすいように描くとしたら、あなたはこのグラフのどのような特徴に注目して図を描きますか。その特徴を三つ答えて下さい。
3 右の図の線分を、正確に3等分したいと思います。定規（直線を引くのに使います）とコンパス（円を描くのに使います）を使ってそのような作図をする手順を、箇条書きにしてわかりやすく説明して下さい。ただし、図形の実際の長さや幅などを測ってはいけません。なお、説明に図を使う場合は、正確でなくても大まかな形を描くだけでかまいません。
_ プレプリント確認状況：arXiv:math 10月4日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/096まで
_ プレプリント確認状況：arXiv:math 10月4日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/102まで
最近のツッコミ↓