Iterative roots of piecewise monotonic functions with finite nonmonotonicity height

It is known that any continuous piecewise monotonic function with nonmonotonicity height not less than 2 has no continuous iterative roots of order n greater than the number of forts of the function. In this paper, we consider the problem of iterative roots in the case that the order n is less than or equal to the number of forts. By investigating the trajectory of possible continuous roots, we give a general method to find all iterative roots of those functions with finite nonmonotonicity height.     

Real polynomial iterative roots in the case of nonmonotonicity height ≥ 2

It is known that a strictly piecewise monotone function with nonmonotonicity height ≥ 2 on a compact interval has no iterative roots of order greater than the number of forts. An open question is: Does it have iterative roots of order less than or equal to the number of forts? An answer was given recently in the case of "equal to". Since many theories of resultant and algebraic varieties can be applied to computation of polynomials, a special class of strictly piecewise monotone functions, in this paper we investigate the question in the case of "less than" for polynomials. For this purpose we extend the question from a compact interval to the whole real line and give a procedure of computation for real polynomial iterative roots. Applying the procedure together with the theory of discriminants, we find all real quartic polynomials of non-monotonicity height 2 which have quadratic polynomial iterative roots of order 2 and answer the question.     

Continuity of iteration and approximation of iterative roots

Motivated by computing iterative roots for general continuous functions, in this paper we prove the continuity of the iteration operators T_n, defined by T_nf=fⁿ. We apply the continuity and introduce the concept of continuity degree to answer positively the approximation question: If lim_m→∞F_m=F, can we find an iterative root f_m of F_m of order n for each m∈N such that the sequence (f_m) tends to the iterative root of F of order n associated with a given initial function? We not only give the construction of such an approximating sequence (f_m) but also illustrate the approximation of iterative roots with an example. Some remarks are presented in order to compare our approximation with the Hyers-Ulam stability.     

Non-monotonic iterative roots extended from characteristic intervals

It has been treated as a difficult problem to find iterative roots of non-monotonic functions. For some PM functions which do not increase the number of forts under iteration a method was given to obtain a non-monotonic iterative root by extending a monotone iterative root from the characteristic interval. In this paper we prove that every continuous iterative root is an extension from the characteristic interval and give various modes of extension for those iterative roots of PM functions.     

Asymptotic distributions of the latent roots of the covariance matrix with multiple population roots

An asymptotic expansion for large sample size n is derived by a partial differential equation method, up to and including the term of order n^?2, for the ₀F₀ function with two argument matrices which arise in the joint density function of the latent roots of the covariance matrix, when some of the population latent roots are multiple. Then we derive asymptotic expansions for the joint and marginal distributions of the sample roots in the case of one multiple root.     

Some applications of Montgomery's sieve

Artin has conjectured that every positive integer not a perfect square is a primitive root for some odd prime. A new estimate is obtained for the number of integers in the interval [M + 1, M + N] which are not primitive roots for any odd prime, improving on a theorem of Gallagher.Erd?s has conjectured that 7, 15, 21, 45, 75, and 105 are the only values of the positive integer n for which n ? 2^k is prime for every k with 1 ≤ k ≤ log₂n. An estimate is proved for the number of such n ≤ N.     

Note on the uniquely colorable graphs

For n ≥ 3, if there exists a uniquely n colorable graph which contains no subgraph isomorphic to K₃, then the number of points in the graph must be strictly greater than n²+n?1.     

An example of convex Hamiltonian diffeomorphism where asymptotic distance from identity is strictly greater than the minimal action

We construct a convex Hamiltonian diffeomorphism on the unit ball of cotangent bundle of Tn (n?2), where the asymptotic distance from identity is strictly greater than the minimal action.     

Dominant regions in noncrystallographic hyperplane arrangements

For a crystallographic root system, dominant regions in the Catalan hyperplane arrangement are in bijection with antichains in a partial order on the positive roots. For a noncrystallographic root system, the analogous arrangement and regions have importance in the representation theory of an associated graded Hecke algebra. Since there is also an analogous root order, it is natural to hope that a similar bijection can be used to understand these regions. We show that such a bijection does hold for type H₃ and for type I₂(m), including arbitrary ratio of root lengths when m is even, but does not hold for type H₄. We give a criterion that explains this failure and a list of the 16 antichains in the H₄ root order which correspond to empty regions.     

On the enumeration of finite maximal connected topologies

A connected topology $\text{T}$ is said to be maximal connected if $\text{U}$ strictly finer than $\text{T}$ implies that $\text{U}$ is disconnected. In this paper, it is shown that the number of homeomorphism classes of maximal connected topologies defined on a set with n points is equal to twice the number of n point trees minus the number of n point trees possessing a symmetry line. An enumeration of a class called critical connected topologies, which includes the maximal connected spaces is then carried out with the help of Pólya's theorem. Another result is that a chain of connected n point T₀ topologies, linearly ordered by strict fineness, can contain a maximum of $\text{1}\text{2}\text{(n}{}^2\text{? 3n + 4)}$ topologies, and, moreover, this number is the best possible upper bound for the length of such a chain.     

On arrangements of roots for a real hyperbolic polynomial and its derivatives

In this paper we count the number ?_n^(0,k), k?n−1, of connected components in the space Δ_n^(0,k) of all real degree n polynomials which a) have all their roots real and simple; and b) have no common root with their kth derivatives. In this case, we show that the only restriction on the arrangement of the roots of such a polynomial together with the roots of its kth derivative comes from the standard Rolle's theorem. On the other hand, we pose the general question of counting all possible root arrangements for a polynomial p(x) together with all its nonvanishing derivatives under the assumption that the roots of p(x) are real. Already the first nontrivial case n=4 shows that the obvious restrictions coming from the standard Rolle's theorem are insufficient. We prove a generalized Rolle's theorem which gives an additional restriction on root arrangements for polynomials.     

New higher order methods for solving nonlinear equations with multiple roots

For a nonlinear equation f(x)=0 having a multiple root we consider Steffensen’s transformation, T. Using the transformation, say, F_q(x)=T^qf(x) for integer q≥2, repeatedly, we develop higher order iterative methods which require neither derivatives of f(x) nor the multiplicity of the root. It is proved that the convergence order of the proposed iterative method is 1+2^q−2 for any equation having a multiple root of multiplicity m≥2. The efficiency of the new method is shown by the results for some numerical examples.     

The Harmonious Chromatic Number of Deep and Wide Complete n- ary Trees

The harmonious chromatic number of a graph G is the least number of colors which can be used to color V(G) such that adjacent vertices are colored differently and no two edges have the same color pair on their vertices. Unsolved Problem 17.5 of Graph Coloring Problems by Jensen and Toft asks for the harmonious chromatic number of T_m,n the complete n-ary tree on m levels. Let q be the number of edged of T_m,n and k be the smallest positive integer such that the binomial coefficient C(k, 2) ≥ q. We show that for all sufficiently large m, n, the harmonious chromatic number of T_m,n is at most k + 1, and that many such T_m,n have harmonious chromatic number k.     

Numerical solution of algebraic fuzzy equations with crisp variable by Gauss–Newton method

In this paper we introduce an algebraic fuzzy equation of degree n with fuzzy coefficients and crisp variable, and we present an iterative method to find the real roots of such equations, numerically. We present an algorithm to generate a sequence that can be converged to the root of an algebraic fuzzy equation.     

Maximum Distance Between Slater Orders and Copeland Orders of Tournaments

Given a tournament T?=?(X, A), we consider two tournament solutions applied to T: Slater’s solution and Copeland’s solution. Slater’s solution consists in determining the linear orders obtained by reversing a minimum number of directed edges of T in order to make T transitive. Copeland’s solution applied to T ranks the vertices of T according to their decreasing out-degrees. The aim of this paper is to compare the results provided by these two methods: to which extent can they lead to different orders? We consider three cases: T is any tournament, T is strongly connected, T has only one Slater order. For each one of these three cases, we specify the maximum of the symmetric difference distance between Slater orders and Copeland orders. More precisely, thanks to a result dealing with arc-disjoint circuits in circular tournaments, we show that this maximum is equal to n(n???1)/2 if T is any tournament on an odd number n of vertices, to (n ²???3n?+?2)/2 if T is any tournament on an even number n of vertices, to n(n???1)/2 if T is strongly connected with an odd number n of vertices, to (n ²???3n???2)/2 if T is strongly connected with an even number n of vertices greater than or equal to 8, to (n ²???5n?+?6)/2 if T has an odd number n of vertices and only one Slater order, to (n ²???5n?+?8)/2 if T has an even number n of vertices and only one Slater order.     

Polynomial root radius optimization with affine constraints

The root radius of a polynomial is the maximum of the moduli of its roots (zeros). We consider the following optimization problem: minimize the root radius over monic polynomials of degree n, with either real or complex coefficients, subject to k linearly independent affine constraints on the coefficients. We show that there always exists an optimal polynomial with at most \(k-1\) inactive roots, that is, roots whose moduli are strictly less than the optimal root radius. We illustrate our results using some examples arising in feedback control.     

A Refinement of Weak Order Intervals into Distributive Lattices

In this paper we consider arbitrary intervals in the left weak order on the symmetric group S _n . We show that the Lehmer codes of permutations in an interval form a distributive lattice under the product order. Furthermore, the rank-generating function of this distributive lattice matches that of the weak order interval. We construct a poset such that its lattice of order ideals is isomorphic to the lattice of Lehmer codes of permutations in the given interval. We show that there are at least ${\left(\lfloor {\frac{n}{2}} \rfloor \right)!}$ permutations in S _n that form a rank-symmetric interval in the weak order.     

Computing iterative roots of polygonal functions

Based on the iterative root theory for monotone functions, an algorithm for computing polygonal iterative roots of increasing polygonal functions was given by J. Kobza. In this paper we not only give an algorithm for roots of decreasing polygonal functions but also generalize Kobza's results to the general n. Furthermore, we extend our algorithms for polygonal PM functions, a class of non-monotonic functions.     

Su una classe di procedimenti iterativi per la risoluzione di equazioni funzionali e applicazioni

Summary In this paper, we study a class of iterative processes of the type z_n=T_nz_n, which approximate the iterative processes x_n+1=Tx_n, where T and T_n are more general operators than contractions in a metric space.

---

---

Lavoro eseguito in relazione al Contratto N^o 115.3050.0.5189 del Comitato per la Matematica del C.N.R. nel corso dell'anno accademico 1968–69.

---

Entrata in Redazione il 25 luglio 1969.