Deciding finiteness for matrix semigroups over function fields over finite fields

We present a deterministic polynomial time algorithm for testing finiteness of a semigroupS generated by matrices with entries from function fields of constant transcendence degree over finite fields. A special case of the problem was shown to be algorithmically soluble in [RTB] by giving a sharp exponential upper bound on the dimension of the matrix algebra generated byS over the field of constants. One of the exponential time algorithms proposed in [RTB] was expected to be improvable. The polynomial time method presented in this note combines the ideas of that algorithm with a procedure from [IRSz] for calculating the radical. Research supported by NWO-OTKA Grant N26673, FKFP Grant 0612/1997, OTKA Grants 016503, 022925, and EC Grant ALTEC-KIT.     

Functional graphs of rational maps induced by endomorphisms of ordinary elliptic curves over finite fields

In this paper we study the dynamics of rational maps induced by endomorphisms of ordinary elliptic curves defined over finite fields. For any such map we describe the cycle and the tree structures of the associated graphs.     

Lifting endomorphisms of formal A-modules over finite fields

Lubin conjectures that for an invertible series to commute with a noninvertible series with only simple roots of iterates, two such commuting power series must be endomorphisms of a single formal group. In this paper, we show that if the reduction of these two commuting power series are endomorphisms of a formal group, then themselves are endomorphisms of a formal group.     

Iterations of linear maps over finite fields

We study the dynamics of the evolution of Ducci sequences and the Martin-Odlyzko-Wolfram cellular automaton by iterating their respective linear maps on . After a review of an algebraic characterization of cycle lengths, we deduce the relationship between the maximal cycle lengths of these two maps from a simple connection between them. For n odd, we establish a conjugacy relationship that provides a more direct identification of their dynamics. We give an alternate, geometric proof of the maximal cycle length relationship, based on this conjugacy and a symmetry property. We show that the cyclic dynamics of both maps in dimension 2n can be deduced from their periodic behavior in dimension n. This link is generalized to a larger class of maps. With restrictions shared by both maps, we obtain a formula for the number of vectors in dimension 2n belonging to a cycle of length q that expresses this number in terms of the analogous values in dimension n.     

The fundamental group of period domains over finite fields

We determine the fundamental group of period domains over finite fields. This answers a question of M. Rapoport raised in [M. Rapoport, Period domains over finite and local fields, in: Proc. Sympos. Pure Math., vol. 62, part 1, 1997, pp. 361-381].     

The residual finiteness of negatively curved polygons of finite groups

A subgroup M⊂G is almost malnormal provided that for each g∈G−M, the intersection M ^g ∩M is finite. It is proven that the free product of two virtually free groups amalgamating a finitely generated almost malnormal subgroup, is residually finite. A consequence of a generalization of this result is that an acute-angled n-gon of finite groups is residually finite if n≥4. Another consequence is that if G acts properly discontinuously and cocompactly on a 2-dimensional hyperbolic building whose chambers have acute angles and at least 4 sides, then G is residually finite. Oblatum 17-VII-2000 & 13-II-2002?Published online: 29 April 2002     

Polynomial functions over finite monoids

This paper is a completion of [7]; we characterize the monoids (S,.,e) such that the algebra (P(n,S), o_n) of polynomial functions over S is congruence free.     

Mapping tori of endomorphisms of free groups

For al large class of endomorphisms of finitely generated free groups we prove that their mapping tori groups are word-hyperbolic if and only if they don’t contain Baumslag-Solitar subgroups.     

Deciding finiteness for matrix groups over function fields

LetF be a field andt an indeterminate. In this paper we consider aspects of the problem of deciding if a finitely generated subgroup of GL(n,F(t)) is finite. WhenF is a number field, the analysis may be easily reduced to deciding finiteness for subgroups of GL(n,F), for which the results of [1] can be applied. WhenF is a finite field, the situation is more subtle. In this case our main results are a structure theorem generalizing a theorem of Weil and upper bounds on the size of a finite subgroup generated by a fixed number of generators with examples of constructions almost achieving the bounds. We use these results to then give exponential deterministic algorithms for deciding finiteness as well as some preliminary results towards more efficient randomized algorithms. Supported in part by NSF DMS Awards 9404275 and Presidential Faculty Fellowship.     

On the construction of irreducible polynomials over finite fields via odd prime degree endomorphisms of elliptic curves

In this paper we present an iterative construction of irreducible polynomials over finite fields based on repeated applications of transforms induced by endomorphisms of odd prime degree of ordinary elliptic curves.     

有限域上矩阵环的幂映射图

对于一个环或者是乘法群H和一个正整数k,我们可以定义一个有向图G(H,k),称为H上的k次幂映射图.它的顶点集合就是H,并且从a到b有一条有向边当且仅当b=ak.交换环或者交换群上的k次幂映射图一般具有较好的对称性,这方面已经有相当多的结果.本文研究有限域上二阶矩阵环的k次幂映射图,利用线性代数和群论的方法,克服了非交换性带来的困难,得到了这类图的顶点入度的分布和圈长的分布.