MarriageTheoremのこと

_ プレプリント確認状況：arXiv:math 10月6日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/113まで

_ メモ：Mapping classes associated to mixed-sign Coxeter graphs（Eriko Hironaka, arXiv:1110.1013）

Given an ordered fat graph with labeled vertices we define a generalized Coxeter system, and Coxeter element. We then construct an associated mapping class with the property that its image under the symplectic homomorphism is conjugate to the negative of the Coxeter element. Applying a result of Lanneau and Thiffeault, we show that the minimum dilatations for orientable mapping classes for surfaces of small genus can be realized by mapping classes of this form.

_ （3/3記：先日の北大への出張では、日本人の発表者に日本語で質問したにもかかわらずその人から休み時間に英語で話しかけられる事案と、キャンパス内で近道しようと思ったら膝丈まで雪に埋もれた上に頭上からカラスに襲われかける事案が発生した。）

_ プレプリント確認状況：arXiv:math 10月13日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/113まで

_ 先日とある理由で、ブロックソート圧縮法（でいいのかな、正式名称は知らない）の原理について教わったらかなり面白かった。参考までに解説文書へのリンクを張っておく。

_ ふと思い立って「数学女子」で検索していたらこんなものを見つけた。何だこれは。

_ プレプリント確認状況：arXiv:math 10月20日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/120まで

_ プレプリント確認状況：arXiv:math 11月1日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/120まで

_ 中身は読んでいないけれども一応メモ。On some quasigroup cryptographical primitives（Piroska Csorgo, Victor Shcherbacov, arXiv:1110.6591）

We propose modifications of known quasigroup based stream ciphers. Systems of orthogonal n-ary groupoids are used.

_ 折角なので、一昨日の日記で言及したブロックソート法についての備忘録を記しておく。

ある与えられた文字列 $w$（例えば、141421356）を以下の要領で並び替える。まず、$w$ から出発し、各文字を左に1桁ずつずらして新しい文字列を作っていき（一番左の文字は右端に移る）、$w$ 自身を含めて$w$ の長さと同じ個数の文字列を作り、行列状に並べる（例では

$$\begin{matrix}1&4&1&4&2&1&3&5&6\\4&1&4&2&1&3&5&6&1\\1&4&2&1&3&5&6&1&4\\4&2&1&3&5&6&1&4&1\\2&1&3&5&6&1&4&1&4\\1&3&5&6&1&4&1&4&2\\3&5&6&1&4&1&4&2&1\\5&6&1&4&1&4&2&1&3\\6&1&4&1&4&2&1&3&5\end{matrix}$$

となる）。こうしてできる行列を $X_1$ と書く。次に $X_1$ の行を辞書式順序に従って並び替える（例では

$$\begin{matrix}1&3&5&6&1&4&1&4&2\\1&4&1&4&2&1&3&5&6\\1&4&2&1&3&5&6&1&4\\2&1&3&5&6&1&4&1&4\\3&5&6&1&4&1&4&2&1\\4&1&4&2&1&3&5&6&1\\4&2&1&3&5&6&1&4&1\\5&6&1&4&1&4&2&1&3\\6&1&4&1&4&2&1&3&5\end{matrix}$$

となる）。この結果を $X_2$ と書く。このとき、行列 $X_2$ の左から何列かを取り出してできる部分行列の行たちもまた辞書式順序で並んでいる（＊）という事実が（辞書式順序の定義から当たり前なのだが）実は後で効いてくる。そして、$X_2$ の一番右の列を上から順に読んでできる文字列 $w'$ を並び替えの結果とする（例では 264411135 となる）。

構成法から、 $X_1$（従って $X_2$）の一番右の列はもとの文字列 $w$ を並び替えたものとなっている。この並び替えた結果 $w'$ からもとの文字列 $w$ を復元してみよう。その方法を考えるために、行列 $X_2$ の右側に自身の複製を並べてみる：

$$\begin{matrix}1&3&5&6&1&4&1&4&2&|&1&3&5&6&1&4&1&4&2\\1&4&1&4&2&1&3&5&6&|&1&4&1&4&2&1&3&5&6\\1&4&2&1&3&5&6&1&4&|&1&4&2&1&3&5&6&1&4\\2&1&3&5&6&1&4&1&4&|&2&1&3&5&6&1&4&1&4\\3&5&6&1&4&1&4&2&1&|&3&5&6&1&4&1&4&2&1\\4&1&4&2&1&3&5&6&1&|&4&1&4&2&1&3&5&6&1\\4&2&1&3&5&6&1&4&1&|&4&2&1&3&5&6&1&4&1\\5&6&1&4&1&4&2&1&3&|&5&6&1&4&1&4&2&1&3\\6&1&4&1&4&2&1&3&5&|&6&1&4&1&4&2&1&3&5\end{matrix}$$

さて、 $X_1$ の各行は先頭行（つまり $w$）を左に一つずつずらしていってできたものなので、各 $k$ について「$X_1$ の各行について、左から $k$ 文字を抜き出した文字列」全体の集合と「$X_1$ の各行について、一番右の文字の後に左から $k-1$ 文字めまでを繋げた文字列」全体の集合は重複度を込めて一致する。よって、その行を並び替えた $X_2$ についても同じ性質が成り立つ。換言すると、上記のように二つ並んだ $X_2$ において、境界（「|」）部分の左隣の1列と右隣の $k-1$ 列を抜き出してできる行列 $Y_k$ の各行からなる集合と、$X_2$ の左から $k$ 列を抜き出してできる行列 $Z_k$ の各行からなる集合は重複度を込めて一致する。すると、性質（＊）より $Z_k$ の行たちは辞書式順序で並んでいるので、 $Y_k$ の行たちを辞書式順序で並べると $Z_k$ が得られる。そのため、$X_2$ の一番右の列であるところの $w'$ を辞書順に並べると $Z_1$ が得られ、その左列に $w'$ を並べると $Y_2$ が得られ、その行を辞書順に並べると $Z_2$ が得られ、その左列に $w'$ を…と繰り返していくことで、$w'$ から出発して行列 $X_2$ を復元できることがわかる。

ただし、$w$ を左側にいくつかずらしてできる別の文字列 $u$ から出発しても行列 $X_2$ は同じものになるので、$X_2$ を復元できても $w$ 自身を一意に復元できるとは限らない。その点を解決するためには、予め文字列 $w$ の末尾に文字列の終わりを表す特殊文字（実用上は、例えばファイルの終端文字EOFなど）を付け加えておけばよい。そうすれば、$X_2$ の行のうち、一番右にその特殊文字が現れている唯一の行がもとの $w$ と確定する。上の例では、「6」が終端文字のような立場であり、実際 $X_2$ の行で一番右が6であるものが文字列 $w$ となっている。

というわけで、変換後の文字列 $w'$ から変換前の（末尾に目印を持つ）文字列 $w$ を復元できることがわかった。そして、特定のパターンの繰り返しが頻繁に生じる文字列（例えば、単語単位の繰り返しからなる自然言語の文章はこの性質を満たす）をこの方法で変換すると、変換後の文字列には同じ文字が連続するブロックが多く含まれるようになり、圧縮アルゴリズムの効率を向上させることができる、という塩梅らしい。まこと面白い仕組みであるなぁ。

_ プレプリント確認状況：arXiv:math 11月6日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/120まで

_ プレプリント確認状況：arXiv:math 11月10日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/120まで

_ プレプリント確認状況：arXiv:math 11月13日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/120まで

_ 何時間かぶっ続けでひたすら計算していたら手首が痛くなった。

_ Twitterでmath26さんから教えていただいたのだが、情報処理学会論文誌に掲載されている「体系的探索による裸玉詰将棋問題の創作」という論文の参考文献として、私が15年ほど前に某詰将棋雑誌の読者コーナーに投稿した文章が引用されていることを知って驚いた。よくもまぁ件の論文の筆者はあんなマニアックな文章を探し出してきたものだ。（この話を知った時点では最近の論文なのかと勘違いし、「15年も前の某雑誌の読者コーナーなんてどうやって探したんだろう」と驚嘆したのだが、さっき見返してみたら論文の発表年は2000年だったので、当時からすると3年前の文章だったことになる。とはいえ3年前の読者コーナーだって相当見つけにくいことには違いないが。）

ちなみに、私の記憶が確かなら（そもそも件の文章の存在をすっかり忘れていたぐらいなので、これは相当怪しい仮定なのだが）、あの文章には数学的にはあまり大したことは書かなかったと思うのだが、それでもこうして参考文献として参照していただけるというのは嬉しいものである。

_ プレプリント確認状況：arXiv:math 11月15日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/120まで

_ 気になった（けれども読んでいない）論文：Balanced $0,1$-words and the Galois group of $(x+1)^n-λx^p$（Lev Glebsky, arXiv:1111.2870）

We study the number of $0,1$-words where the fraction of 0 is "almost" fixed for any initial subword. It turns out that this study use and reveal the structure of the Galois group (the monodromy group) of the polynomials $(x+1)^n-\lambda x^p$. ($p$ is not necessary a prime here.)

_ プレプリント確認状況：arXiv:math 11月20日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/120まで

_ 積読状態の論文が増えていてあまり良くない傾向である。

_ ここ数日取り組んでいた計算について、最初に導入した近似が粗すぎたせいで結果が使い物にならないことがさっき判明して軽く頭が痛い件。さてどうしたものか…。

_ プレプリント確認状況：arXiv:math 11月22日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/120まで

_ 昨日書いた計算の件は、別の方針でどうにかなるかもしれない気がしてきた。

_ 先日から話題になっている、はてながはてなブックマークボタンでユーザの行動情報を取得している件（参考情報としては例えばこのあたり）があり、はてなダイアリーの方の記事をこちらに移す予定の優先度が上昇した。

_ プレプリント確認状況：arXiv:math 12月6日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/120まで

_ 気になった論文：The absolute order of a permutation representation of a Coxeter group（Christos A. Athanasiadis, Yuval Roichman, arXiv:1112.0856）

A permutation representation of a Coxeter group $W$ naturally defines an absolute order. This family of partial orders (which includes the absolute order on $W$) is introduced and studied in this paper. Conditions under which the associated rank generating polynomial divides the rank generating polynomial of the absolute order on $W$ are investigated when $W$ is finite. Several examples, including a symmetric group action on perfect matchings, are discussed. As an application, a well-behaved absolute order on the alternating subgroup of $W$ is defined.

第１著者は以前Coxeter hyperplane arrangement（A型だけだったかもしれない）関連の論文を書いていたのだけど、今回の話もそういう方面と関連があるのだろうか。（と思うなら論文を読んでみればよいのだが…。）

_ プレプリント確認状況：arXiv:math 12月8日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/120まで

_ プレプリント確認状況：arXiv:math 12月20日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/130まで

_ 3/14（ホワイトデー）を分数（14分の3）だと思って小数にしてみると、およそ0.214（より詳しくは0.2142857142857…）となってバレンタインデー（2月14日）が現れるということに気が付いた。

_ プレプリント確認状況：arXiv:math 1月4日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/130まで

_ ↑ついにarXiv:mathのチェック状況が2012年に追い付いた。感慨深い。

_ 気になった論文その１：Asymptotical behaviour of roots of infinite Coxeter groups I（Christophe Hohlweg, Jean-Philippe Labbé, Vivien Ripoll, arXiv:1112.5415v1）

Let W be an infinite Coxeter group. We initiate the study of the set E of limit points of "normalized" positive roots (representing the directions of the roots) of W. We show that E is contained in the isotropic cone of the bilinear form B associated to a geometric representation, and illustrate this property with numerous examples and pictures in rank 3 and 4. We also define a natural geometric action of W on E, and then we exhibit a countable subset of E, formed by limit points for the dihedral reflection subgroups of W. We explain that this subset can be built from the intersection with Q of the lines passing through two positive roots, and we establish that it is dense in E.

その２：Alternating subgroups of Coxeter groups and their spinor extensions（O. V. Ogievetsky, L. Poulain d'Andecy, arXiv:1112.6347v1）

Let $G$ be a discrete Coxeter group, $G^+$ its alternating subgroup and $\tilde{G}^+$ the spinor cover of $G^+$. A presentation of the groups $G^+$ and $\tilde{G}^+$ is proved for an arbitrary Coxeter system $(G,S)$; the generators are related to edges of the Coxeter graph. Results of the Coxeter--Todd algorithm - with this presentation - for the chains of alternating groups of types A, B and D are given.

分野にMathematical Physicsが入っているのが気になる。どんな応用がある話なんだろうか。

その３：On counterexamples in questions of unique determination of convex bodies（Dmitry Ryabogin, Vlad Yaskin, arXiv:1201.0544v1）

We discuss a construction that gives counterexamples to various questions of unique determination of convex bodies.

_ 昨日書いた3/14と.214の話を妻に話したら好評だった。ああいう話を面白がってくれる人でよかったなぁと思う。

_ （3/19記：某勉強会と某フォーラムをはしごしたのだが、両者の雰囲気の違いが感じられて興味深かった。）

_ （3/19記：休日。ものすごい勢いで眠った気がする。）

_ （3/19記：休日。久々に気分転換できた気がする。）

_ プレプリント確認状況：arXiv:math 1月10日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/130まで

_ 気になった論文：A Statement in Combinatorics that is Independent of ZFC (an exposition)（Stephen Fenner, William Gasarch, arXiv:1201.1207v1）

It is known that, for any finite coloring of the naturals, there exists distinct naturals $e_1,e_2,e_3,e_4$ that are the same color such that $e_1+e_2=e_3+e_4$. Consider the following statement which we denote S: For every $\aleph_0$-coloring of the reals there exists distinct reals $e_1,e_2,e_3,e_4$ such that $e_1+e_2=e_3+e_4$?} Is it true? Erdos showed that S is equivalent to the negation of the Continuum Hypothesis, and hence S is indepedent of ZFC. We give an exposition of his proof and some modern observations about results of this sort.

エルデシュが証明したと書いてあるけど、エルデシュ＝角谷の定理とかいう定理と関係する話なのかなぁ。

_ プレプリント確認状況：arXiv:math 1月12日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/130まで

_ 気になった論文：The Number of Group Homomorphisms from $D_m$ into $D_n$（Jeremiah Johnson, arXiv:1201.2363v3）

Counting homomorphisms between cyclic groups is a common exercise in a first course in abstract algebra. A similar problem, accessible at the same level, is to count the number of group homomorphisms from a dihedral group of order $2m$ into a dihedral group of order $2n$. While the solution requires only elementary group theory, the result does not appear in the literature or in the usual texts. As the solution may be of interest, particularly to those teaching undergraduate abstract algebra, it is provided in this note.

学部の代数学の演習問題のネタに、ということらしい。例によって（と堂々と書いている場合ではないが…）中身は読んでいないのだが、二面体群というよりCoxeter群として考えても面白そうだなぁと思った。

_ ↑というか、ひょっとするとCoxeter群で似たような論文があるんじゃないかなぁ（心当たりがあるわけではないが）。

_ 職場に私の居場所がない（居室が引っ越し作業中で机が使えない的な意味で）ためお休み中。

_ プレプリント確認状況：arXiv:math 1月16日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/134まで

_ 2012年度の気になる研究集会リスト（仮）

そろそろ来年度の計画を立てた方がよさそうだと気付いたので、来年度の研究集会を物色中。（参考：RIMS研究集会リスト）なお、あくまで「気になる研究集会リスト（仮）」なので、ここに挙がっているからといって必ず参加するわけでもなければ、挙がっていない研究集会に参加する可能性もある。あと、多分後で更新されると思う。

・5月

5/10-11「CSEC研究会」＠秋田大学

5/18「ISEC研究会」＠機械振興会館

・6月

6/21「神田・公開鍵暗号ワークショップ」＠インターネットイニシアティブ（IIJ）本社

・7月

7/9-11「Third Workshop on Mathematical Cryptology (WMC 2012)」＠CIEM-Castro Urdiales, Spain

7/19-20「ISEC-CSEC等合同研究会」＠北海道工業大学

7/23-27「凸多面体論の最近の潮流を探る」＠RIMS

・8月

8/20-23「代数学シンポジウム」＠RIMS

8/28-31「組合せ論サマースクール2012」＠島根県松江市

・9月

9/12-14「証明論と複雑性」＠RIMS

9/21「ISEC研究会」＠機械振興会館

・10月

10/9-12「組合せ論的表現論とその周辺」＠RIMS

10/23-25「次世代計算科学の基盤技術とその展開」＠RIMS

10/30-11/1「CSS 2012」＠くにびきメッセ：島根県立産業交流会館

・11月

11/7-9「IWSEC 2012」＠西新プラザ（福岡）

11/23-25「数学基礎論若手の会2012」＠奈良県青少年会館

・12月

12/4-7「強制法による拡大と巨大基数」＠RIMS

12/11-14「SITA 2012」＠大分県 別府湾ロイヤルホテル

12/14「CSEC研究会」＠未定

12/26「CRISMATH 2012」＠未定

・1月

1/9-12「ITCS 2013 Innovations in Theoretical Computer Science」＠Berkeley, California

1/22-25「SCIS 2013」＠ウェスティン都ホテル京都

1/28-30「理論計算機科学の新展開」＠RIMS

・2月

2/18-20「代数とコンピュータサイエンス」＠RIMS

2/26-3/1「PKC 2013」＠奈良

・3月

3/3-6「TCC 2013」＠東大

3/4-7「第９回数学総合若手研究集会（MCYR9）」＠北大

3/14-15「CSEC研究会」＠東京電機大学

_ プレプリント確認状況：arXiv:math 1月17日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/147まで

_ 気になった論文：Somewhat Practical Fully Homomorphic Encryption（Junfeng Fan and Frederik Vercauteren, IACR ePrint 2012/144）

In this paper we port Brakerski's fully homomorphic scheme based on the Learning With Errors (LWE) problem to the ring-LWE setting. We introduce two optimised versions of relinearisation that not only result in a smaller relinearisation key, but also faster computations. We provide a detailed, but simple analysis of the various homomorphic operations, such as multiplication, relinearisation and bootstrapping, and derive tight worst case bounds on the noise caused by these operations. The analysis of the bootstrapping step is greatly simplified by using a modulus switching trick. Finally, we derive concrete parameters for which the scheme provides a given level of security and becomes fully homomorphic.

somewhat practicalと（タイトルで）言っているけれどもどのくらい効率化されたのだろうか。

_ プレプリント確認状況：arXiv:math 1月17日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/151まで

_ プレプリント確認状況：arXiv:math 1月17日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/158まで

_ プレプリント確認状況：arXiv:math 1月22日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/158まで

_ プレプリント確認状況：arXiv:math 1月24日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/158まで

_ プレプリント確認状況：arXiv:math 1月29日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/158まで

_ 昨日読んだ「知られざる大学教員の実態」というブログ記事の内容を是非多くの方に知っていただきたい。勿論その人の環境に応じて個人差はあるだろうけど、端的に言って想像以上の激務である。自分がこれと同じ状況に置かれたら早々にぶっ倒れる自信がある。にもかかわらず教員のポストは増えるどころか減る傾向にあるというのが恐ろしい話なのだが、ポストを増やすのが難しいとしてもせめて教員の負担を減らすためにワークシェアリングぐらいはできないものだろうか？ワークシェアリングの概念を真っ先に実装すべきは（高校までも含めた）教員の世界だと強く思う。一時期「ゆとり教育」なるものが喧伝されていたけれども、良い教育を行うために真に必要なのは、生徒（学生）よりもむしろ教員の側のゆとりであると思わされる。

_ プレプリント確認状況：arXiv:math 1月29日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/161まで

_ プレプリント確認状況：arXiv:math 1月29日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/164まで

_ 気になった論文：On Secure Two-party Integer Division（Morten Dahl, Chao Ning, Tomas Toft, IACR ePrint 2012/164）

We consider the problem of {\it secure integer division}: given two Paillier encryptions of $\ell$-bit values $n$ and $d$, determine an encryption of \intdiv{n}{d} without leaking any information about $n$ or $d$. We propose two new protocols solving this problem.

The first requires $\Oh(\ell)$ arithmetic operation on encrypted values (secure addition and multiplication) in $\Oh(1)$ rounds. This is the most efficient constant-rounds solution to date. The second protocol requires only $\Oh \left( (\log^2 \ell)(\kappa + \loglog \ell) \right)$ arithmetic operations in $\Oh(\log^2 \ell)$ rounds, where $\kappa$ is a correctness parameter. Theoretically, this is the most efficient solution to date as all previous solutions have required $\Omega(\ell)$ operations. Indeed, the fact that an $o(\ell)$ solution is possible at all is highly surprising.

_ プレプリント確認状況：arXiv:math 1月31日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/164まで

_ プレプリント確認状況：arXiv:math 1月31日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/168まで

_ 気になった論文：A Distinguisher-Based Attack of a Homomorphic Encryption Scheme Relying on Reed-Solomon Codes（Val\'erie Gauthier and Ayoub Otmani and Jean-Pierre Tillich, IACR ePrint 2012/168）

Bogdanov and Lee suggested a homomorphic public-key encryption scheme based on error correcting codes. The underlying public code is a modified Reed-Solomon code obtained from inserting a zero submatrix in the Vandermonde generating matrix defining it. The columns that define this submatrix are kept secret and form a set $L$. We give here a distinguisher that detects if one or several columns belong to $L$ or not. This distinguisher is obtained by considering the code generated by component-wise products of codewords of the public code (the so called ``square code''). This operation is applied to punctured versions of this square code obtained by picking a subset $I$ of the whole set of columns. It turns out that the dimension of the punctured square code is directly related to the cardinality of the intersection of $I$ with $L$. This allows an attack which recovers the full set $L$ and which can then decrypt any ciphertext.

まだ中身をちゃんと読んでいないのだが、以前の日記で紹介した、STOC 2012に採録された符号ベース準同型暗号方式に対する攻撃のようである。STOC 2012自体はまだ開催されていないのだが、開催に先駆けて論文がプレプリントサーバで公表され、それに対する攻撃がやはりSTOC 2012本番前に公表され、それを受けてかSTOC 2012の採録論文リストから当該論文が削除される*1という中々趣深い事態になっている*2。昔の暗号系の学会では、新しい暗号方式の提案に関する発表の最中に聴講者が提案方式を破ってしまうという光景も見られたらしい*3が、それに比べると発表前に気付けるだけ進歩した状況なのだろうか。