A computational comparison of the first nine members of a determinantal family of root-finding methods

For each natural number m greater than one, and each natural number k less than or equal to m, there exists a root-finding iteration function, B_m^(k) defined as the ratio of two determinants that depend on the first m−k derivatives of the given function. This infinite family is derived in Kalantari (J. Comput. Appl. Math. 126 (2000) 287–318) and its order of convergence is analyzed in Kalantari (BIT 39 (1999) 96–109). In this paper we give a computational study of the first nine root-finding methods. These include Newton, secant, and Halley methods. Our computational results with polynomials of degree up to 30 reveal that for small degree polynomials B_m^(k−1) is more efficient than B_m^(k), but as the degree increases, B_m^(k) becomes more efficient than B_m^(k−1). The most efficient of the nine methods is B₄⁽⁴⁾, having theoretical order of convergence equal to 1.927. Newton's method which is often viewed as the method of choice is in fact the least efficient method.     

On the word problem for the free Burnside semigroups satisfying <Emphasis Type="Italic">x</Emphasis><Superscript>2</Superscript> = <Emphasis Type="Italic">x</Emphasis><Superscript>3</Superscript>

We study the word problem for the free Burnside semigroups satisfying x ² = x ³. For any k > 2, we reduce this problem for the k-generated free Burnside semigroup B(2, 1, k) to the word problem for the two-generated semigroup B(2, 1, 2). Furthermore, if every element of B(2, 1, 2) is a regular language, then every element of B(2, 1, k) appears to be a regular language as well. Thus, Brzozowski’s conjecture holds for the semigroup B(2, 1, k) if and only if it holds for B(2, 1, 2).     

On free semilattice-ordered semigroups satisfying x n =x

Let B(k,0,n) denote the group with k generators which is free in the group variety defined by the identity x ⁿ =1. Let B _slo (k,1,n) denote the semilattice-ordered semigroup with k generators which is free in the semilattice-ordered semigroup variety defined by the identity x ⁿ =x. We prove a generalization of the Green-Rees theorem: B _slo (k,1,n) is finite for all k≥1 if and only if B(k,0,n−1) is finite for all k≥1. We find a formula for card(B _slo (1,1,n)). We construct B _slo (k,1,n) for some concrete values of k and n.     

The number of ideals in a quadratic field

LetK be a quadratic Geld, and letR(N) be the number of integer ideals inK with norm at most AT. Letx with conductork be the quadratic character associated withK. Then |R(N)−NL(1,x)|⩽Bk ^50/73 N ^23/73(logN)^461/146 forN ≥Ak, whereA andB are constants. ForN ≥Ak ^c,C sufficiently large, the factork ^50/73 may be replaced by (d(k))^4/73 k ^46/73. Dedicated to the memory of Professor K G Ramanathan     

An equivalence between varieties of cyclic Post algebras and varieties generated by a finite field

In this paper we give a term equivalence between the simple k-cyclic Post algebra of order p, L _p,k, and the finite field F(p ^k) with constants F(p). By using Lagrange polynomials, we give an explicit procedure to obtain an interpretation Φ₁ of the variety V(L _p,k) generated by L _p,k into the variety V(F(p ^k)) generated by F(p ^k) and an interpretation Φ₂ of V(F(p ^k)) into V(L _p,k) such that Φ₂Φ₁(B) = B for every B ε V(L _p,k) and Φ₁Φ₂(R) = R for every R ε V(F(p ^k)).     

Sums and differences of four kth powers

We prove an upper bound for the number of representations of a positive integer N as the sum of four kth powers of integers of size at most B, using a new version of the determinant method developed by Heath-Brown, along with recent results by Salberger on the density of integral points on affine surfaces. More generally we consider representations by any integral diagonal form. The upper bound has the form O_N(B^c/?k){O_{N}(B^{c/\sqrt{k}})}, whereas earlier versions of the determinant method would produce an exponent for B of order k ^−1/3 (uniformly in N) in this case. Furthermore, we prove that the number of representations of a positive integer N as a sum of four kth powers of non-negative integers is at most O_e(N^1/k+2/k3/2+e){O_{\varepsilon}(N^{1/k+2/k^{3/2}+\varepsilon})} for k ≥ 3, improving upon bounds by Wisdom.     

Lie powers and Witt vectors

In the study of Lie powers of a module V in prime characteristic p, a basic role is played by certain modules B _n introduced by Bryant and Schocker. The isomorphism types of the B _n are not fully understood, but these modules fall into infinite families , one family B(k) for each positive integer k not divisible by p, and there is a recursive formula for the modules within B(k). Here we use combinatorial methods and Witt vectors to show that each module in B(k) is isomorphic to a direct sum of tensor products of direct summands of the kth tensor power V ^{⊗ k} . To the memory of Manfred Schocker.     

Geometric algorithms for the minimum cost assignment problem

We consider the minimum-cost λ-assignment problem, which is equivalent to the minimum-weight one-to-many matching problem on a complete bipartite graph Γ = (A, B), where A and B have n and k nodes (n ? k), respectively. Formulating the problem geometrically, we given an O(kn + k^2.5n^0.5 log^1.5 n) time randomized algorithm, which is better than the existing O(kn² + n² log n) time algorithm if n > k log k.     

Enumeration of the bent functions of least deviation from a quadratic bent function

We study a construction of the bent functions of least deviation from a quadratic bent function, describe all these bent functions of 2k variables, and show that the quantity of them is 2 ^k (2¹ + 1) ... (2 ^k + 1). We find some lower bound on the number of the bent functions of least deviation from a bent function of the Maiorana-McFarland class.     

On Λ(p)-subsets of squares

This paper is a follow up of [B₁]. It is shown that the sequence of squares {n ²|n=1, 2, ...} contains Λ(p)-subsets of “maximal density”, for any givenp>4. The proof is based on the probabilistic method developed in [B₁] and a precise estimate of the Λ(p)-constant for the sequence of squares itself. Analogues of this phenomenon are obtained for other arithmetic sets, such as the sequence ofkth powers {n ^k |n=1, 2, ...} or the sequence of prime numbers. Sections 2 and 3 of the paper are of independent interest to orthogonal system theory.     

On L. Fejes Tóth’s “sausage-conjecture”

Letk non-overlapping translates of the unitd-ballB ^d ⊂E ^d be given, letC _k be the convex hull of their centers, letS _k be a segment of length 2(k−1) and letV denote the volume. L. Fejes Tóth's sausage conjecture, says that ford≧5V(S _k +B ^d ) ≦V(C _k +B ^d In the paper partial results are given.     

Successive projection method for solving the unbalanced Procrustes problem

We present a successive projection method for solving the unbalanced Procrustes problem: given matrix A∈Rn×n and B∈Rn×k, n>k, minimize the residual‖AQ-B‖F with the orthonormal constraint QTQ = Ik on the variant Q∈Rn×k. The presented algorithm consists of solving k least squares problems with quadratic constraints and an expanded balance problem at each sweep. We give a detailed convergence analysis. Numerical experiments reported in this paper show that our new algorithm is superior to other existing methods.     

A Note on the Double Affine Hecke Algebra of Type GL2

We express the double affine Hecke algebra ? associated to the general linear group GL₂(k) (here, k is a field with char(k) ≠ 2) as an amalgamated free product of quadratic extensions over the three-dimensional quantum torus 𝒪_q((k^×)³). With an eye towards proving ring-theoretic results pertaining to ?, a general treatment of amalgamated products of Ore and quadratic extensions is given. We prove an analogue of the Hilbert Basis Theorem for an amalgamated product Q of quadratic extensions and determine conditions for when the one-sided ideals of Q are principal or doubly-generated. Furthermore, we determine sufficient conditions which imply Q is a principal ideal ring. Finally, we construct an explicit isomorphism from ? to the amalgamated free product ring of quadratic extensions over 𝒪_q((k^×)³), a ring known to be noetherian. Therefore, it follows that ? is noetherian.     

Convolution identities and lacunary recurrences for Bernoulli numbers

We extend Euler's well-known quadratic recurrence relation for Bernoulli numbers, which can be written in symbolic notation as n(B₀+B₀)=−nBn−1−(n−1)Bn, to obtain explicit expressions for n(Bk+Bm) with arbitrary fixed integers k,m?0. The proof uses convolution identities for Stirling numbers of the second kind and for sums of powers of integers, both involving Bernoulli numbers. As consequences we obtain new types of quadratic recurrence relations, one of which gives B6k depending only on B2k,B2k+2,…,B4k.     

More on Poincaré’s and Perron’s Theorems for Difference Equations∗

Consider the scalar kth order linear difference equation: x(n + k) + pi(n)x(n + k - 1) + … + pk(n)x(n) = 0 where the limits qi=lim_n→∞Pi(n) (i=1,…,k) are finite. In this paper, we confirm the conjecture formulated recently by Elaydi. Namely, every nonzero solution x of (?) satisfies the same asymptotic relation as the fundamental solutions described earlier by Perron, ie., ?= lim sup_n→∞ |x(n)| is equal to the modulus of one of the roots of the characteristics equation χ ^k + q ₁χ ^k?1+…+qk=0. This result is a consequence of a more general theorem concerning the Poincaré difference system x(n+1)=[A+B(n]x(n), where A and B(n) (n=0,1,…) are square matrices such that ‖B(n)‖ →0 as n → ∞. As another corollary, we obtain a new limit relation for the solutions of (?).     

The Algebra of Flows in Graphs

We define a contravariant functorKfrom the category of finite graphs and graph morphisms to the category of finitely generated graded abelian groups and homomorphisms. For a graphX, an abelian groupB, and a nonnegative integerj, an element of Hom(K^j(X), B) is a coherent family ofB-valued flows on the set of all graphs obtained by contracting some (j − 1)-set of edges ofX; in particular, Hom(K¹(X), ) is the familiar (real) “cycle-space” ofX. We show thatK ^· (X) is torsion-free and that its Poincaré polynomial is the specializationt^{n − k}T_X(1/t, 1 + t) of the Tutte polynomial ofX(hereXhasnvertices andkcomponents). Functoriality ofK ^· induces a functorial coalgebra structure onK ^· (X); dualizing, for any ringBwe obtain a functorialB-algebra structure on Hom(K ^· (X), B). WhenBis commutative we present this algebra as a quotient of a divided power algebra, leading to some interesting inequalities on the coefficients of the above Poincaré polynomial. We also provide a formula for the theta function of the lattice of integer-valued flows inX, and conclude with 10 open problems.     

Probabilistic constructions of B 2[g] sequences

We use the probabilistic method to prove that for any positive integer g there exists an infinite B2[g] sequence A = {ak} such that ak ≤ k^2＋1/g（log k）^1/g＋0（1） as k→∞. The exponent 2＋1/g improves the previous one, 2 ＋ 2/g, obtained by Erdos and Renyi in 1960. We obtain a similar result for B2 [g] sequences of squares.     

Polynomial Factorisation and an Application to Regular Directed Graphs

The main theme is the distribution of polynomials of given degree which split into a product of linear factors over a finite field. The work was motivated by the following problem on regular directed graphs. Extending a notion of Chung, Katz has defined a regular directed graph based on thek-algebrak[X]/(f), wherekis the finite field of orderqandfa monic polynomial of degreenoverk. It is shown that the diameter of this graph is at mostn+2 wheneverq≥B(n)=[n(n+2)!]². This improves on the work of Katz who gave a similar result for square-free polynomialsfwithout specifyingB(n).     

Error estimates of expanded mixed methods for optimal control problems governed by hyperbolic integro‐differential equations

In this article, we investigate the L^∞(L²) ‐error estimates of the semidiscrete expanded mixed finite element methods for quadratic optimal control problems governed by hyperbolic integrodifferential equations. The state and the costate are discretized by the order k Raviart‐Thomas mixed finite element spaces, and the control is approximated by piecewise polynomials of order k(k ≥ 0). We derive error estimates for both the state and the control approximation. Numerical experiments are presented to test the theoretical results. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

On B(5, 18) Groups

A group G is said to be a B(n, k) group if for any n-element subset A of G, |A²| ≤k. In this paper, a characterization of B(5, 18) groups is given. It is shown that G is a B(5, 18) group if and only if one of the following statements holds: (1) G is abelian; (2) |G| ≤18; (3) G ? ? a, b | a⁵ = b⁴ = 1, a^b = a^?1 ?.