Newton’s method and high-order algorithms for the nth root computation

Two modifications of Newton’s method to accelerate the convergence of the n$n$th root computation of a strictly positive real number are revisited. Both modifications lead to methods with prefixed order of convergence p∈N,p≥2$p\in \mathbb{N},p\ge 2$. We consider affine combinations of the two modified p$p$th-order methods which lead to a family of methods of order p$p$ with arbitrarily small asymptotic constants. Moreover the methods are of order p+1$p+1$ for some specific values of a parameter. Then we consider affine combinations of the three methods of order p+1$p+1$ to get methods of order p+1$p+1$ again with arbitrarily small asymptotic constants. The methods can be of order p+2$p+2$ with arbitrarily small asymptotic constants, and also of order p+3$p+3$ for some specific values of the parameters of the affine combination. It is shown that infinitely many p$p$th-order methods exist for the n$n$th root computation of a strictly positive real number for any p≥3$p\ge 3$.     

On the second neighborhood conjecture of Seymour for regular digraphs with almost optimal connectivity

The second neighborhood conjecture of Seymour says that every antisymmetric digraph has a vertex whose second neighborhood is not smaller than the first one. The Caccetta–Häggkvist conjecture says that every digraph with n$n$ vertices and minimum out-degree r$r$ contains a cycle of length at most ⌈n/r⌉$\lceil n/r\rceil$. We give a proof of the former conjecture for digraphs with out-degree r$r$ and connectivity r−1$r-1$, and of the second one for digraphs with connectivity r−1$r-1$ and r≥n/3$r\ge n/3$. The main tool is the isoperimetric method of Hamidoune.     

A note on distance-regular graphs with a small number of vertices compared to the valency

In this note we study distance-regular graphs with a small number of vertices compared to the valency. We show that for a given α>2$\alpha >2$, there are finitely many distance-regular graphs Γ$\Gamma$ with valency k$k$, diameter D≥3$D\ge 3$ and v$v$ vertices satisfying v≤αk$v\le \alpha k$ unless (D=3$D=3$ and Γ$\Gamma$ is imprimitive) or (D=4$D=4$ and Γ$\Gamma$ is antipodal and bipartite). We also show, as a consequence of this result, that there are finitely many distance-regular graphs with valency k≥3$k\ge 3$, diameter D≥3$D\ge 3$ and _c2≥εk$c_2\ge \epsilon k$ for a given 0<ε<1$0<\epsilon <1$ unless (D=3$D=3$ and Γ$\Gamma$ is imprimitive) or (D=4$D=4$ and Γ$\Gamma$ is antipodal and bipartite).     

On the effectiveness of a generalization of Miller’s primality theorem

Berrizbeitia and Olivieri showed in a recent paper that, for any integer r$r$, the notion of ω$\omega$-prime to base a$a$ leads to a primality test for numbers n≡1$n\equiv 1$ mod r$r$, that under the Extended Riemann Hypothesis (ERH) runs in polynomial time. They showed that the complexity of their test is at most the complexity of the Miller primality test (MPT), which is O((logn)^4+o(1))$O\left({(logn)}^{4+o\left(1\right)}\right)$. They conjectured that their test is more effective than the MPT if r$r$ is large.     

On functional limits of short- and long-memory linear processes with GARCH(1,1) noises

This paper considers the short- and long-memory linear processes with GARCH (1,1) noises. The functional limit distributions of the partial sum and the sample autocovariances are derived when the tail index α$\alpha$ is in (0,2)$(0,2)$, equal to 2, and in (2,∞)$(2,\infty )$, respectively. The partial sum weakly converges to a functional of α$\alpha$-stable process when α<2$\alpha <2$ and converges to a functional of Brownian motion when α≥2$\alpha \ge 2$. When the process is of short-memory and α<4$\alpha <4$, the autocovariances converge to functionals of α/2$\alpha /2$-stable processes; and if α≥4$\alpha \ge 4$, they converge to functionals of Brownian motions. In contrast, when the process is of long-memory, depending on α$\alpha$ and β$\beta$ (the parameter that characterizes the long-memory), the autocovariances converge to either (i) functionals of α/2$\alpha /2$-stable processes; (ii) Rosenblatt processes (indexed by β$\beta$, 1/2<β<3/4$1/2<\beta <3/4$); or (iii) functionals of Brownian motions. The rates of convergence in these limits depend on both the tail index α$\alpha$ and whether or not the linear process is short- or long-memory. Our weak convergence is established on the space of càdlàg functions on [0,1]$[0,1]$ with either (i) the _J1$J_1$ or the _M1$M_1$ topology (Skorokhod, 1956); or (ii) the weaker form S$S$ topology (Jakubowski, 1997). Some statistical applications are also discussed.     

Optimality conditions and duality for nondifferentiable multiobjective programming problems involving d-r-type I functions

In this paper, new classes of nondifferentiable functions constituting multiobjective programming problems are introduced. Namely, the classes of d$d$-r$r$-type I objective and constraint functions and, moreover, the various classes of generalized d$d$-r$r$-type I objective and constraint functions are defined for directionally differentiable multiobjective programming problems. Sufficient optimality conditions and various Mond–Weir duality results are proved for nondifferentiable multiobjective programming problems involving functions of such type. Finally, it is showed that the introduced d$d$-r$r$-type I notion with r≠0$r\ne 0$ is not a sufficient condition for Wolfe weak duality to hold. These results are illustrated in the paper by suitable examples.     

A unified proof of Brooks’ theorem and Catlin’s theorem

Brooks’ theorem is a fundamental result in the theory of graph coloring. Catlin proved the following strengthening of Brooks’ theorem: Let d$d$ be an integer at least 3, and let G$G$ be a graph with maximum degree d$d$. If G$G$ does not contain _Kd+1$K_{d+1}$ as a subgraph, then G$G$ has a d$d$-coloring in which one color class has size α(G)$\alpha \left(G\right)$. Here α(G)$\alpha \left(G\right)$ denotes the independence number of G$G$. We give a unified proof of Brooks’ theorem and Catlin’s theorem.     

Modules satisfying the weak Nakayama property

Let R$R$ be a commutative ring with identity. We will say that an R$R$-module M$M$ satisfies the weak Nakayama property, if IM=M$IM=M$, where I$I$ is an ideal of R$R$, implies that for any x∈M$x\in M$ there exists a∈I$a\in I$ such that (a−1)x=0$(a-1)x=0$. In this paper, we will study modules satisfying the weak Nakayama property. It is proved that if R$R$ is a local ring, then R$R$ is a Max ring if and only if J(R)$J\left(R\right)$, the Jacobson radical of R$R$, is T$T$-nilpotent if and only if every R$R$-module satisfies the weak Nakayama property.     

Asymptotic average shadowing property on compact metric spaces

We prove that if for a continuous map f$f$ on a compact metric space X$X$, the chain recurrent set, R(f)$R\left(f\right)$ has more than one chain component, then f$f$ does not satisfy the asymptotic average shadowing property. We also show that if a continuous map f$f$ on a compact metric space X$X$ has the asymptotic average shadowing property and if A$A$ is an attractor for f$f$, then A$A$ is the single attractor for f$f$ and we have A=R(f)$A=R\left(f\right)$. We also study diffeomorphisms with asymptotic average shadowing property and prove that if M$M$ is a compact manifold which is not finite with dimM=2$dimM=2$, then the C¹$C^1$ interior of the set of all C¹$C^1$ diffeomorphisms with the asymptotic average shadowing property is characterized by the set of Ω$\Omega$-stable diffeomorphisms.     

On probabilistic results for the discrepancy of a hybrid-Monte Carlo sequence

In many applications it has been observed that hybrid-Monte Carlo sequences perform better than Monte Carlo and quasi-Monte Carlo sequences, especially in difficult problems. For a mixed s$s$-dimensional sequence m$m$, whose elements are vectors obtained by concatenating d$d$-dimensional vectors from a low-discrepancy sequence q$q$ with (s−d)$(s-d)$-dimensional random vectors, probabilistic upper bounds for its star discrepancy have been provided. In a paper of G. Ökten, B. Tuffin and V. Burago [G. Ökten, B. Tuffin, V. Burago, J. Complexity 22 (2006), 435–458] it was shown that for arbitrary ε>0$\epsilon >0$ the difference of the star discrepancies of the first N$N$ points of m$m$ and q$q$ is bounded by ε$\epsilon$ with probability at least 1−2exp(−ε²N/2)$1-2exp(-{\epsilon }^{2}N/2)$ for N$N$ sufficiently large. The authors did not study how large N$N$ actually has to be and if and how this actually depends on the parameters s$s$ and ε$\epsilon$. In this note we derive a lower bound for N$N$, which significantly depends on s$s$ and ε$\epsilon$. Furthermore, we provide a probabilistic bound for the difference of the star discrepancies of the first N$N$ points of m$m$ and q$q$, which holds without any restrictions on N$N$. In this sense it improves on the bound of Ökten, Tuffin and Burago and is more helpful in practice, especially for small sample sizes N$N$. We compare this bound to other known bounds.     

On topological entropy of commuting tree maps

Let T$T$ be a tree with s$s$ ends and f,g$f,g$ be continuous maps from T$T$ to T$T$ with f°g=g°f$f°g=g°f$. In this note we show that if there exists a positive integer m≥2$m\ge 2$ such that gcd(m,l)=1$gcd(m,l)=1$ for any 2≤l≤s$2\le l\le s$ and f,g$f,g$ share a periodic point which is a km$km$-periodic point of f$f$ for some positive integer k$k$, then the topological entropy of f°g$f°g$ is positive.     

Sister Beiter and Kloosterman: A tale of cyclotomic coefficients and modular inverses

For a fixed prime p$p$, the maximum coefficient (in absolute value) M(p)$M\left(p\right)$ of the cyclotomic polynomial _Φpqr(x)${\Phi }_{pqr}\left(x\right)$, where r$r$ and q$q$ are free primes satisfying r>q>p$r>q>p$ exists. Sister Beiter conjectured in 1968 that M(p)≤(p+1)/2$M\left(p\right)\le (p+1)/2$. In 2009 Gallot and Moree showed that M(p)≥2p(1−?)/3$M\left(p\right)\ge 2p(1-?)/3$ for every p$p$ sufficiently large. In this article Kloosterman sums (‘cloister man sums’) and other tools from the distribution of modular inverses are applied to quantify the abundancy of counter-examples to Sister Beiter’s conjecture and sharpen the above lower bound for M(p)$M\left(p\right)$.     

Parametric inference for discretely observed multidimensional diffusions with small diffusion coefficient

We consider a multidimensional diffusion X$X$ with drift coefficient b(α,_Xt)$b(\alpha ,X_t)$ and diffusion coefficient ?σ(β,_Xt)$?\sigma (\beta ,X_t)$. The diffusion sample path is discretely observed at times _tk=kΔ$t_k=k\Delta$ for k=1…n$k=1\dots n$ on a fixed interval [0,T]$[0,T]$. We study minimum contrast estimators derived from the Gaussian process approximating X$X$ for small ?$?$. We obtain consistent and asymptotically normal estimators of α$\alpha$ for fixed Δ$\Delta$ and ?→0$?\to 0$ and of (α,β)$(\alpha ,\beta )$ for Δ→0$\Delta \to 0$ and ?→0$?\to 0$ without any condition linking ?$?$ and Δ$\Delta$. We compare the estimators obtained with various methods and for various magnitudes of Δ$\Delta$ and ?$?$ based on simulation studies. Finally, we investigate the interest of using such methods in an epidemiological framework.     

Matchings in graphs of odd regularity and girth

We establish lower bounds on the matching number of graphs of given odd regularity d$d$ and odd girth g$g$, which are sharp for many values of d$d$ and g$g$. For d=g=5$d=g=5$, we characterize all extremal graphs.     

Semilocal convergence of a family of third-order methods in Banach spaces under Hölder continuous second derivative

In this paper, the semilocal convergence of a family of multipoint third-order methods used for solving F(x)=0$F\left(x\right)=0$ in Banach spaces is established. It is done by using recurrence relations under the assumption that the second Fréchet derivative of F$F$ satisfies Hölder continuity condition. Based on two parameters depending upon F$F$, a new family of recurrence relations is defined. Using these recurrence relations, an existence–uniqueness theorem is established to prove that the R$R$-order convergence of the method is (2+p)$(2+p)$. A priori error bounds for the method are also derived. Two numerical examples are worked out to demonstrate the efficacy of our approach.