Geometrical solutions of some quadratic equations with non-real roots

This note gives geometrical/graphical methods of finding solutions of the quadratic equation ax ² + bx + c = 0, a p 0, with non-real roots. Three different cases which give rise to non-real roots of the quadratic equation have been discussed. In case I a geometrical construction and its proof for finding the solutions of the quadratic equation ax ² + bx + c = 0, a p 0, when a,b,c ] R, the set of real numbers, are presented. Case II deals with the geometrical solutions of the quadratic equation ax ² + bx + c = 0, a p 0, when b ] R, the set of real numbers; and a,c ] C, the set of complex numbers. Finally, the solutions of the quadratic equation ax ² + bx + c = 0, a p 0, when a,c ] R, the set of real numbers, and b ] C, the set of complex numbers, are presented in case III.     

On Bounding the Betti Numbers and Computing the Euler Characteristic of Semi-Algebraic Sets

In this paper we prove new bounds on the sum of the Betti numbers of closed semi-algebraic sets and also give the first single exponential time algorithm for computing the Euler characteristic of arbitrary closed semi-algebraic sets. Given a closed semi-algebraic set S R ^k defined as the intersection of a real variety, Q=0, deg(Q)≤d, whose real dimension is k', with a set defined by a quantifier-free Boolean formula with no negations with atoms of the form P _i =0, P _i ≥ 0, P _i ≤ 0, deg(P _i ) ≤ d, 1≤ i≤ s, we prove that the sum of the Betti numbers of S is bounded by s ^k' (O(d)) ^k . This result generalizes the Oleinik—Petrovsky—Thom—Milnor bound in two directions. Firstly, our bound applies to arbitrary unions of basic closed semi-algebraic sets, not just for basic semi-algebraic sets. Secondly, the combinatorial part (the part depending on s ) in our bound, depends on the dimension of the variety rather than that of the ambient space. It also generalizes the result in [4] where a similar bound is proven for the number of connected components. We also prove that the sum of the Betti numbers of S is bounded by s ^k' 2 ^{O(k2 m4)} in case the total number of monomials occurring in the polynomials in is m. Using the tools developed for the above results, as well as some additional techniques, we give the first single exponential time algorithm for computing the Euler characteristic of arbitrary closed semi-algebraic sets. Received September 9, 1997, and in revised form March 18, 1998, and October 5, 1998.     

Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions

The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions. Specifically, if S is a set of n points in general position in R ^d , the maximum complexity of its Voronoi diagram under the L _∞ metric, and also under a simplicial distance function, are both shown to be . The upper bound for the case of the L _∞ metric follows from a new upper bound, also proved in this paper, on the maximum complexity of the union of n axis-parallel hypercubes in R ^d . This complexity is , for d ≥ 1 , and it improves to , for d ≥ 2 , if all the hypercubes have the same size. Under the L ₁ metric, the maximum complexity of the Voronoi diagram of a set of n points in general position in R ³ is shown to be . We also show that the general position assumption is essential, and give examples where the complexity of the diagram increases significantly when the points are in degenerate configurations. (This increase does not occur with an appropriate modification of the diagram definition.) Finally, on-line algorithms are proposed for computing the Voronoi diagram of n points in R ^d under a simplicial or L _∞ distance function. Their expected randomized complexities are for simplicial diagrams and for L _∞ -diagrams. Received July 31, 1995, and in revised form September 9, 1997.     

Dynamics of landslide model with time delay and periodic parameter perturbations

In present paper, we analyze the dynamics of a single-block model on an inclined slope with Dieterich–Ruina friction law under the variation of two new introduced parameters: time delay T_d and initial shear stress μ. It is assumed that this phenomenological model qualitatively simulates the motion along the infinite creeping slope. The introduction of time delay is proposed to mimic the memory effect of the sliding surface and it is generally considered as a function of history of sliding. On the other hand, periodic perturbation of initial shear stress emulates external triggering effect of long-distant earthquakes or some non-natural vibration source. The effects of variation of a single observed parameter, T_d or μ, as well as their co-action, are estimated for three different sliding regimes: β < 1, β = 1 and β > 1, where β stands for the ratio of long-term to short-term stress changes. The results of standard local bifurcation analysis indicate the onset of complex dynamics for very low values of time delay. On the other side, numerical approach confirms an additional complexity that was not observed by local analysis, due to the possible effect of global bifurcations. The most complex dynamics is detected for β < 1, with a complete Ruelle–Takens–Newhouse route to chaos under the variation of T_d, or the co-action of both parameters T_d and μ. These results correspond well with the previous experimental observations on clay and siltstone with low clay fraction. In the same regime, the perturbation of only a single parameter, μ, renders the oscillatory motion of the block. Within the velocity-independent regime, β = 1, the inclusion and variation of T_d generates a transition to equilibrium state, whereas the small oscillations of μ induce oscillatory motion with decreasing amplitude. The co-action of both parameters, in the same regime, causes the decrease of block’s velocity. As for β > 1, highly-frequent, limit-amplitude oscillations of initial stress give rise to oscillatory motion. Also for β > 1, in case of perturbing only the initial shear stress, with smaller amplitude, velocity of the block changes exponentially fast. If the time delay is introduced, besides the stress perturbation, within the same regime, the co-action of T_d (T_d < 0.1) and small oscillations of μ induce the onset of deterministic chaos.     

How tangents solve algebraic equations, or a remarkable geometry of discriminant varieties

Let D_d,k denote the discriminant variety of degree d polynomials in one variable with at least one of its roots being of multiplicity ≥ k. We prove that the tangent cones to D_d,k span D_{d,k − 1} thus, revealing an extreme ruled nature of these varieties. The combinatorics of the web of affine tangent spaces to D_d,k in D_{d,k − 1} is directly linked to the root multiplicities of the relevant polynomials. In fact, solving a polynomial equation P(z) = 0 turns out to be equivalent to finding hyperplanes through a given point which are tangent to the discriminant hypersurface D_d,2. We also connect the geometry of the Viète map V_d: , given by the elementary symmetric polynomials, with the tangents to the discriminant varieties {D_d,k}.Various d-partitions {μ} provide a refinement {D^o_μ} of the stratification of by the D_d,k's. Our main result, Theorem 7.1, describes an intricate relation between the divisibility of polynomials in one variable and the families of spaces tangent to various strata {D^o_μ}.     

On the variances of a spatial unit root model*

Asymptotic properties of the variances of the spatial autoregressive model X _k,ℓ = αX _k−1,ℓ + βX _k,ℓ−1 + γX _{k−1,ℓ−1} + ε _k,ℓ are investigated in the unit root case, that is, where the parameters are on the boundary of the domain of stability that forms a tetrahedron in [−1, 1]³. The limit of the variance of n ^−ϱ X _[ns],[nt] is determined, where ϱ = 1/4 on the interior of the faces of the domain of stability, ϱ = 1/2 on the edges, and ϱ = 1 on the vertices.     

The geometry of products of minors

We consider the Newton polytope Σ(m,n) of the product of all minors of an m× n matrix of indeterminates. Using the fact that this polytope is the secondary polytope of the product Δ _m-1 ×Δ _n-1 of simplices, and thus has faces corresponding to coherent polyhedral subdivisions of Δ _m-1 ×Δ _n-1 , we study facets of Σ(m,n) , which correspond to the coarsest, nontrivial such subdivisions. We make use of the relation between secondary and fiber polytopes, which in this case gives a representation of Σ(m,n) as the Minkowski average of all m × n transportation polytopes. <lsiheader> <onlinepub>7 August, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>20n2p231.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>no <sectionname> </lsiheader> Received August 7, 1996, and in revised form April 4, 1997.     

The structure of the set of satisfying assignments for a random <Emphasis Type="Italic">k</Emphasis>-CNF

Let F _k (n, m) be a random k-CNF obtained by a random, equiprobable, and independent choice of m brackets from among all k-literal brackets on n variables. We investigate the structure of the set of satisfying assignments of F _k (n, m). A method is proposed for finding r(k, s)such that the probability of presence of ns-dimensional faces (0 < s < 1) in the set of satisfying assignments of the formula F _k s(n, r(k, s)n) goes to 1 as n goes to infinity. We prove the existence of a sequential threshold for the property of having ns-dimensional faces (0 < s < 1). In other words, there exists a sequence r _n (k, s) such that the probability of having an ns-dimensional face in the set of satisfying assignments of the formula F _k (n, r _n (k, s)(1 + d)n) goes to 0 for all d > 0 and to 1 for all d < 0. __________ Translated from Prikladnaya Matematika i Informatika, No. 26, pp. 61–95, 2007.     

On Point Sets with Many Unit Distances in Few Directions

We study the problem of the maximum number of unit distances among n points in the plane, under the additional restriction that we count only those unit distances that occur in a fixed set of k directions, taking the maximum over all sets of n points and all sets of k directions. We prove that, for fixed k and sufficiently large n > n ₀ (k) , the extremal sets are essentially sections of lattices, bounded by edges parallel to the k directions and of equal length. <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p355.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received January 10, 1997, and in revised form May 16, 1997.     

In between k -Sets, j -Facets, and i -Faces: (i ,j) - Partitions

   Abstract. Let S be a finite set of points in general position in R ^d . We call a pair (A,B) of subsets of S an (i,j) -partition of S if |A|=i , |B|=j and there is an oriented hyperplane h with S

On the commutativity of antiblocker diagrams under lift-and-project operators

The behavior of the disjunctive operator, defined by Balas, Ceria and Cornuéjols, in the context of the “antiblocker duality diagram” associated with the stable set polytope, QSTAB(G), of a graph and its complement, was first studied by Aguilera, Escalante and Nasini. The authors prove the commutativity of this diagram in any number of iterations of the disjunctive operator. One of the main consequences of this result is a generalization of the Perfect Graph Theorem under the disjunctive rank.In the same context, Lipták and Tunçel study the lift-and-project operators N₀, N and N₊ defined by Lovász and Schrijver. They find a graph for which the diagram does not commute in one iteration of the N₀- and N-operator. In connection with N₊, the authors implicitly suggest a similar result proving that if the diagram commutes in k=O(1) iterations, P=NP.In this paper, we give for any number of iterations, explicit proofs of the non commutativity of the N₀-, N- and N₊-diagram.In the particular case of the N₀- and N-operator, we find bounds for the ranks of the complements of line graphs (of complete graphs), which allow us to prove that the diagrams do not commute for these graphs.     

Convergence of an explicit finite volume scheme for first order symmetric systems

Summary.  This paper is devoted to the derivation of a O(h ^1/2) error estimate for the classical upwind, explicit in time, finite volume scheme for linear first order symmetric systems. Such a result already existed for the corresponding implicit in time finite volume scheme, since it can be interpreted as a particular case of the space-time discontinuous Galerkin method but the technique of proof, used in that case, does not extend to explicit schemes. The general framework, recently developed to analyse the convergence rate of finite volume schemes for non linear scalar conservation laws, can not be used either, because it is not adapted for systems, even linear. In this article, we propose a new technique, which takes advantage of the linearity of the problem. The first step consists in controlling the approximation error ∥u−u _h ∥ _L2 by an expression of the form <ν _h , g>−2<μ _h , gu>, where u is the exact solution, g is a particular smooth function, and μ _h , ν _h are some linear forms depending on the approximate solution u _h . The second step consists in carefully estimating the error terms <μ _h , gu> and <ν _h , g>, by using uniform stability results for the discrete problem and regularity properties of the continuous solution. Received December 20, 2001 / Revised version received January 2, 2001 / Published online November 27, 2002 Mathematics Subject Classification (1991): 65N30     

Kinematics of Mechanisms to the Second Order – Application to the Closed Mechanisms

The degree of freedom of a closed mechanism is the dimension of a subset M of R ⁿ , M being the inverse image of the unity by the closure function f : (q ₁, ..., q _n ) f(q ₁, ..., q _n ), where q ₁, ..., q _n are the articular coordinates. We first study the regular points for the mapping f from R ⁿ into the Lie group of displacements and, second, study the singularities of the mapping f. The classical theory of mechanisms considers, often implicitly, that f is a subimmersion. Here, the calculations are made in a larger case, up to second order, and the results are then slightly different. The case of such classical mechanisms as Bennett, Bricard, and Goldberg mechanisms, justify the considerations of this more general framework and the example of a Bricard mechanism is chosen as an application of the method.     

On the Rate of Approximation of Closed Jordan Curves by Lemniscates

As proved by Hilbert, it is, in principle, possible to construct an arbitrarily close approximation in the Hausdorff metric to an arbitrary closed Jordan curve Γ in the complex plane {z} by lemniscates generated by polynomials P(z). In the present paper, we obtain quantitative upper bounds for the least deviations H _n (Γ) (in this metric) from the curve Γ of the lemniscates generated by polynomials of a given degree n in terms of the moduli of continuity of the conformal mapping of the exterior of Γ onto the exterior of the unit circle, of the mapping inverse to it, and of the Green function with a pole at infinity for the exterior of Γ. For the case in which the curve Γ is analytic, we prove that H _n (Γ) = O(q _n ), 0 ≤ q = q(Γ) < 1, n → ∞.__________Translated from Matematicheskie Zametki, vol. 77, no. 6, 2005, pp. 861–876.Original Russian Text Copyright ©2005 by O. N. Kosukhin.     

p-Adic dynamical systems of Chebyshev polynomials

We study the behaviour of the iterates of the Chebyshev polynomials of the first kind in p-adic fields. In particular, we determine in the field of complex p-adic numbers for p > 2, the periodic points of the p-th Chebyshev polynomial of the first kind. These periodic points are attractive points. We describe their basin of attraction. The classification of finite field extensions of the field of p-adic numbers ? _p , enables one to locate precisely, for any integer ν ≥ 1, the ν-periodic points of T _p : they are simple and the nonzero ones lie in the unit circle of the unramified extension of ? _p , (p > 2) of degree ν. This generalizes a result, stated by M. Zuber in his PhD thesis, giving the fixed points of T _p in the field ? _p , (p > 2). As often happens, we consider separately the case p = 2. Also, if the integer n ≥ 2 is not divisible by p, then any fixed point w of T _n is indifferent in the field of p-adic complex numbers and we give for p ≥ 3, the p-adic Siegel disc around w.     

A pure quantum mechanical theory of parity effect in tunneling and evolution of spins

In recent years, the spin parity effect in magnetic macroscopic quantum tunneling has attracted extensive attention. Using the spin coherent-state path-integral method it is shown that if the HamiltonianH of a single-spin system hasM - fold rotational symmetry around z-axis, the tunneling amplitude 〈−S|e ^Ht |S〉 vanishes when S, the quantum number of spin, is not an integer multiple ofM/2, where |m〉 (m=-S, -S +1, ⋯, S) are the eigenstates of S^z. Not only is a pure quantum mechanical approach adopted to the above result, but also is extended to more general cases where the quantum system consists ofN spins, the quantum numbers of which can take any values, including the single-spin system, ferromagnetic particle and antiferromagnetic particle as particular instances, and where the states involved are not limited to the extreme ones. The extended spin parity effect is that if the Hamiltonian ℋ of the system ofN spins also has the above symmetry, then 〈m′_N⋯m′₂ m′₁|e^{−H t} |m ₁ m ₂⋯m _N vanishes when ∑ _i=1 ^N (m _i−m′₁) not an integer multiple ofM, where |m ₁ m ₂⋯m _N〉=∏ _α=1 ^N |m _a 〉 are the eigenstates of S _a ^z . In addition, it is argued that for large spin the above result, the so-called spin parity effect, does not mean the quenching of spin tunneling from the direction of ⊕-z to that of ±z. Project supported by the National Natural Science Foundation of China (Grant Nos. 19674002, 19677101).     

Ascents of size less than <Emphasis Type="Italic">d</Emphasis> in compositions

A composition of a positive integer n is a finite sequence π₁π₂...π _m of positive integers such that π₁+...+π _m = n. Let d be a fixed number. We say that we have an ascent of size d or more (respectively, less than d) if π _i+1 ≥ π _i +d (respectively, π _i < π _i+1 < π _i + d). Recently, Brennan and Knopfmacher determined the mean, variance and limiting distribution of the number of ascents of size d or more in the set of compositions of n. In this paper, we find an explicit formula for the multi-variable generating function for the number of compositions of n according to the number of parts, ascents of size d or more, ascents of size less than d, descents and levels. Also, we extend the results of Brennan and Knopfmacher to the case of ascents of size less than d. More precisely, we determine the mean, variance and limiting distribution of the number of ascents of size less than d in the set of compositions of n.     

Nonsingularity of the difference and the sum of two idempotent matrices

Groß and Trenkler 1 pointed out that if a difference of idempotent matrices P and Q is nonsingular, then so is their sum, and Koliha et al2 expressed explicitly a condition, which combined with the nonsingularity of P+Q ensures the nonsingularity of P-Q. In the present paper, these results are strengthened by showing that the nonsingularity of P-Q is in fact equivalent to the nonsingularity of any combination aP+bQ-cPQ (where a≠0,b≠0,a+b=c), and the nonsingularity of P+Q is equivalent to the nonsingularity of any combination aP+bQ-cPQ (where a≠0,b≠0,a+b≠c).     

The Lyapunov matrix equation SA+A1S=S1B1BS

The matrix equation $\text{SA+A}{}^1\text{S=S}{}^1\text{B}{}^1\text{BS}$ is studied, under the assumption that (A, B¹) is controllable, but allowing nonhermitian S. An inequality is given relating the dimensions of the eigenspaces of A and of the null space of S. In particular, if B has rank 1 and S is nonsingular, then S is hermitian, and the inertias of A and S are equal. Other inertial results are obtained, the role of the controllability of (A¹, B¹S¹) is studied, and a class of D-stable matrices is determined.