Noncomputability,unpredictability, undecidability,and unsolvability in economic and finance theories

We outline, briefly, the role that issues of the nexus between noncomputability and unpredictability, on the one hand, and between undecidability and unsolvability, on the other hand, have played in Computable Economics (CE). The mathematical underpinnings of CE are provided by (classical) recursion theory, varieties of computable and constructive analysis and aspects of combinatorial optimization. The inspiration for this outline was provided by Professor Graça's thought‐provoking recent article. © 2012 Wiley Periodicals, Inc. Complexity, 2012     

Algebra in Roth,Faulhaber, and Descartes

Descartes' “multiplicative” theory of equations in the Géométrie (1637) systematically treats equations as polynomials set equal to zero, bringing out relations between equations, roots, and polynomial factors. We here consider this theory as a response to Peter Roth's suggestions in Arithmetica Philosophica (1608), notably in his “seventh-degree” problem set. These specimens of arithmetic-masterly problem design develop skills with multiplicative and other degree-independent techniques. The challenges were fine-tuned by introducing errors disguised as printing errors. During Descartes' visit to Germany in 1619–1622, he probably worked with Johann Faulhaber (1580–1635) on these problems; they are discussed in Faulhaber's Miracula Arithmetica (1622), which also looks forward to fuller publication, probably by Descartes.     

Paths,cycles, and arc-connectivity in digraphs

In this paper we prove the following theorem: Let D be a k-arcconnected digraph (multiple arcs allowed). If x is a vertex of D and / is an integer with / ≤ k, then for any / disjoint arc pairs {f₁, g₁}, ?, {f₁, g₁}, where f₁, ?, f₁ are arcs with head at x and g₁, ?, g₁ are arcs with tail at x, there exist in D / arc-disjoint cycles C₁, ?, C₁ such that {f_i, g_i} ? E(C_i) for each i (E(C_i) denotes the arc set of C_i) and such that D - ∪ E(C_i) is (k - 1)-arc-connected. Several interesting results are deduced from this theorem. Our results generalize the early works of Mader (“On a Property of n-Edge-Connected Digraphs,” Combinatorica, vol. 1 [1981], pp. 385-386) and Shiloach (“Edge-Disjoint Branching in Directed Multigraphs,” Information Processing Letters, vol. 8 [1979], pp. 24-27). An extension of Mader's theorem about admissible liftings of digraphs is also obtained in this paper. © 1995 John Wiley & Sons, Inc.     

Switchings, extensions, and reductions in central digraphs

A directed graph is called central if its adjacency matrix A satisfies the equation A²=J, where J is the matrix with a 1 in each entry. It has been conjectured that every central directed graph can be obtained from a standard example by a sequence of simple operations called switchings, and also that it can be obtained from a smaller one by an extension. We disprove these conjectures and present a general extension result which, in particular, shows that each counterexample extends to an infinite family.     

Singularities, Shocks, and Instabilities in Interface Growth

Two-dimensional interface motion is examined in the setting of geometric crystal growth. We focus on the relationships between local curvature and global shape evolution displaying the dual role of singularities and shocks depending on the parameterization of the curve—the crystal surface. Discontinuities in surface slope accompany regions of asymptotically decreasing curvature during transient growth, whereas an absence of discontinuities preempts such asymptotic curvature evolution. In one parameterization, these discontinuities manifest themselves as a finite-time continuous blowup of curvature, and in another, as a shock and hence a localized divergence of curvature. Previously, it has been conjectured, based on numerical evidence, that the minimum blowup time is preempted by shock formation. We prove this conjecture in the present paper. Additionally we prove that a class of local geometric models preserves the convexity of the surface. These results are connected to experiments on crystal growth.     

Eigenvalues,geometric expanders,sorting in rounds,and ramsey theory

Expanding graphs are relevant to theoretical computer science in several ways. Here we show that the points versus hyperplanes incidence graphs of finite geometries form highly (nonlinear) expanding graphs with essentially the smallest possible number of edges. The expansion properties of the graphs are proved using the eigenvalues of their adjacency matrices. These graphs enable us to improve previous results on a parallel sorting problem that arises in structural modeling, by describing an explicit algorithm to sortn elements ink time units using parallel processors, where, e.g., α₂=7/4, α₃=8/5, α₄=26/17 and α₅=22/15. Our approach also yields several applications to Ramsey Theory and other extremal problems in combinatorics.     

Observation,Measurement, and Computation in Finite Games

Limitations in agents ability to observe, measure and compute are studied. A formulation in terms of induced changes in the players subjective perception of the game makes it possible to study these phenomena on a common footing with objective variation in the game. We study a model where payoffs undergo continuous variation and players reason about the process from limited local information. Specifically, finite games, and statements about them, are interpreted within sheaf models, which incorporate both variation and a logic of limited observation. Nashs theorem on the existence of equilibrium is not valid unless special observational properties hold, although closely related statements are valid. The possibility of learning to play a mixed strategy Nash equilibrium from observation of past play is also examined within the framework.I thank the referee and associate editor for their comments and suggestions. I also received very helpful suggestions from Josh Epstein. All remaining errors are my own.Received: April 2000 / Revised: December 2003     

Probability, geometry, and irreversibility in quantum mechanics

The main conclusion of this paper is that the Bell–Wigner–Accardi theory of quantum probabilities in spin systems may be placed within the general operator trigonometry developed independently by this author about 30 years ago. The use of the Grammian from the operator trigonometry simplifies and clarifies the analysis of Wigner. A general triangle inequality from the operator trigonometry clarifies and generalizes the analysis of Accardi. The statistical meaning of the complex numbers in quantum mechanics is seen to be that of the natural geometry of the operator trigonometry. A new connection of the operator trigonometry to CP symmetry violation is established.     

Eigenvalues,diameter, and mean distance in graphs

It is well-known that the second smallest eigenvalue ₂ of the difference Laplacian matrix of a graphG is related to the expansion properties ofG. A more detailed analysis of this relation is given. Upper and lower bounds on the diameter and the mean distance inG in terms of ₂ are derived.This work was supported in part by the Research Council of Slovenia, Yugoslavia. A part of the work was done while the author was visiting the Ohio State University, supported by a Fulbright grant.     

Properness,strictness, and nilness in jordan systems

The basic theme of this paper, suggested by Ottmar Loos, is to show that certain sets S ofelements in a Jordan system J form an ideal by showing that S = J∩R([Jtilde]) is the Amitsur shrinkage of some well-knownl radical R on some extension [Jtilde] of J. The Jacobson radical Rad(J) and the degenerate radical Deg(J) have elemental characterizations as (respectively) the properly quasi-invertible elements and the m-finite elements. Frojn these two characterizations we show that: (1) the strictly properly nilpotent elements coincide with the strictly properly quasi-invertible elements and form the ideal J∩Rad(J[T]) (2) the strictly m-finite elements coincide with the m-finite elements and form the ideal Deg:(J) (3) the m-bounded elements form an ideal J ∩ Deg(Seq(J)) (Seq the algebra of sequences); and (4) the strictly m-bounded elements coincide with the strictly properly nilpotence-bounded elements and form the ideal J ∩ Deg(Seq(J[t])). We show that all these constructions are stable under structural pairs, a useful generalization of the concept of structural transformation. The question of whether the properly nilpotent elements form an ideal, and if so whether this is the nil radical, is an open question intimately related to the Kothe Conjecture for associative algebras.     

Optimality,stability, and convergence in nonlinear control

Sufficient optimality conditions for infinite-dimensional optimization problems are derived in a setting that is applicable to optimal control with endpoint constraints and with equality and inequality constraints on the controls. These conditions involve controllability of the system dynamics, independence of the gradients of active control constraints, and a relatively weak coercivity assumption for the integral cost functional. Under these hypotheses, we show that the solution to an optimal control problem is Lipschitz stable relative to problem perturbations. As an application of this stability result, we establish convergence results for the sequential quadratic programming algorithm and for penalty and multiplier approximations applied to optimal control problems.This research was supported by the U.S. Army Research Office under Contract. Number DAAL03-89-G-0082, by the National Science Foundation under Grant Number DMS 9404431, and by Air Force Office of Scientific Research under Grant Number AFOSR-88-0059. A. L. Dontchev is on leave from the Institute of Mathematics, Bulgarian Academy of Sciences, Sofia, Bulgaria.