GAP has a special function to compute the normalizers of permutation groups in the symmetric groups. But still there exist difficult cases even though they are of small degree. Furthermore this function sometimes causes the difficulty. The author will report this fact and also reprot an attempt to improve this function. In 2000 the author fixed most of these difficult cases by using association schemes formed by the groups. By a slight modification of GAP program partly using this method the computing time was shortened to some extent.
Let G be an arbitrary finite group and S be a Sylow p-subgroup of G.
Here we think Dade's conjecture which concerning the number of irreducible characters of G and N_G(S), and we propose a strong form of this conjecture, which concerns character values.
We prove this extended conjecture for several sporadic simple groups.
For the calculations the GAP system is used.
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.
For a $q$-series $f=\sum_{i=-1}^{\infty}a_iq^i, a_{-1}=1,a_0=0$ with $ q=e^{2\pi iz},$ Hecke polynomial $P_n(x)$ is the unique polynomial of degree $n$ such that $P_n(f(z))=q^{-n}+($terms of positive powers in $q).$ For each element $g$ of the Monster, let $f_g$ be the Thompson series with constant term $0$.
We calculate the zeros of these polynomials $P_n(x)$ for all $g$ and for all $n\leq 50,$ and also describe them graphically. In some (many) cases all the zeros are real, while in some (many) other cases they are not all real and form interesting graphical pictures on the complex number plane. This generalizes the earlier work of Asai-Kaneko-Ninomiya (1997) that all the zeros of $P_n(x)$ are real for $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.
We classify the ternary extremal self-dual codes of length 44 obtained from the quadratic residue codes of length 48 by subtracting the unique self-dual code of length 4.
The kissing number in n dimensions is the maximum number of spheres with the same size to the fixed one sphere, which are kissing around the fixed one sphere and which do not intersect each other except for the boundary. Until quite recently, the determined kissing number, that is to say that, which has already been shown, were only ones in 2,3,8 and 24 dimensions. In 2003, Musin (Russian mathematician) determined the kissing number in 4 dimensions. In this talk, we would like to introduce about this Musin's work.
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.
In 2004, E.van Dam and J.Koolen constructed a distance-regular graph, which is a distance-regular graph with same parameter to the Grassmann graph`s one but is not isomorphic to the Grassmann graph. I talk about local eigenvalues and its multiplicities of the twisted Grassmann graph. To compute them, I used the action of automorphism groups on the direct set of the vertex set.
In search of mathematical structures using a computer, the task frequently overflows the capacity of the computer. Here I treat two topics, and propose devices to overcome the obstacles. Probably these devices work for other problems. < Waring's Problem > In 1980's, computational evidence of G(3) = 4 was given. For general Waring's Problems, I propose two concepts " Trunk & Star Principle" and "Quasi-parametrizable set". < Covering System > A covering system is a covering of the ring of integers by congruence classes of distinct moduli. To construct these for various moduli sets, I propose "General Fractal " and "semi-local".
A congruent number is a positive, square-free integer if it is the area of a right triangle with rational number sides. Equivalently, n is congruent if the elliptic curve y^2=x^3-n^2x has a point of infinite order, which is known to come from a non-trivial solution to one of a finite number of biquadratic Diophantine equations.
All congruent numbers less than 42553 are known. We have recently solved the Diophantine equation
One of the main topic in {addition chain} is to detect its minimum length. In this talk, we introduce ``$p$-addition chain'' for an integer $p\ge 2$ and see how analogous results in $p=2$ look like. Among them we obtain a pruning bound for $p$-addition chain. We also show a result with fewer {small steps} when $p=3$.
We prove that any affine transformation for a cut-and-project set, a famous mathematical model of quasicrystals, corresponds to an affine transformation for the window of the cut-and-project set.
Pleasants(``Designer quasicrystals: cut-and-project sets with pre-assigned properties'', In: Directions in Mathematical Quasicrystals, eds. by M.Baake and R.V.Moody, 2000) discusses the aperiodicity of cut-and-project sets, and by using our theorem we can discuss asymmetries w.r.t. affine transformations, too.
Combined by properties of W.Parry's greedy beta expansions, our theorem establishes that the Thurston-Akiyama tilings are not symmetric w.r.t. all affine transformations except the identity.
Aiming to apply computational learning theory to programming languages, we introduce a Blum's abstract complexity measure and the important complexity classes to the lambda-calculus, a foundational system of programming laguages. By it, we prove that properties typical to the computational learning theory also holds for the lambda-calculus.
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.
NZMATH, a number theory oriented calculation system based on Python, have been continuously developed for two years since the announcement of its outline at AC2003. We will summarise the two years of the development with problems and issues recognized through the experience, and will present a medium term future vision of development for the coming two years.
We report about implementation of algorithms to compute several important finite abelian groups on the system NZMATH for number theory. Precisely, we compute ring class groups of imaginary quadratic fields, rational points of elliptic curves over finite prime fields, Jacobians of hyperelliptic curves over finite prime fields. We also report some experimental results based on the implementation, and present our future subjects.
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.
Index calculus is tools for factorizing an integer by quadratic sieve method and solving DLP of a finite field. The idea of this method is that a randomly given integer or a randomly given element of a finite field is written by the products of small primes for some probability. For the DLP of the Jacobian group of a hyperelliptic curve of genus g, since the probability that an element of the Jacobian written by the Mumford representation being a sum of the points of the curve of definition field, is 1/g!, Gaudry gives the analogous algorithm. This algorithm is improved by Harley, Th\'eriault, the author, Gaudry and Th\'eome, Diem. When genus is bigger than 3, the complexity of solving DLP by this method is smaller than that of using rho-method which is often used. Here, we will talk about the idea that uses two large primes minutely.
The Gallant-Lambert-Vanstone (GLV) method is an efficient scalar multiplication method for (hyper-)elliptic curve cryptography.
In this talk, we show an efficient algorithm for some real multiplications (RM) on Jacobians of genus 2 curves. Then we discuss applications of the GLV method to the curves with the efficient RM.
It is the first time to use RM for efficient scalar multiplication as far as we know. We show that the genus 2 curves with RM have enough effciency to be used in the GLV method as in the previous CM case.
Moreover, we will see that such RM curves can be obtained abundantly unlike the previously proposed CM curves of genus 2.
Okamoto, Uchiyama and Tanaka announced quantum public key cryptosystem(QPKC) in Crypto2000. This talk is about the implementation of three processes namely, key generation, encoding and decoding of nucleus of QPKC on NZMATH.
In particular, I made some experiments about the efficiency of the characteristics of key generation in the case of some quadratic fields. Moreover, since the discrete logarithm problem is settled with a quantum computer by polynomial time, I only take into consideration the time loss when implementing this key generation.
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.
The cardinalities of Selmer groups of an elliptic curve gives an upper bound of the Mordell-Weil rank of the curve. A classical way to calculate the Selmer groups is to investigate the local solvability of certain equations. However, it is not easy when the discriminant of the curve has many prime factors. Recently, several mathematicians reported a relation between the cardinalities of Selmer groups and a property of certain graphs. In this talk, I would like to explain the outline of the theory and report certain results of this area.
The quadratic Frobenius test is a primality test using Lucas sequence with parameters $(a,b)$.
Composite numbers which pass through the Frobenius test with parameters $(a,b)$ are called Frobenius pseudoprimes with respect to $(a,b)$ ($fpsp(a,b)$ in short). Computational experiments suggest that the ratio of such $fpsp(a,b)$ seems heavily dependent on the parameters $(a,b)$.
There are conditions that every number satisfying some properties is a $fpsp(a,b)$, and such conditions are called "bad conditions".
In this talk, we show a new bad condition that there are infinitely many $fpsp$ of RSA form $pq$ satisfying it, and we discuss the choice of parameters $(a,b)$ to avoid bad conditions including the newly discovered one.
We introduce some notes of the linkable group signature scheme that we proposed at AC2003. The linkable group signature is the special class of group signature. In linkable group signature, it is possible to judge whether two different signatures are generated by the same member or not. We achieved the linkablitiy of our scheme by using the Weil Pairing. Moreover, we show some ideas of new digital signature schemes.
We propose a stream cipher CryptMT. This method is to convert the output integer sequence of Mersenne Twister random number generator, by taking accumlative products and by taking the most significant 8 bits by masking, into a cryptographic pseudorandom number sequence.
Its period is proved to be 2^{19937}-1 and its internal state consists of 19937 bits, and hence it is tough against the attacks based on the collision of the states. Implementation shows that this method is much faster than the optimized version of AES pseudorandom number generator.
Abstractly saying, this method is one of the examples of "huge period, fast but not cryptographically secure pseudorandom sequence + a simple filter with memory."
Hurwitz and Tasoev continued fractions are regular continued fractions with a quasi-periodic pattern on the sequence of partial quotients. In previous works in this context the author obtained closed forms for the value of continued fractions of this type where the length of period was at most $4$. Here a new method is developed yielding results with longer period.
We usually use Groebner basis as one of tools to manuplate ideals in certain polynomial ring and related algebraic structures, and so many algorithms to compute them have been developed.
In this talk, we are going to talk about comprehensive Groebner bases (CGB), kinds of parametric Groebner bases. Most algorithms for CGB are defined as extensions of the Buchberger's algorithms by embedding computations of case-distinctions on parameters.
On the other hand, we successfully unmerge the computations of case-distinctions from the Buchberger's algorithm, using primary ideal decompositions. It makes our algorithm for CGB simple, and furthermore faster in many cases.
Some pseudorandom number generators (PRNGs) with linear recursion have non-negligible deviation from the randomness. Usually, statistical tests are conducted to detect such deviation. Matsumoto-Nishimura (2000) introduced an algorithm to compute the deviation from the binomial distribution using MacWilliams' Identity.
This study uses the splitting version of MacWilliams' identity to obtain the best strategy for a coin-tossing gambling based on some linear PRNGs, and the expected gained money. The strategy depends only on the number of the heads in the past. Several PRNGs are compared using this methods.
We present an algorithm that converts a set of bitmaps of freehand drawings to an almost random bit sequence. The goal of this talk is to show that our algorithm preserves irregularity of freehand drawings, by giving semantics (mathematical model) of irregular objects. Our semantics is based on forcing complexity, that is, the minimum size of a forcing condition. We use forcing and tautologies only for semantics. Our algorithm does not utilize these concepts. We show that our model is more suitable for our purpose than known models of random objects. We show experimental results, too.
Andrew C-C. Yao has shown that the distributional complexity of game trees is not greater than the randomized complexity. In this talk, we show that the distributional complexity is Ω(n^0.6942), and that the corresponding distributional probability is in the range [0.5486, 0.6180]. Finally, we discuss the Las Vegas and Monte Carlo complexities of game trees.
We show that a language containing explicit substitutions and a first-order signature is naturally modelled as the initial algebra of a certain endofunctor. An interesting point of this modelling is that explicit substitutions are expressed as a Kan extension. We derive a similar formula for adding explicit substitutions to the untyped lambda-calculus and then show these initial algebras provide useful datatypes for manipulating abstract syntax. We also comment on the apparent lack of modularity in syntax with variable binding as compared to first-order languages.
We will give an overview of a computer environment NF/CAL which we are developing as a framework for "doing" mathematics on a computer. If one look at mathematicians activities as linguistic acts, we can observe that mathematics is described by using computation and logic in a mutually dependent way. Based on this observation, we have been proposing a framework called NF (Natural Framework) for describing mathematics in it. We will also present and give a demonstration of a computer environment CAL (Computation and Logic) which realizes NF on a computer. We will mainly talk about the motivation and philosophical meaning of developing such a system, and we will also compare our approach with other competing systems.
$Date: 2005/11/13 13:08:50 $+ 9:00:00 (JST)