Distribution of matrices with restricted entries over finite fields

For a prime p, we consider some natural classes of matrices over a finite field F_p of p elements, such as matrices of given rank or with characteristic polynomial having irreducible divisors of prescribed degrees. We demonstrate two different techniques which allow us to show that the number of such matrices in each of these classes and also with components in a given subinterval [-H, H] [-(p - 1)/2, (p - 1)/2] is asymptotically close to the expected value.     

Quadratic equations over finite fields and class numbers of real quadratic fields

Letp be an odd prime and the finite field withp elements. In the present paper we shall investigate the number of points of certain quadratic hypersurfaces in the vector space and derive explicit formulas for them. In addition, we shall show that the class number of the real quadratic field (wherep1 (mod 4)) over the field of rational numbers can be expressed by means of these formulas.     

Graph colourings with forbidden k-coloured subgraphs

Abstract

For a set F of graphs and a natural number k, an (F, k)-colouring of a graph G is a proper colouring of V (G) such that no subgraph of G isomorphic to an element of F is coloured with at most k colours. Equivalently, if P is the class of all graphs that do not contain an element of F as a subgraph, a χP,k colouring of G is a proper colouring such that the union of at most k colour classes induces a graph in P. The smallest number of colours in such a colouring of G, if it exists, is denoted by χP,k (G). We give some general results on χP,k-colourings and investigate values of χP,k (G) for some choices of P and classes of graphs G.     

Orthogonal representations over finite fields and the chromatic number of graphs

We study the relationship between the minimum dimension of an orthogonal representation of a graph over a finite field and the chromatic number of its complement. It turns out that for some classes of matrices defined by a graph the 3-colorability problem is equivalent to deciding whether the class defined by the graph contains a matrix of rank 3 or not. This implies the NP-hardness of determining the minimum rank of a matrix in such a class. Finally we give for any class of matrices defined by a graph that is interesting in this respect a reduction of the 3-colorability problem to the problem of deciding whether or not this class contains a matrix of rank equal to three.The author is financially supported by the Cooperation Centre Tilburg and Eindhoven Universities.     

Planar functions over finite fields

Letp>2 be a prime. A functionf: GF(p)GF(p) is planar if for everyaGF(p) ^*, the functionf(x+a–f(x) is a permutation ofGF(p). Our main result is that every planar function is a quadratic polynomial. As a consequence we derive the following characterization of desarguesian planes of prime order. IfP is a protective plane of prime orderp admitting a collineation group of orderp ², thenP is the Galois planePG(2,p). The study of such collineation groups and planar functions was initiated by Dembowski and Ostrom [3] and our results are generalizations of some results of Johnson [8].We have recently learned that results equivalent to ours have simultaneously been obtained by Y. Hiramine and D. Gluck.     

Topology of dynamical systems in finite groups and number theory

We study and develop a very new object introduced by V.I. Arnold: a monad is a triple consisting of a finite set, a map from that finite set to itself and the monad graph which is the directed graph whose vertices are the elements of the finite set and whose arrows lead each vertex to its image (by the map). We consider the case in which the finite set entering in the monad definition is a finite group G and the map is the Frobenius map, for some k∈Z. We study the Frobenius dynamical system defined by the iteration of the monad fk, and also study the combinatorics and topology (i.e., the discrete invariants) of the monad graph. Our study provides useful information about several structures on the group associated to the monad graph. So, for example, several properties of the quadratic residues of finite commutative groups can be obtained in terms of the graph of the Frobenius monad .     

An application of Fourier transforms on finite Abelian groups to an enumeration arising from the Josephus problem

Text

We analyze an enumeration associated with the Josephus problem by applying a Fourier transform to a multivariate generating function. This yields a formula for the enumeration that reduces to a simple expression under a condition we call local prime abundance. Under this widely held condition, we prove (Corollary 3.4) that the proportion of Josephus permutations in the symmetric group Sn that map t to k (independent of the choice of t and k) is 1/n. Local prime abundance is intimately connected with a well-known result of S.S. Pillai, which we exploit for the purpose of determining when it holds and when it fails to hold. We pursue the first case where it fails, reducing an intractable DFT computation of the enumeration to a tractable one. A resulting computation shows that the enumeration is nontrivial for this case.

Video

For a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=DnZi-Znuk-A.     

List edge colourings of some 1-factorable multigraphs

The List Edge Colouring Conjecture asserts that, given any multigraphG with chromatic indexk and any set system {S _e :eE(G)} with each |S _e |=k, we can choose elementss _e S _e such thats _e s _f whenevere andf are adjacent edges. Using a technique of Alon and Tarsi which involves the graph monomial of an oriented graph, we verify this conjecture for certain families of 1-factorable multigraphs, including 1-factorable planar graphs.Supported by the University Research Council of Vanderbilt University and NSERC Canada grants A5414 and A5499.Supported by NSERC Canada grant A5499     

Cyclotomic units over finite fields

Let ζ be a primitivesp-th root of unity for a primep>2, and consider the group Ω(ζ) of cyclotomic units in the ringR(ζ)=ℒ[ζ+ζ^-1]. This paper deals with the image of Ω(ζ) in the unit group ofR(ζ)/qR(ζ), whereq is a prime ≠p. In particular, it obtains criteria for this image to be essentially everything, and a lower bound on the density of primesp (withq fixed) for which it cannot be. These results have a direct bearing on previous work about units in integral group rings for cyclic groups of orderpq. Work supported in part by an operating grant from NSERC (Canada).     

Uniformly defining valuation rings in Henselian valued fields with finite or pseudo-finite residue fields

We give a definition, in the ring language, of _Zp${\mathbb{Z}}_p$ inside _Qp${\mathbb{Q}}_p$ and of _Fp[[t]]${\mathbb{F}}_p[[t]]$ inside _Fp((t))${\mathbb{F}}_p((t))$, which works uniformly for all p   and all finite field extensions of these fields, and in many other Henselian valued fields as well. The formula can be taken existential-universal in the ring language, and in fact existential in a modification of the language of Macintyre. Furthermore, we show the negative result that in the language of rings there does not exist a uniform definition by an existential formula and neither by a universal formula for the valuation rings of all the finite extensions of a given Henselian valued field. We also show that there is no existential formula of the ring language defining _Zp${\mathbb{Z}}_p$ inside _Qp${\mathbb{Q}}_p$ uniformly for all p  . For any fixed finite extension of _Qp${\mathbb{Q}}_p$, we give an existential formula and a universal formula in the ring language which define the valuation ring.     

Polynomials over ordered fields

In this paper we determine which polynomials over ordered fields have multiples with nonnegative coefficients and also which polynomials can be written as quotients of two polynomials with nonnegative coefficients. This problem is related to a result given by Pólya in [G.H. Hardy, J.E. Littlewood, G. Pólya, Inequalities, Cambridge University Press, Cambridge, England, 1952] (as a companion of Artin’s theorem) that asserts that if F(X₁,…,X_n)∈R[X₁,…,X_n] is a form (i.e., a homogeneous polynomial) s.t.  with ∑x_j>0, then F=G/H, where G,H are forms with all coefficients positive (i.e., every monomial of degree degG or degH appears in G or H, resp., with a coefficient that is strictly positive). In Pólya’s proof H is chosen to be H=(X₁+?+X_n)^m for some m.At the end we give some applications, including a generalization of Pólya’s result to arbitrary ordered fields.     

Inequalities for solutions of singular initial problems for Carathéodory systems via Ważewski’s principle

In this paper we give sufficient conditions for solvability of a singular initial problem formulated for Carathéodory systems of ordinary differential equations. The existence of solutions is proved by the supposition that corresponding auxiliary lower and upper singular problems have solutions. The proof technique uses a notion of a regular polyfacial subset which is developed for Carathéodory systems of ordinary differential equations and a modification of the topological method for such systems given by Palamides, Sficas and Staikos. An application concerning the existence of positive solutions for a special class of singular problems is given as well.     

List Colouring When The Chromatic Number Is Close To the Order Of The Graph

Ohba has conjectured [7] that if G has 2 (G)+1 or fewer vertices then the list chromatic number and chromatic number of G are equal. In this short note we prove the weaker version of the conjecture obtained by replacing 2 (G)+1 by * This research was partially supported by DIMACS and by CNRS/NSF collaboration grant. Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey.     

Graph homomorphisms and nodal domains

In this paper, we derive some necessary spectral conditions for the existence of graph homomorphisms in which we also consider some parameters related to the corresponding eigenspaces such as nodal domains. In this approach, we consider the combinatorial Laplacian and co-Laplacian as well as the adjacency matrix. Also, we present some applications in graph decompositions where we prove a general version of Fisher’s inequality for G-designs.     

On the stability and boundedness of solutions of nonlinear vector differential equations of third order

In this paper, by using Liapunov’s second method, we establish some new results for stability and boundedness of solutions of nonlinear vector differential equations of third order. By constructing a Liapunov function, sufficient conditions for stability and boundedness of solutions of equations considered are obtained. Concerning to the subject, some explanatory examples are also given. Our results improve and include a result existing in the literature.     

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.     

Simultaneous solutions to diagonal equations over finite fields

An elementary proof of the Weil conjectures is given for the special case of a non-singular pair of diagonal equations over a finite field. The number of simultaneous solutions to an arbitrary number of diagonal equations over GF(q) is also estimated by the same classical methods.