Wedderburn polynomials over division rings, I

A Wedderburn polynomial over a division ring K is a minimal polynomial of an algebraic subset of K. Such a polynomial is always a product of linear factors over K, although not every product of linear polynomials is a Wedderburn polynomial. In this paper, we establish various properties and characterizations of Wedderburn polynomials over K, and show that these polynomials form a complete modular lattice that is dual to the lattice of full algebraic subsets of K. Throughout the paper, we work in the general setting of an Ore skew polynomial ring K[t,S,D], where S is an endomorphism of K and D is an S-derivation on K.     

Continued fractions for certain algebraic power series

Let F be an arbitrary field and let K = F((x⁻¹)) be the field of formal Laurent series in x⁻¹ over F. The usual theory of continued fractions carries over to K, with the polynomials in x playing the role of the integers. We study the continued fraction expansions of elements of K which are algebraic over F(x), the field of rational functions of x.We give the first explicit expansions of algebraic elements of degree greater than 2 for which the degrees of the partial quotients are bounded. In particular we give explicitly the continued fraction expansion for the solution f in K of the cubic equation xf³ + f + x = 0 when F = GF(2). This cubic was studied by Baum and Sweet. We give examples, for every field F of characteristic greater than 2, of algebraic elements of degree greater than 2 whose partial quotients are all linear, and we give these expansions explicitly. These are the first known examples with partial quotients of bounded degree when F has characteristic greater than 2.     

On the expressive power of CNF formulas of bounded tree- and clique-width

We study representations of polynomials over a field K from the point of view of their expressive power. Three important examples for the paper are polynomials arising as permanents of bounded tree-width matrices, polynomials given via arithmetic formulas, and families of so called CNF polynomials. The latter arise in a canonical way from families of Boolean formulas in conjunctive normal form. To each such CNF formula there is a canonically attached incidence graph. Of particular interest to us are CNF polynomials arising from formulas with an incidence graph of bounded tree- or clique-width.We show that the class of polynomials arising from families of polynomial size CNF formulas of bounded tree-width is the same as those represented by polynomial size arithmetic formulas, or permanents of bounded tree-width matrices of polynomial size. Then, applying arguments from communication complexity we show that general permanent polynomials cannot be expressed by CNF polynomials of bounded tree-width. We give a similar result in the case where the clique-width of the incidence graph is bounded, but for this we need to rely on the widely believed complexity theoretic assumption #P?FP/poly.     

Recurrent Methods for Constructing Irreducible Polynomials over GF(2s)

The paper is devoted to some results concerning the constructive theory of the synthesis of irreducible polynomials over Galois fields GF(q), q=2^s. New methods for the construction of irreducible polynomials of higher degree over GF(q) from a given one are worked out. The complexity of calculations does not exceed O(n³) single operations, where n denotes the degree of the given irreducible polynomial. Furthermore, a recurrent method for constructing irreducible (including self-reciprocal) polynomials over finite fields of even characteristic is proposed.     

Elementary Abelianp-extensions of algebraic function fields

LetK be a field of characteristicp>0 andF/K be an algebraic function field. We obtain several results on Galois extensionsE/F with an elementary Abelian Galois group of orderp ⁿ.

1. E can be generated overF by some elementy whose minimal polynomial has the specific formT ^pn?T?z.
2. A formula for the genus ofE is given.
3. IfK is finite, then the genus ofE grows much faster than the number of rational points (as [E∶F] → ∞).
4. We present a new example of a function fieldE/K whose gap numbers are nonclassical.

     

Cube root Ramanujan formulas and elementary Galois theory

The cube root Ramanujan formulas are explained from the point of view of Galois theory. Let F be a cyclic cubic extension of a field K. It is proved that the normal closure over K of a pure cubic extension of F contains a certain pure cubic extension of K. The proposed proof can be generalized to radicals of any prime degree q. In the case where the base field K is the field of rational numbers and the field F is embedded in the cyclotomic extension obtained by adding the pth roots of unity, the corresponding simple radical extension of the field of rational numbers is explicitly constructed. The proof of the main result illustrates Hilbert’s Theorem 90. An example of a particular formula generalizing Ramanujan’s formulas for degree 5 is given. A necessary condition for nested radical expressions of depth 2 to be contained in the normal closure of a pure cubic extension of the field F is given.     

Newton stratification for polynomials: The open stratum

In this paper we consider the Newton polygons of L-functions coming from additive exponential sums associated to a polynomial over a finite field Fq. These polygons define a stratification of the space of polynomials of fixed degree. We determine the open stratum: we give the generic Newton polygon for polynomials of degree d?2 when the characteristic p?3d, and the Hasse polynomial over Fp, i.e. the equation defining the hypersurface complementary to the open stratum.     

Every place admits local uniformization in a finite extension of the function field

We prove that every place P of an algebraic function field F|K of arbitrary characteristic admits local uniformization in a finite extension F of F. We show that F|F can be chosen to be Galois, after a finite purely inseparable extension of the ground field K. Instead of being Galois, the extension can also be chosen such that the induced extension FP|FP of the residue fields is purely inseparable and the value group of F only gets divided by the residue characteristic. If F lies in the completion of an Abhyankar place, then no extension of F is needed. Our proofs are based solely on valuation theoretical theorems, which are of particular importance in positive characteristic. They are also applicable when working over a subring R⊂K and yield similar results if R is regular and of dimension smaller than 3.     

Standard identities for skew-symmetric matrices

Let n be a positive, even integer and let K_n(F) denote the subspace of skew-symmetric matrices of Mn(F), the full matrix algebra with coefficients in a field F. A theorem of Kostant states that K_n(F) satisfies the (2n-2)-fold standard identity s_2n-2. In this paper we refine this result by showing that s_2n-2 may be written non-trivially as the sum of two polynomial identities of K_n(F).     

On local Galois representations associated to ordinary Hilbert modular forms

Let F be a totally real field and p be an odd prime which splits completely in F. We show that a generic p-ordinary non-CM primitive Hilbert modular cuspidal eigenform over F of parallel weight two or more must have a locally non-split p-adic Galois representation, at at least one of the primes of F lying above p. This is proved under some technical assumptions on the global residual Galois representation. We also indicate how to extend our results to nearly ordinary families and forms of non-parallel weight.     

Graph polynomials from principal pivoting

The recursive computation of the interlace polynomial introduced by Arratia, Bollobás and Sorkin is defined in terms of a new pivoting operation on undirected simple graphs. In this paper, we interpret the new pivoting operation on graphs in terms of standard pivoting (on matrices). Specifically, we show that, up to swapping vertex labels, Arratia et al.'s pivoting operation on a graph is equivalent to a principal pivot transform on the graph's adjacency matrix, provided that all computations are performed in the Galois field F₂. Principal pivoting on adjacency matrices over F₂ has a natural counterpart on isotropic systems. Thus, our view of the interlace polynomial is closely related to the one by Aigner and van der Holst.The observations that adjacency matrices of undirected simple graphs are skew-symmetric in F₂ and that principal pivoting preserves skew-symmetry in all fields suggest to extend Arratia et al.'s pivoting operation to fields other than F₂. Thus, the interlace polynomial extends to polynomials on gain graphs, namely bidirected edge-weighted graphs whereby reversed edges carry non-zero weights that differ only by their sign. Extending a proof by Aigner and van der Holst, we show that the extended interlace polynomial can be represented in a non-recursive form analogous to the non-recursive form of the original interlace polynomial, i.e., the Martin polynomial.For infinite fields it is shown that the extended interlace polynomial does not depend on the (non-zero) gains, as long as they obey a non-singularity condition. These gain graphs are all supported by a single undirected simple graph. Thus, a new graph polynomial is defined for undirected simple graphs. The recursive computation of the new polynomial can be done such that all ends of the recursion correspond to independent sets. Moreover, its degree equals the independence number. However, the new graph polynomial is different from the independence polynomial.     

On a generalization of the Euler totient function

For a general polynomial Euler product F(s) we define the associated Euler totient function φ(n, F) and study its asymptotic properties. We prove that for F(s) belonging to certain subclass of the Selberg class of L-functions, the error term in the asymptotic formula for the sum of φ(n, F) over positive integers n ≤ x behaves typically as a linear function of x. We show also that for the Riemann zeta function the square mean value of the error term in question is minimal among all polynomial Euler products from the Selberg class, and that this property uniquely characterizes ζ(s).     

Periods of polynomials over a Galois ring

The period of a monic polynomial over an arbitrary Galois ring GR(pe,d) is theoretically determined by using its classical factorization and Galois extensions of rings. For a polynomial f(x) the modulo p remainder of which is a power of an irreducible polynomial over the residue field of the Galois ring, the period of f(x) is characterized by the periods of the irreducible polynomial and an associated polynomial of the form (x-1)m+pg(x). Further results on the periods of such associated polynomials are obtained, in particular, their periods are proved to achieve an upper bound value in most cases. As a consequence, the period of a monic polynomial over GR(pe,d) is equal to pe-1 times the period of its modulo p remainder polynomial with a probability close to 1, and an expression of this probability is given.     

Chromatic Polynomials of Complements of Bipartite Graphs

We define a biclique to be the complement of a bipartite graph, consisting of two cliques joined by a number of edges. In this paper we study algebraic aspects of the chromatic polynomials of these graphs. We derive a formula for the chromatic polynomial of an arbitrary biclique, and use this to give certain conditions under which two of the graphs have chromatic polynomials with the same splitting field. Finally, we use a subfamily of bicliques to prove the cubic case of the α + n conjecture, by showing that for any cubic integer α, there is a natural number n such that α + n is a chromatic root.     

On the First Galois Cohomology Group of the Algebraic Group SL1(D)

Let A be a central simple algebra over a field F. Denote the reduced norm of A over F by Nrd: A* → F* and its kernel by SL₁(A). For a field extension K of F, we study the first Galois Cohomology group H ¹(K,SL₁(A)) by two methods, valuation theory for division algebras and K-theory. We shall show that this group fails to be stable under purely transcendental extension and formal Laurent series.     

Densities for 4-class ranks of quadratic function fields

Let F=Fq(T) be a rational function field of odd characteristic, and fix a positive integer t. In this article we study the family of quadratic function fields , where D is a polynomial over Fq of odd degree having t distinct irreducible factors. The 4-class rank r₄(K) is the rank of the 4-torsion of the group of divisor classes of K, and it is known that 0?r₄(K)?t−1. For fixed r we compute the proportion of such fields K satisfying r₄(K)=r, and in particular we determine the behaviour of this value as t→∞. We will need some asymptotic results for these computations, in particular the number of polynomials D as above whose irreducible factors fulfill certain parity and quadratic residue conditions.     

The automorphisms of Petit’s algebras

Let σ be an automorphism of a field K with fixed field F. We study the automorphisms of nonassociative unital algebras which are canonical generalizations of the associative quotient algebras K[t;σ]∕fK[t;σ] obtained when the twisted polynomial f∈K[t;σ] is invariant, and were first defined by Petit. We compute all their automorphisms if σ commutes with all automorphisms in Aut_F(K) and n≥m?1, where n is the order of σ and m the degree of f, and obtain partial results for n<m?1. In the case where K∕F is a finite Galois field extension, we obtain more detailed information on the structure of the automorphism groups of these nonassociative unital algebras over F. We also briefly investigate when two such algebras are isomorphic.     

Roots of Irreducible Polynomials in Tame Henselian Extension Fields

A class of irreducible polynomials 𝒫 over a valued field (F, v) is introduced, which is the set of all monic irreducible polynomials over F when (F, v) is maximally complete. A “best-possible” criterion is given for when the existence of an approximate root in a tamely ramified Henselian extension K of F of a polynomial f in 𝒫 guarantees the existence of an exact root of f in K.     

On the generalized Ball bases

The Ball basis was introduced for cubic polynomials by Ball, and two different generalizations for higher degree m polynomials have been called the Said–Ball and the Wang–Ball basis, respectively. In this paper, we analyze some shape preserving and stability properties of these bases. We prove that the Wang–Ball basis is strictly monotonicity preserving for all m. However, it is not geometrically convexity preserving and is not totally positive for m>3, in contrast with the Said–Ball basis. We prove that the Said–Ball basis is better conditioned than the Wang–Ball basis and we include a stable conversion between both generalized Ball bases. The Wang–Ball basis has an evaluation algorithm with linear complexity. We perform an error analysis of the evaluation algorithms of both bases and compare them with other algorithms for polynomial evaluation.     

Primitive Normal Bases for Towers of Field Extensions

Given an extension E/F of Galois fields and an intermediate field K, we consider the problem whether the (E, K)-trace of a primitive F-normal element of E can be a prescribed F-normal element of K. An interesting application is the existence of trace-compatible sequences of primitive F-normal elements for certain towers of Galois fields. In this respect, particular emphasis is laid on extensions having prime power degree.