On the guaranteed convergence of new two-point root-finding methods for polynomial zeros

We presented new two-point methods for the simultaneous approximation of all n simple (real or complex) zeros of a polynomial of degree n. We proved that the R-order of convergence of the total-step version is three. Moreover, computationally verifiable initial conditions that guarantee the convergence of one of the proposed methods are stated. These conditions are stated in the spirit of Smale’s point estimation theory; they depend only on available data, the polynomial coefficients, polynomial degree n and initial approximations \(x_{1}^{(0)},\ldots ,x_{n}^{(0)}\) , which is of practical importance. Using the Gauss-Seidel approach we state the corresponding single-step version and consequently its prove that the lower bound of its R-order of convergence is at least 2 + y _n > 3, where y _n ∈ (1, 2) is the unique positive root of the equation y ⁿ ? y ? 2 = 0. Two numerical examples are given to demonstrate the convergence behavior of the considered methods, including global convergence.     

Brauer–Thrall for Totally Reflexive Modules over Local Rings of Higher Dimension

Let R be a commutative Noetherian local ring. Assume that R has a pair {x,y} of exact zerodivisors such that dim R/(x,y)?≥?2 and all totally reflexive R/(x)-modules are free. We show that the first and second Brauer–Thrall type theorems hold for the category of totally reflexive R-modules. More precisely, we prove that, for infinitely many integers n, there exists an indecomposable totally reflexive R-module of multiplicity n. Moreover, if the residue field of R is infinite, we prove that there exist infinitely many isomorphism classes of indecomposable totally reflexive R-modules of multiplicity n.     

Flip Graphs of Bounded Degree Triangulations

We study flip graphs of triangulations whose maximum vertex degree is bounded by a constant k. In particular, we consider triangulations of sets of n points in convex position in the plane and prove that their flip graph is connected if and only if k > 6; the diameter of the flip graph is O(n ²). We also show that, for general point sets, flip graphs of pointed pseudo-triangulations can be disconnected for k ≤ 9, and flip graphs of triangulations can be disconnected for any k. Additionally, we consider a relaxed version of the original problem. We allow the violation of the degree bound k by a small constant. Any two triangulations with maximum degree at most k of a convex point set are connected in the flip graph by a path of length O(n log n), where every intermediate triangulation has maximum degree at most k + 4.     

Plane Graphs with Parity Constraints

Let S be a set of n points in general position in the plane. Together with S we are given a set of parity constraints, that is, every point of S is labeled either even or odd. A graph G on S satisfies the parity constraint of a point ${p\in S}$ if the parity of the degree of p in G matches its label. In this paper, we study how well various classes of planar graphs can satisfy arbitrary parity constraints. Specifically, we show that we can always find a plane tree, a two-connected outerplanar graph, or a pointed pseudo-triangulation that satisfy all but at most three parity constraints. For triangulations we can satisfy about 2/3 of the parity constraints and we show that in the worst case there is a linear number of constraints that cannot be fulfilled. In addition, we prove that for a given simple polygon H with polygonal holes on S, it is NP-complete to decide whether there exists a triangulation of H that satisfies all parity constraints.     

Computational Complexity of the Vertex Cover Problem in the Class of Planar Triangulations

We study the computational complexity of the vertex cover problem in the class of planar graphs (planar triangulations) admitting a plane representation whose faces are triangles. It is shown that the problem is strongly NP-hard in the class of 4-connected planar triangulations in which the degrees of vertices are of order O(log n), where n is the number of vertices, and in the class of plane 4-connected Delaunay triangulations based on the Minkowski triangular distance. A pair of vertices in such a triangulation is adjacent if and only if there is an equilateral triangle ?(p, λ) with p ∈ R² and λ > 0 whose interior does not contain triangulation vertices and whose boundary contains this pair of vertices and only it, where ?(p, λ) = p + λ? = {x ∈ R²: x = p + λa, a ∈ ?}; here ? is the equilateral triangle with unit sides such that its barycenter is the origin and one of the vertices belongs to the negative y-axis. Keywords: computational complexity, Delaunay triangulation, Delaunay TD-triangulation.     

Lines imply spaces in density Ramsey theory

Some results of geometric Ramsey theory assert that if F is a finite field (respectively, set) and n is sufficiently large, then in any coloring of the points of Fⁿ there is a monochromatic k-dimensional affine (respectively, combinatorial) subspace (see [9]). We prove that the density version of this result for lines (i.e., k = 1) implies the density version for arbitrary k. By using results in [3, 6] we obtain various consequences: a “group-theoretic” version of Roth's Theorem, a proof of the density assertion for arbitrary k in the finite field case when ∥F∥ = 3, and a proof of the density assertion for arbitrary k in the combinatorial case when ∥F∥ = 2.     

On Degrees of Growth of Finitely Generated Groups

We prove that for an arbitrary function ρ of subexponential growth there exists a group G of intermediate growth whose growth function satisfies the inequality v _G,S (n) ? ρ(n) for all n. For every prime p, one can take G to be a p-group; one can also take a torsion-free group G. We also discuss some generalizations of this assertion.     

Arithmetic transfinite induction and recursive well-orderings

A uniform, algebraic proof that every number-theoretic assertion provable in any of the intuitionistic theories T listed below has a well-founded recursive proof tree (demonstraby in T) is given. Thus every such assertion is provable by transfinite induction over some primitive recursive well-ordering. T can be higher order number theory, set theory, or its extensions equiconsistent with large cardinals. It is shown that there is a number-theoretic assertion B(n) (independent of T) with a parameter n such that any primitive recursive linear ordering R on ω for which transfinite induction on R for B(n) is provable in T is in fact a well-ordering.     

Approximations in the l∞ norm and the generalized inverse

We introduce the concept of a strict l_∞-metric projector, based in the definition of strict approximation, to prove that for each matrix A of order m×n with coefficients in the field R of real numbers there exists a set of operators G: R^m → Rⁿ homogeneous and continuous, but not necessarily linear (strict generalized inverse) such that AGA = A and 6AGy?y6 is minimized for all y, when the norm is the l_∞ norm. We investigate the properties of these operators and prove that there are two distinguished operators A^-1_{∞, β} and A^-1_∞ which are extensions of the generalized inverse introduced by Newman and Odell in the case of a strictly convex norm.     

Catalan Triangulations of the Möbius Band

A Catalan triangulation of the Möbius band is an abstract simplicial complex triangulating the Möbius band which uses no interior vertices, and has vertices labelled 1, 2, …, n in order as one traverses the boundary. We prove two results about the structure of this set, analogous to well-known results for Catalan triangulations of the disk. The first is a generating function for Catalan triangulations of M having n vertices, and the second is that any two such triangulations are connected by a sequence of diagonal-flips.     

On almost-quasi-commutative rings

A ring R is called almost-quasi-commutative if for each x, y ∈ R there exist nonzero relatively prime integers j = j(x, y) and k = k(x, y) and a non-negative integer n = n(x, y) such that jxy = k(yx) ⁿ . We establish some general properties of such rings, study commutativity of almost-quasi-commutative R, and consider several examples.     

Acute triangulations of polyhedra and ℝ N

We study the problem of acute triangulations of convex polyhedra and the space ? ⁿ . Here an acute triangulation is a triangulation into simplices whose dihedral angles are acute. We prove that acute triangulations of the n-cube do not exist for n≥4. Further, we prove that acute triangulations of the space ? ⁿ do not exist for n≥5. In the opposite direction, in ?³, we present a construction of an acute triangulation of the cube, the regular octahedron and a non-trivial acute triangulation of the regular tetrahedron. We also prove nonexistence of an acute triangulation of ?⁴ if all dihedral angles are bounded away from π/2.     

Positivity of Riesz functionals and solutions of quadratic and quartic moment problems

We employ positivity of Riesz functionals to establish representing measures (or approximate representing measures) for truncated multivariate moment sequences. For a truncated moment sequence y, we show that y lies in the closure of truncated moment sequences admitting representing measures supported in a prescribed closed set K⊆Rn if and only if the associated Riesz functional Ly is K-positive. For a determining set K, we prove that if Ly is strictly K-positive, then y admits a representing measure supported in K. As a consequence, we are able to solve the truncated K-moment problem of degree k in the cases: (i) (n,k)=(2,4) and K=R²; (ii) n?1, k=2, and K is defined by one quadratic equality or inequality. In particular, these results solve the truncated moment problem in the remaining open cases of Hilbert's theorem on sums of squares.     

Some sieves for partition theory

A Combinatorial lemma due to Zolnowsky is applied to partition theory in a new way. Several even-odd formulas are derived. A combinatorial proof of the Jacobi triple-product identity is given. Some sieve formulas are proved which relate to the Euler pentagonal number theorem and the Rogers-Ramanujan identities and their generalizations. A formula is given for the number of partitions of n into parts not congruent to 0, ±x (mod y).     

Commutativity of rings with derivations

I. N. Herstein [10] proved that a prime ring of characteristic not two with a nonzero derivation d satisfying d(x)d(y) = d(y)d(x) for all x, y must be commutative, and H. E. Bell and M. N. Daif [8] showed that a prime ring of arbitrary characteristic with nonzero derivation d satisfying d(xy) = d(yx) for all x, y in some nonzero ideal must also be commutative. For semiprime rings, we show that an inner derivation satisfying the condition of Bell and Daif on a nonzero ideal must be zero on that ideal, and for rings with identity, we generalize all three results to conditions on derivations of powers and powers of derivations. For example, let R be a prime ring with identity and nonzero derivation d, and let m and n be positive integers such that, when charR is finite, m ∨ n < charR. If d(x ^m y ⁿ ) = d(y ⁿ x ^m ) for all x, y ∈ R, then R is commutative. If, in addition, charR≠ 2 and the identity is in the image of an ideal I under d, then d(x) ^m d(y) ⁿ = d(y) ⁿ d(x) ^m for all x, y ∈ I also implies that R is commutative.     

The diophantine equation x3 + 3y3 = 2n

It is proved that the equation of the title has a finite number of integral solutions (x, y, n) and necessary conditions are given for (x, y, n) in order that it can be a solution (Theorem 2). It is also proved that for a given odd x₀ there is at most one integral solution (y, n), n ≥ 3, to x₀³ + 3y³ = 2ⁿ and for a given odd y₀ there is at most one integral solution (x, n), n ≥ 3, to x³ + 3y₀³ = 2ⁿ.     

The regular graph of a commutative ring

Let R be a commutative ring, let Z(R) be the set of all zero-divisors of R and Reg(R) = R\Z(R). The regular graph of R, denoted by G(R), is a graph with all elements of Reg(R) as the vertices, and two distinct vertices x, y ∈ Reg(R) are adjacent if and only if x+y ∈ Z(R). In this paper we show that if R is a commutative Noetherian ring and 2 ∈ Z(R), then the chromatic number and the clique number of G(R) are the same and they are 2 ⁿ , where n is the minimum number of prime ideals whose union is Z(R). Also, we prove that all trees that can occur as the regular graph of a ring have at most two vertices.     

Tiling R 5 by Crosses

An n-dimensional cross comprises 2n+1 unit cubes: the center cube and reflections in all its faces. It is well known that there is a tiling of R ⁿ by crosses for all n. AlBdaiwi and the first author proved that if 2n+1 is not a prime then there are $2^{\aleph_{0}}$ non-congruent regular (= face-to-face) tilings of R ⁿ by crosses, while there is a unique tiling of R ⁿ by crosses for n=2,3. They conjectured that this is always the case if 2n+1 is a prime. To support the conjecture we prove in this paper that also for R ⁵ there is a unique regular, and no non-regular, tiling by crosses. So there is a unique tiling of R ³ by crosses, there are $2^{\aleph_{0}}$ tilings of R ⁴, but for R ⁵ there is again only one tiling by crosses. We guess that this result goes against our intuition that suggests ‘the higher the dimension of the space, the more freedom we get’.     

A constructive proof of Ky Fan's generalization of Tucker's lemma

We present a proof of Ky Fan's combinatorial lemma on labellings of triangulated spheres that differs from earlier proofs in that it is constructive. We slightly generalize the hypotheses of Fan's lemma to allow for triangulations of Sⁿ that contain a flag of hemispheres. As a consequence, we can obtain a constructive proof of Tucker's lemma that holds for a more general class of triangulations than the usual version.