GAPの置換群の対称群における正規化群の計算では特別な関数が 用意されているが、それでも、次数が小さい場合でも困難な場合が ある。さらに、その関数が、かえって、困難を引き起こす場合がある。 このことを報告し、また、その改良の試みを報告する。筆者は2000年に、 群の作るアソシエーションスキームを利用して、次数の小さな場合の 困難な場合を解消した。この方法を部分的に適用したGAPプログラムの 少しの改変で計算時間に多少の改善が見られた。
有限群$G$とそのシロー$p$-部分群$S$の正規化群$N_G(S)$に対し，$G$と$S$の 既約指標の個数には，その次数に関してある関係が存在すると考えられて おり， それに関していくつかの予想が提出されている．その中でDade予想と呼ばれて いる予想に対し，それを指標の値まで含めて拡張した予想について考える． ここでは，この予想が成り立つ例として，いくつかの散在型単純群をあげる． 確認にはGAPを用いた．
The famous ATLAS of Finite Groups (henceforth called the ATLAS) by Conway et al.\ (Clarendon Press, 1984) contains, among a wealth of other useful information, the ordinary character tables of all sporadic simple groups and a large collection of interesting finite groups of Lie type. The ``Modular Atlas Project'' aims at computing the modular character tables of these ATLAS groups.
In a sequel to the ATLAS, An Atlas of Brauer Characters by Jansen et al. (Clarendon Press, 1995), the modular character tables of the ATLAS groups of order up to 10^9 have been published. Since then, many more tables have been completely or partially computed.
In this survey lecture I shall present the state of the art in the ``Modular Atlas Project''. Moreover, I shall explain the computational tools employed in computing modular character tables of large groups, in particular the MeatAxe and the Condensation. The latter is an enhancement of the MeatAxe based upon the idea of Morita equivalence. Condensation rises many theoretical and practical questions which will also be discussed in my talk, as well as the latest ideas and suggestions to overcome some of these difficulties.
The methods will be illustrated through the recently completed computation of the 2-modular character table of the sporadic simple Fischer group Fi_{23} by Neunhoffer, Noeske and myself.
$q$-シリーズ $f=\sum_{i=-1}^{\infty}a_iq^i, a_{-1}=1,a_0=0$ ただし $q=e^{2\pi iz}$ に対して、 Hecke多項式 $P_n(x)$ は次数 $n$ の多項式で条件 $P_n(f(z))=q^{-n}+(q$ の正のべきからなる項達$)$ を満たすものとして一意的に定義されます。モンスター群の各元 $g$ に対して, $f_g$ を定数項が $0$ となるThompsonシリーズ とします。ここでは、各 $g$ および全ての $n\leq 50$ に対して 多項式 $P_n(x)$ の零点を求め、かつ図示します。多くの場合には それらは全部実数になりますが、他の多くの場合にはそうならず、複素 平面上の面白い図を与えます。ここでの計算結果は、 浅井ー金子ー二宮(1997)による $P_n(x)$ の零点は $f_{1A}=j(z)-744$ に対して全て実数になる という結果の拡張と考えられます。
Let G be a finite group and \Phi_{n}(G) be the total number of distict n-tuples of elements of G. Then we denote P_{n}(G)=\frac{\Phi_{n}(G)}{|G|^n} as the probability that n randomly chosen elements of G generate G. It is known that when G is a finite non-abelian simple group, then P_{n}(G) tends to 1 as |G| tends to infinity. In this article, using the Group Algorithm Programming "GAP" and the conjugacy classes of maximal subgroups of G, we give a lower bound for P_{2}(G), where G is the projective special linear group PSL(m,q). In fact, we prove that:
Theorem. Let G=PSL(m,q) be a simple group with q \geq 2. Then (i) P_{2}(G)>4/7 if m=2, (ii) P_{2}>1/2 if m=3, (iii) P_{2}(G)>2/3 if m\geq 4.
We construct new linear two-weight codes over the finite field with q elements.
To do this we solve the equivalent problem of finding point sets in the projective geometry with certain intersection properties. These point sets are in bijection to solutions of a Diophantine linear system of equations. To reduce the size of the system of equations we restrict the search for solution to solutions with special symmetries. In several cases we found new distance-optimal two-weight codes.
長さ４４の ternary extremal self-dual code で 長さ４８の平方剰余符号から長さ４の ternary self-dual code を subtract して 得られるものを計算機を用いて分類した
n次元のkissing number とはn-1次元球面の周りに同じ大きさの球 を接触させていき、接触球たちは境界以外は 交わらないとする。このような接触球の最大 個数をkissing numberという。今までkissing numberは2,3,8,24次元のもののみ知られていたが、2003年にロシアの数学者Musinにより、4次元 のkissing number が決定された。この講演で Musinの4次元のkissing number の決定 の証明を紹介したい。
We consider tilings and packings of $\RR^d$ by integral translates of cubes $[0,2[^d$, which are $4\ZZ^d$-periodic. Such cube packings can be described by cliques of an associated graph, which allow us to classify them in dimension $d\leq 4$. For higher dimension, we use random methods for generating some examples.
Such a cube packing is called {\em non-extendible} if we cannot insert a cube in the complement of the packing.
In dimension 3, there is a unique non-extendible cube packing with 4 cubes. We prove that $d$-dimensional cube packings with more than $2^d-3$ cubes can be extended to cube tilings. We also give a lower bound on the number $N$ of cubes of non-extendible cube packings.
Given such a cube packing and $z\in \ZZ^d$, we denote by $N_z$ the number of cubes inside the $\4t$-cube $z+[0,4[^d$ and call {\em second moment} the average of $N_z^2$. We prove that the regular tiling by cubes has maximal second moment and give a lower bound on the second moment of a cube packing in terms of its density and dimension.
ユークリッド平面上で長さ k の辺を一つ固定する。その辺を含み 三辺の長さが i,j,k である三角形の個数は長さ k の辺の位置に よらず、i,j,k のみで決まる。この観点をグラフ上の距離に対して 考えたものが distance-regular graph である。2004年に E.van Dam, J. Koolen がある distance-regular graph を構成し、それが すでに知られている graph と distance-regular graph として 非常に似ているが非同型であることを示した。今回はこの二つの graph の局所構造について調べた結果を発表する。
コンピュータによる数学的構造の探索を 行うとき、 そのままではコンピュータの能力をはみだすことが多い。 ここでは2つのトピックスを取り上げて、対策を述べる。 これらの概念や原理は他の問題にも応用が期待できる。
＜ワーリング問題＞ 3乗和のワーリング問題について、 G(3) = 4 であろうという予測が80年代にコンピュータによって 得られている。ここで、ワーリング問題一般について2つの概念 「幹とスター原理」、「擬パラメトライザブル集合」を導入して考察 をする。
＜被覆系＞ 整数環の異なるモジュラスの合同類による被覆を 被覆系という。この構成のために 「一般フラクタル」、「セミローカル」 の概念を導入する。
42553 以下の自然数は合同数か否か、完全に分類されている。
今回、不定方程式 (1) 7^2*X^4-Y^4=6079*Z^2 の解として、
X=1011483919871 Y=2056657258885 Z=74121914867760454411676
が見つかったので、42553 は合同数となった。
(2) 877*X^4-4*Y^4=Z^2 はガウスの整数をつかって1984 年に解かれているが、ガウスの整数を使わずに(1)を解くアルゴリズムを適用し解く事ができる。
加法(連)鎖において 最小の長さをどのように求めるかは べき乗計算の最適化に関連して中心的な課題である。 この講演では2以上の自然数$p$に対し $p$-加法鎖を導入し、 $p=2$ の場合のいろいろな結果が$p$-加法鎖に適用すると どうなるのかいくつかの例を紹介する。特に「深さ優先アルゴリズム」 に必要な枝刈り条件についての拡張を紹介し、また $p=3$のときの小段階の少ない加法鎖の場合の計算結果も紹介したい。
準結晶の数理モデルである有名な cut-and-project集合 (以降、切断射影集合) に 対する任意のaffine変換は、切断射影集合の窓に対するaffine変換に対応すること を示した。
Pleasants(``Designer quasicrystals: cut-and-project sets with pre-assigned properties'', In: Directions in Mathematical Quasicrystals, ed. by M.Baake, R.V.Moody, 2000) は同様の切断射影集合の並進非対称性について論じているが、我々の定理により、 affine変換に関する非対称性についても考察でき、W.Parry のβ進貪欲展開の性質を 組み合わせることにより、Thurston-秋山タイル張りが恒等変換以外のaffine変換に ついて閉じていないことが示される。
ラムダ式はプログラムの理論的雛型であるが、 計算可能関数を学習の対象とする学習理論を 手本にして、ラムダ式を学習対象とする学習 理論の構築を試みた。Blum の抽象計算量を ラムダ式に導入し、計算可能関数を学習の対象と する学習理論における代表的な定理も、成立することを 示す。またラムダ式を学習対象とする学習理論の 応用の可能性についても論じる。
Algorithms for computer algebra systems have developed rapidly in recent decades. Nevertheless, user interfaces for these rich systems have hardly moved beyond the standard text shell. We present GiANT, a newly developed graphical interface for computer algebra. GiANT dynamically provides the user with typeset formulas, interactive diagrams, and drag-and-drop functionality. The result is an information-rich workspace that supports a new level of human- computer interaction.
Python による数論向け計算システム NZMATH は AC2003 での概要発表から今日 まで順調に開発が続いている。この2年間の開発の進展を振り返るとともに、開 発の中で見えてきた問題点や課題を整理し、この先2年間の開発の中期的展望を 述べる。
数論システムNZMATHに, 幾つかの重要な有限アーベル群を計算するアルゴリズ ムを実装した報告をする. 具体的には, 虚二次体の環類群, 有限素体上の楕 円曲線の有理点, および有限素体上の種数2の超楕円曲線のヤコビアンを計算 する. また実装に基づいたいくつかの実験結果を発表し, 今後の課題を明ら かにする.
Let $m$ be a square-free integer and let $\k$ be the quadratic field $\Q(\sqrt{m})$ with discriminant $d$. Denote the ring of integer of $\k$ by $\O_\k$. Two ideals $\mf{a}$ and $\mf{b}$ in $\O_\k$ are said to equivalent in the wide sense if and only if there exists an element $\alpha \in \k$ such that $\mf{a} = \alpha \mf{b}$. If we restrict the norm $N(\alpha)$ of the element $\alpha$ to be positive, then the ideals $\mf{a}$ and $\mf{b}$ are said to be equivalent in the narrow sense. Under these equivalence relations, the ideals of $\O_\k$ forms the abelian groups $H$ and $H^+$, known as the ideal class group of the quadratic field $K$ in the wide and in the narrow sense, respectively.
Approaches towards the understanding of these groups have involved almost all areas of mathematics ranging from reciprocity laws to class field theory and Iwasawa theory. In the hope of contributing towards the understanding of these groups, we present an algorithm for computing the Sylow 2-subgroups of $H$ and $H^+$ which is simpler than existing algorithms as it only requires understanding of techniques for solving quadratic diophantine equations $ax^2 +by^2 = z^2$ and $ax^2+2bxy+cy^2=z^2$. In comparisson with other existing algorithms, the algorithm to be presented works directly with ideals making it able to compute the wide sense case. We present some results obtained by implementing the algorithm.
The computation of Galois groups is the only problem out of Zassenhaus's four main problems in computational algebra that still has no general solution.
While substantial progress has been made in the recent years, computation of Galois groups of polynomials of degree up to 23 are now routinely done (using Magma), no degree-independent algorithm has been published so far.
In my talk I will explain what computational challenges need solving to remove the dependence on pre-computed data and report on recent advances in doing so.
指数計算法は2次篩法による整数の素因数分解や有限体上での 離散対数問題を解くために使われる手法である。これらは、ある確率でランダム にとって整数や、有限体の元が小さな素数の積で書かれることを利用してこれら の問題解法に使っている。種数gの超楕円曲線のヤコビアン群の離散対数問題 についても、Mumford表現されたヤコビアン群の元が1/g!の確率で、 定義体上の曲線の点の和で書かれることから、類似の解法がGaudryによってえられた。 この方法は、Harley, Th\'eriault, 筆者、Gaudry, Th\'eome, Diem等によって 改良がなされ、種数が3以上の場合には通常のρ法を使う解法より 計算量的には少ない方法で離散対数問題が解けることが知られている。 ここでは、特に二つのLarge Primeを使う改良について詳しく述べる。
(超)楕円曲線暗号では、Gallant-Lambert-Vanstone (GLV) 法 と呼ばれる高速スカラー倍算計算法が知られている。 本講演では、ある実乗法の効率的な計算法と そのような 実乗法を有する曲線へのGLV法の適用について述べる。 講演者の知る限りでは、高速スカラー倍算へ実乗法が 応用されたのは初めてである。
まず、上記の実乗法を用いたGLV法は、従来の虚数乗法を 用いた（種数2）GLV法と同程度に効率的であることを示す。 更に、虚数乗法を利用する従来曲線と比べて、 本講演の実乗法を有する曲線がより多く得られる ことも示す。
Crypto2000において，岡本・内山・田中の三氏が量子公開鍵暗号系(QPKC) を発表した．本講演では，数論システムNZMATH上でQPKCの核となる３つのプロ セス(鍵生成，復号化，暗号化)を実装する．
そして特に，鍵生成の効率性に関する計算機実験をいくつかの二次体の場合に ついて実行する．考察として，離散対数問題(量子暗号では多項式時間で 解決)以外のところでかかってしまうタイムロスについて考えてみる．
A {\em black-box} secret sharing scheme (BBSSS) for a given access structure works in exactly the same way over any finite Abelian group, as it only requires black-box access to group operations and to random group elements. In particular, there is no dependence on e.g.\ the structure of the group or its order. The expansion factor of a BBSSS is the length of a vector of shares (the number of group elements in it) divided by the number of players $n$. We will discuss BBSSS based on Shamir secret sharing over an integral extension. In particular, we will concentrate on a novel method based on {\em primitive sets in algebraic number fields}, thus exposing a new unexpected link between cryptology and number theory. This leads to a BBSSS with an expansion factor that is absolutely minimal up to an additive term of at most~2.
楕円曲線のセルマー群の大きさは、モーデル・ヴェイユ群の階数の上限を与える。 セルマー群は、伝統的には不定方程式の局所可解性を調べることによって計算される。
しかし、この方法では判別式の素因子の個数が増えるにしたがって計算が困難になる。 近年、セルマー群の大きさがあるグラフの性質と関係していることが報告されており、 その概要およびこの方面での考察の成果を報告する。
Quadratic Frobenius test は Lucas sequence $U_j(a,b)$ 等を用いた素数判定ストである. 従って合成数でありながら Frobenius test をパスするものが存在し, それは Frobenius 擬素数 ($fpsp(a,b)$) と呼ばれる. $(a,b)$ の選び方によってその密度が異なることが実験結果からわかっている. このことに関連して,ある性質を持つ合成数が必然的に $fpsp$ となってしまうような性質（条件）を bad dondition ($BD$) と名づける.
ここでは新たに見つけた $BD$ の場合にRSA 型の $fpsp$ が無限に多く存在することを示し, この場合を含む複数の $BD$を同時に回避するアイデアについて述べる.
本稿では，AC2003で筆者らが提案した署名者同一性検証可能グループ署名方式 のいくつかの注意点についての検討を行います．グループ署名は署名者の匿名 性を保証したディジタル署名方式であり，筆者らの提案した方式は，ヴェイユ ペアリングを用いて署名者同一性の検証を可能としたグループ署名方式でした． さらに，現在検討中の新しい署名方式のアイデアを紹介します．
ストリーム暗号CryptMTの紹介をする。この方式は、モンテカルロ法 用に設計された線形擬似乱数メルセンヌツイスターの出力を、 32ビット奇整数に変換した後、積算的に掛け算をして上位8ビットを暗号 乱数列として用いるものである。周期は2^{19937}-1で内部状態が 19937ビットであるため、状態の衝突を利用した攻撃に極めて耐性が強い。 また、最速版のAESによる擬似乱数生成より高速である。 抽象的に言えば、本方式は 「巨大周期を持つ高速だが非安全な擬似乱数 ＋メモリをもつシンプルなフィルター」 の一つの具体例である。
Hurwitz連分数とTasoev連分数は部分商の列が擬似周期のパターンをもつ正規 連分数である。現在までの研究では、部分商の周期の長さが高々４までのもの が構成されてきた。ここでは、あまり知られていないある種のアルゴリズムを 応用することにより、より長い周期をもつ連分数を体系的に簡単に得られるこ とを、いくつかの実例とともに示していく。
グレブナー基底は多項式環上のイデアルを扱うためにはもはや無くては ならない道具であり, その周辺概念に対する計算アルゴリズムの 多くも研究されてきた. 媒介変数を伴なうグレブナー基底(以下 CGB)もその一つである.
これまで CGB はその発表以来 Buchbergerのアルゴリズム の内部に媒介変数による条件分岐を加えたアルゴリズムにて 計算され, また実装もそれにそった形で改良されてきた. 我々は準素イデアル分解を用いる事で媒介変数による条件分岐を Buchbergerのアルゴリズムから分離する事に成功した. これによりCGBを計算するためのアルゴリズムは単純かつ高速となった.
現在使われている線形擬似乱数の中には、無視できない偏りを持って いるものがある。通常は統計的検定により偏りを検知するが、 松本-西村(2000)は符号理論のMacWilliams恒等式を使って、 二項分布からの偏りを計算するアルゴリズムを開発した。
本研究では、分離型MacWilliams恒等式を用いて、線形擬似乱数 によりコイン投げギャンブルを行ったとき、過去のコイン投げに おける表・裏の個数に基づいた最適の戦略を計算し、儲けの期待値を 求める方法を与え、複数の擬似乱数生成法について比較を行った。
手描き曲線のビットマップからほとんどランダムなビット列を抽出するアルゴリ ズムを示す．そのアルゴリズムが手描き曲線の不規則性を保存することを示すの が本講演の目的である．これを示すため，不規則な対象のセマンティクス（数学 的モデル）を与える．強制条件の最小サイズ，すなわち，forcing complexity に基づいてセマンティクスを構成する．フォーシングやトートロジーを使うのは あくまでもセマンティクスにおいてのみであり，アルゴリズムにおいてはこれら の概念を用いない．ランダムな対象についての既知のモデルよりも今回のセマン ティクスの方が本研究の目的にかなっていることを示す．実験結果も示す．
ゲーム木の分布的複雑さは、ランダム的複雑さ以下であること がYaoによって証明されている。本講演では、ゲーム木の分布的 複雑さがΩ(n^0.6942) であることを示し、さらに、分布的複雑 さに対応する分布確率が[0.5486, 0.6180] の範囲にあることを 証明する。最後に、ゲーム木のラスベガス複雑さとモンテカルロ 複雑さについても考察する。
一階の関数記号と明示的代入からなる言語は、ある関手による始代 数によって自然にモデル化できることを示す。ここで特徴的なこと は、明示的代入をKan拡張を用いて表現することができる点である。 また型なしλ計算に明示的代入を加えた場合でも、同様なモデル化 ができることを示す。さらにこれらの始代数によるモデル化は、抽 象構文を操作するような関数型プログラムにおいて有用な代数デー タ型を導くことを示す。最後に一階の言語に比べて、高階抽象構文 のモジュラー性の困難さについて説明する。
数学を計算機の上で記述するための枠組として講演者が開発しているシステム NF/CAL について解説する．人間の知的活動としての数学を言語行為として見 るとき，数学は計算と論理が重層的に用いられて記述されていることが観察さ れる．この観察にもとづいて，数学を記述するための枠組である NF (Natural Framework) を提案する．また NF を計算機上に実現するシステムである CAL (Computation and Logic) の解説とデモンストレーションを行う．話の中心は， そのようなシステムを開発することの哲学的意味，動機となる予定であり，ま た既存の類似のシステムとの相違についてもふれる．
$Date: 2005/10/31 11:31:01 $+ 9:00:00 (JST)