Ergodic properties of the Erdös measure, the entropy of the goldenshift, and related problems

We define a two-sided analog of the Erdös measure on the space of two-sided expansions with respect to the powers of the golden ratio, or, equivalently, the Erdös measure on the 2-torus. We construct the transformation (goldenshift) preserving both Erdös and Lebesgue measures on that is the induced automorphism with respect to the ordinary shift (or the corresponding Fibonacci toral automorphism) and proves to be Bernoulli with respect to both measures in question. This provides a direct way to obtain formulas for the entropy dimension of the Erdös measure on the interval, its entropy in the sense of Garsia-Alexander-Zagier and some other results. Besides, we study central measures on the Fibonacci graph, the dynamics of expansions and related questions.With 11 PiguresTo the memory of Paul ErdösSupported in part by the INTAS grant 93-0570. The first author was supported by the French foundation PRO MATHEMATICA. The first author expresses his gratitude to l'Institut de Mathématiques de Luminy for support during his stay in Marseille in 1996-97. The second author is grateful to the University of Stony Brook for support during his visit in February–March 1996 and to the Institute for Advanced studies of Hebrew University for support during his being there in 1997     

Homology of the double and the triple loop spaces¶of E6, E7, and E8

We study the mod p homology of the double and the triple loop spaces of exceptional Lie groups E ₆, E ₇, and E ₈ through the Eilenberg–Moore spectral sequence and the Serre spectral sequence using homology operations. The Bockstein actions on them are also determined. As a result, the Eilenberg–Moore spectral sequences of the path loop fibrations converging to H _*(Ω² G;? _p ) and H _*(Ω³ G;? _p ) collapse at the E ²-term for any compact simple Lie group G. Received: 11 November 1999     

On universal and periodic β-expansions,and the Hausdorff dimension of the set of all expansions

We study the topology of a set naturally arising from the study of β-expansions. After proving several elementary results for this set we study the case when our base is Pisot. In this case we give necessary and sufficient conditions for this set to be finite. This finiteness property will allow us to generalise a theorem due to Schmidt and will provide the motivation for sufficient conditions under which the growth rate and Hausdorff dimension of the set of β-expansions are equal and explicitly calculable.     

Fredman’s reciprocity,invariants of abelian groups,and the permanent of the Cayley table

Let C_n{\mathcal{C}}_{n} denote the cyclic group of order n. For G=C_nG={\mathcal{C}}_{n}, we compute the Poincaré series of all C_n{\mathcal{C}}_{n}-isotypic components in (the symmetric tensor exterior algebra of ). From this we derive a general reciprocity and some number-theoretic identities. This generalises results of Fredman and Elashvili–Jibladze. Then we consider the Cayley table, , of G and some generalisations of it. In particular, we prove that the number of formally different terms in the permanent of equals , where n is the order of G.     

Lehmer pairs of zeros,the de Bruijn-Newman constant Λ, and the Riemann Hypothesis

We give here a rigorous formulation for a pair of consecutive simple positive zeros of the functionH ₀ (which is closely related to the Riemann -function) to be a Lehmer pair of zeros ofH ₀. With this formulation, we establish that each such pair of zeros gives a lower bound for the de Bruijn-Newman constant (where the Riemann Hypothesis is equivalent to the assertion that 0). We also numerically obtain the following new lower bound for :

Spaces of Operators,the ψ-Daugavet Property,and Numerical Indices

Suppose ψ : [0, ∞) → [1, ∞) is a strictly increasing function. A Banach space X is said to have the ψ-Daugavet Property if the inequality holds for every compact operator T : X → X. We show that, if 1 < p < ∞ and K(ℓ_p)↪ X ↪ B(ℓ_p), then X has the ψ-Daugavet Property with (here and c_p is an absolute constant). We also prove that a C^*-algebra A is commutative if and only if for any . Together, these results allow us to distinguish between some types of von Neumann algebras by considering spaces of operators on them. The author was supported in part by the NSF grant DMS-9970369.     

Multiparametric Families of Solutions of the Kadomtsev–Petviashvili-I Equation,the Structure of Their Rational Representations,and Multi-Rogue Waves

We construct solutions of the Kadomtsev–Petviashvili-I equation in terms of Fredholm determinants. We deduce solutions written as a quotient of Wronskians of order 2N. These solutions, called solutions of order N, depend on 2N?1 parameters. They can also be written as a quotient of two polynomials of degree 2N(N +1) in x, y, and t depending on 2N?2 parameters. The maximum of the modulus of these solutions at order N is equal to 2(2N + 1)². We explicitly construct the expressions up to the order six and study the patterns of their modulus in the plane (x, y) and their evolution according to time and parameters.     

A note on the principle of mathematical induction,intuition and consciousness in the light of ideas of Poincaré and Galois

In his argumentation for the non-computability of thought-processes (in general) Penrose is invoking Gödel’s theorem (see [R. Penrose, Shadows of the Mind – A search for the Missing Science of Consciousness, Oxford University Press, Oxford, 1994]). It is the aim with the following note to indicate that the same effect may be obtained in a simpler and possibly also more fundamental way. This does not necessarily mean that I fully believe in Penrose’s thesis – the question is still largely open – but I think that my note indicates that there are a lot of items that remains to be clarified before a satisfactory scientific consensus will be reached. There is a huge gap between the precision of strict scientific contexts and those where this kind of processes are going on. At the same time we will see that the same kind of ideas had been impinging themselves on mathematicians like Poincaré and Galois, like Penrose himself of a very intuitive kind. It is plausible that the solution of the enigma of the scientific character of processes referring back to themselves lies in deep properties of autonomous systems. The self-referential character of the interpretations in Gödel’s theorem is quite central. This will be the subject of a forthcoming paper.     

Multiplicities of Pfaffian intersections,and the Łojasiewicz inequality

An effective estimate for the local multiplicity of a complete intersection of complex algebraic and Pfaffian varieties is given, based on a local complex analog of the Rolle-Khovanskii theorem. The estimate is valid also for the properly defined multiplicity of a non-isolated intersection. It implies, in particular, effective estimates for the exponents of the polar curves, and the exponents in the ojasiewicz inequalities for Pfaffian functions. For the intersections defined by sparse polynomials, the multiplicities outside the coordinate hyperplanes can be estimated in terms of the number of non-zero monomials, independent of degrees of the monomials.     

An ODE’s Version of the Formula of Baker, Campbell, Dynkin and Hausdorff and the Construction of Lie Groups with Prescribed Lie Algebra

If ${\mathcal{L} = {\sum_{j=1}^m} {X_j^2} + X_0}If L = ?_j=1^m X_j² + X₀{\mathcal{L} = {\sum_{j=1}^m} {X_j^2} + X_0} is a H?rmander partial differential operator in \mathbbR^N{\mathbb{R}^N}, we give sufficient conditions on the vector fields X _j ’s for the existence of a Lie group structure \mathbbG = (\mathbbR^N, *){\mathbb{G} = (\mathbb{R}^N, *)} (and we exhibit its construction), not necessarily nilpotent nor homogeneous, such that L{\mathcal{L}} is left invariant on \mathbbG{\mathbb{G}}. The main tool is a formula of Baker-Campbell-Dynkin-Hausdorff type for the ODE’s naturally related to the system of vector fields {X ₀, . . . , X _m }. We provide a direct proof of this formula in the ODE’s context (which seems to be missing in literature), without invoking any result of Lie group theory, nor the abstract algebraic machinery usually involved in formulas of Baker-Campbell-Dynkin-Hausdorff type. Examples of operators to which our results apply are also furnished.     

On the geometry,preemptions and complexity of multiprocessor and shop scheduling

In this paper we study multiprocessor and open shop scheduling problems from several points of view. We explore a tight dependence of the polynomial solvability/intractability on the number of allowed preemptions. For an exhaustive interrelation, we address the geometry of problems by means of a novel graphical representation. We use the so-called preemption and machine-dependency graphs for preemptive multiprocessor and shop scheduling problems, respectively. In a natural manner, we call a scheduling problem acyclic if the corresponding graph is acyclic. There is a substantial interrelation between the structure of these graphs and the complexity of the problems. Acyclic scheduling problems are quite restrictive; at the same time, many of them still remain NP-hard. We believe that an exhaustive study of acyclic scheduling problems can lead to a better understanding and give a better insight of general scheduling problems. We show that not only acyclic but also a special non-acyclic version of periodic job-shop scheduling can be solved in polynomial (linear) time. In that version, the corresponding machine dependency graph is allowed to have a special type of the so-called parti-colored cycles. We show that trivial extensions of this problem become NP-hard. Then we suggest a linear-time algorithm for the acyclic open-shop problem in which at most m−2 preemptions are allowed, where m is the number of machines. This result is also tight, as we show that if we allow one less preemption, then this strongly restricted version of the classical open-shop scheduling problem becomes NP-hard. In general, we show that very simple acyclic shop scheduling problems are NP-hard. As an example, any flow-shop problem with a single job with three operations and the rest of the jobs with a single non-zero length operation is NP-hard. We suggest linear-time approximation algorithm with the worst-case performance of ( , respectively) for acyclic job-shop (open-shop, respectively), where (‖ℳ‖, respectively) is the maximal job length (machine load, respectively). We show that no algorithm for scheduling acyclic job-shop can guarantee a better worst-case performance than . We consider two special cases of the acyclic job-shop with the so-called short jobs and short operations (restricting the maximal job and operation length) and solve them optimally in linear time. We show that scheduling m identical processors with at most m−2 preemptions is NP-hard, whereas a venerable early linear-time algorithm by McNaughton yields m−1 preemptions. Another multiprocessor scheduling problem we consider is that of scheduling m unrelated processors with an additional restriction that the processing time of any job on any machine is no more than the optimal schedule makespan C _max^*. We show that the (2m−3)-preemptive version of this problem is polynomially solvable, whereas the (2m−4)-preemptive version becomes NP-hard. For general unrelated processors, we guarantee near-optimal (2m−3)-preemptive schedules. The makespan of such a schedule is no more than either the corresponding non-preemptive schedule makespan or max {C _max^*,p _max}, where C _max^* is the optimal (preemptive) schedule makespan and p _max is the maximal job processing time. E.V. Shchepin was partially supported by the program “Algebraical and combinatorial methods of mathematical cybernetics” of the Russian Academy of Sciences. N. Vakhania was partially supported by CONACyT grant No. 48433.     

Products of Distributions, Conservation Laws and the Propagation of δ -Shock Waves

This paper contains a study of propagation of singular travelling waves u(x,t)for conservation laws ut + [φ(u)]x =Ψ(u),where φ,Ψ are entire functions taking real values on the real axis.Conditions for ...     

An Analysis of the Dynamical Evolution of Experimental,Recreative and Abusive Marijuana Consumption in the States of Colorado and Washington Beyond the Implementation of I–502

We analyze the NERA model (N: Nonuser, E: Experimental Users, R: Recreational Users, A: Addicts), which describes the illicit drug usage dynamics in a population consisting of both drug users and nonusers. The model considers three categories of drug users: the experimental (E) category, the recreational (R) category and the addict(A) category. We prove the uniqueness and positivity of the solution to the model in time.

We extend the model by taking into account the unpredictability of person-to-person contacts and consider individuals susceptible to experience an illicit drug being subjected to a continuous spectrum of random factors. Based on the existence of such a randomness in the movement from nonuser to experimental users, we modify the model to set up a stochastic one. The latter model is also analyzed in the current work. We verify and validate our results by using the data available in Hanley (2013 Hanley, S. (2013). Legalization of recreational marijuana in Washington: Monitoring trends in use prior to the implementation of I–502. Retrieved from http://www.wsipp.wa.gov/ReportFile/1540/Wsipp Legalization-of-Recreational-Marijuana-in-Washington-Monitoring-Trends-in-Use-Prior-to-the-Implementation-of-I-502 Full-Report.pdf. [Google Scholar]), on the prevalence of marijuana in the population of 21+ in the states of Colorado and Washington. We simulate the evolution of the above mentioned categories of drug users within those two states from 2002, beyond the implementation of I–502 and until 2040. Our results show that the model can used as a policy decision mechanism in the problematic of illicit drug consumption by monitoring the respond of the different categories of drug users when subject to drug control interventions.     

On unfoldable cardinals, ω-closed cardinals,and the beginning of the inner model hierarchy

Let be a cardinal, and let H be the class of sets of hereditary cardinality less than ; let () > be the height of the smallest transitive admissible set containing every element of {}H. We show that a ZFC-definable notion of long unfoldability, a generalisation of weak compactness, implies in the core model K, that the mouse order restricted to H is as long as . (It is known that some weak large cardinal property is necessary for the latter to hold.) In other terms we delimit its strength as follows: TheoremCon(ZFC+²- ¹₁-Determinacy) Con(ZFC+V=K+ a long unfoldable cardinal Con(ZFC+X(X^# exists) + is universally Baire rR(DL(r))), and this is set-generically absolute). We isolate a notion of -closed cardinal which is weaker than an ₁-Erd\ os cardinal, and show that this bounds the first long unfoldable: Theorem Let be -closed. Then there is a long unfoldable <.Mathematics Subject Classification (2000): 03E45, 03E15, 03E55, 03E60The author wishes to gratefully acknowledge support from Nato Grant PST.CLG 975324.     

Distribution of zeros of the Hermite-Padé polynomials for a system of three functions,and the Nuttall condenser

The well-known approach of J. Nuttall to the derivation of strong asymptotic formulas for the Hermite-Padé polynomials for a set of m multivalued functions is based on the conjecture that there exists a canonical (in the sense of decomposition into sheets) m-sheeted Riemann surface possessing certain properties. In this paper, for m = 3, we introduce a notion of an abstract Nuttall condenser and describe a procedure for constructing (based on this condenser) a three-sheeted Riemann surface $\Re _3$ that has a canonical decomposition. We consider a system of three functions $\mathfrak{f}_1 ,\mathfrak{f}_2 ,\mathfrak{f}_3$ that are rational on the constructed Riemann surface and satisfy the independence condition det . In the case of m = 3, we refine the main theorem from Nuttall’s paper of 1981. In particular, we show that in this case the complement ?? \ B of the open (possibly, disconnected) set B ? ?? introduced in Nuttall’s paper consists of a finite number of analytic arcs. We also propose a new conjecture concerning strong asymptotic formulas for the Padé approximants.     

Functional Itô calculus,path-dependence and the computation of Greeks

Dupire’s functional Itô calculus provides an alternative approach to the classical Malliavin calculus for the computation of sensitivities, also called Greeks, of path-dependent derivatives prices. In this paper, we introduce a measure of path-dependence of functionals within the functional Itô calculus framework. Namely, we consider the Lie bracket of the space and time functional derivatives, which we use to classify functionals accordingly to their degree of path-dependence. We then revisit the problem of efficient numerical computation of Greeks for path-dependent derivatives using integration by parts techniques. Special attention is paid to path-dependent functionals with zero Lie bracket, called locally weakly path-dependent functionals in our classification. Hence, we derive the weighted-expectation formulas for their Greeks. In the more general case of fully path-dependent functionals, we show that, equipped with the functional Itô calculus, we are able to analyze the effect of the Lie bracket on the computation of Greeks. Moreover, we are also able to consider the more general dynamics of path-dependent volatility. These were not achieved using Malliavin calculus.     

Refinements of the β-core and the strong equilibrium and the Aumann proposition

The Aumann proposition establishes that an outcome in the -core of the one-shot gameG is the same as the strong equilibrium utility allocations of the associated supergame. We refine the -core by requiring that the threat strategies used to deter deviations be credible and examine the consequences for the Aumann proposition in the case of the refinement. We show that a refinement of the strong-equilibrium notion is always in the refined -core. The converse is not necessarily true unless the utility allocations are linear.I am grateful to T. Ichiishi for several discussions that helped in the development of this paper. This is part of the author's Ph.D. dissertation submitted at the university of Iowa in December 1985.     

Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz

For a graph G, let χ(G) denote its chromatic number and σ(G) denote the order of the largest clique subdivision in G. Let H(n) be the maximum of χ(G)=σ(G) over all n-vertex graphs G. A famous conjecture of Hajós from 1961 states that σ(G) ≥ χ(G) for every graph G. That is, H(n)≤1 for all positive integers n. This conjecture was disproved by Catlin in 1979. Erd?s and Fajtlowicz further showed by considering a random graph that H(n)≥cn ^1/2/logn for some absolute constant c>0. In 1981 they conjectured that this bound is tight up to a constant factor in that there is some absolute constant C such that χ(G)=σ(G) ≤ Cn ^1/2/logn for all n-vertex graphs G. In this paper we prove the Erd?s-Fajtlowicz conjecture. The main ingredient in our proof, which might be of independent interest, is an estimate on the order of the largest clique subdivision which one can find in every graph on n vertices with independence number α.