Light affine lambda calculus and polynomial time strong normalization

Light Linear Logic (LLL) and Intuitionistic Light Affine Logic (ILAL) are logics that capture polynomial time computation. It is known that every polynomial time function can be represented by a proof of these logics via the proofs-as-programs correspondence. Furthermore, there is a reduction strategy which normalizes a given proof in polynomial time. Given the latter polynomial time “weak” normalization theorem, it is natural to ask whether a “strong” form of polynomial time normalization theorem holds or not. In this paper, we introduce an untyped term calculus, called Light Affine Lambda Calculus (λLA), which corresponds to ILAL. λLA is a bi-modal λ-calculus with certain constraints, endowed with very simple reduction rules. The main property of LALC is the polynomial time strong normalization: any reduction strategy normalizes a given λLA term in a polynomial number of reduction steps, and indeed in polynomial time. Since proofs of ILAL are structurally representable by terms of λLA, we conclude that the same holds for ILAL. This is a full version of the paper [21] presented at LICS 2001.     

Global Minimization of a Multivariate Polynomial using Matrix Methods

The problem of minimizing a polynomial function in several variables over R ⁿ is considered and an algorithm is given. When the polynomial has a minimum the algorithm returns the global minimal value and finds at least one point in every connected component of the set of minimizers. A characterization of such points is given. When the polynomial does not have a minimum the algorithm computes its infimum. No assumption is made on the polynomial.     

Finitely Generated PI-Superalgebras with Bounded Multiplicities of the Cocharacters

ABSTRACT

In this note, we characterize finitely generated superalgebras satisfying an ordinary polynomial identity whose multiplicities of the supercocharacters are bounded by a constant.     

Finite polynomial orbits in quadratic rings

All finite orbits of polynomial mappings in one variable in rings of integers of quadratic number fields are determined. The largest such orbit has seven elements and lies in the third cyclotomic field. 2000 Mathematics Subject Classification Primary—11R09, 11R11, 37F10     

Polynomial time algorithms for some classes of constrained nonconvex quadratic problems

In this paper we consider different classes of noneonvex quadratic problems that can be solved in polynomial time. We present an algorithm for the problem of minimizing the product of two linear functions over a polyhedron P in R ⁿ The complexity of the algorithm depends on the number of vertices of the projection of P onto the R ² space. In the worst-case this algorithm requires an exponential number of steps but its expected computational time complexity is polynomial. In addition, we give a characterization for the number of isolated local minimum areas for problems on this form.

Furthermore, we consider indefinite quadratic problems with variables restricted to be nonnegative. These problems can be solved in polynomial time if the number of negative eigenvalues of the associated symmetric matrix is fixed.     

Polynomial Processes for Power Prices

ABSTRACT

Polynomial processes have the property that expectations of polynomial functions (of degree n, say) of the future state of the process conditional on the current state are given by polynomials (of degree ≤ n) of the current state. Here we explore the potential of polynomial maps of polynomial processes for modelling energy prices. We focus on the example of Alberta power prices, derive one- and two-factor models for spot prices. We examine their performance in numerical experiments, and demonstrate that the richness of the dynamics they are able to generate makes them well suited for modelling even extreme examples of energy price behaviour.     

The Hardness of Polynomial Equation Solving

Elimination theory was at the origin of algebraic geometry in the nineteenth century and now deals with the algorithmic solving of multivariate polynomial equation systems over the complex numbers or, more generally, over an arbitrary algebraically closed field. In this paper we investigate the intrinsic sequential time complexity of universal elimination procedures for arbitrary continuous data structures encoding input and output objects of elimination theory (i.e., polynomial equation systems) and admitting the representation of certain limit objects. Our main result is the following: let there be given such a data structure and together with this data structure a universal elimination algorithm, say P, solving arbitrary parametric polynomial equation systems. Suppose that the algorithm P avoids unnecessary branchings and that P admits the efficient computation of certain natural limit objects (as, e.g., the Zariski closure of a given constructible algebraic set or the parametric greatest common divisor of two given algebraic families of univariate polynomials). Then P$ cannot be a polynomial time algorithm. The paper contains different variants of this result and discusses their practical implications.     

Function Algebras on Disks

For a small closed disk D in the complex plane the uniform closure A in C ( D ) of the polynomials in z 2 and a second function of the form f 2 , with f behaving as [zbar], is considered. It has been shown before, using theory of polynomial convexity, that A p C ( D ) for some choices of f , while for other choices of f the situation A = C ( D ) can occur. A new class of functions f is presented for which A = C ( D ).     

On Certain Fejér and Tchebychev Type Integrals

Let m and n denote a pair of positive integers. In this paper, we call upon the Hadamard product and computer algebra techniques to evaluate the Fejér integral π ^?1 ∫₀ ^π (sin mθ / sin θ) ²ⁿ dθ. Using symmetry arguments, it is proved that the value of this integral is an odd polynomial in m of degree 2n ? 1. This permits using polynomial curve fitting methods and mathematical software packages to obtain evaluation formulas for n relatively small. Some cases of the above integral with 2n replaced by 2n + 1 are also discussed. A familiar identity shows that these yield evaluations of integrals of powers of certain Tchebychev polynomials.     

A New Functor from E 6-mod to E 7-mod

We find a new representation of the simple Lie algebra of type E ₇ on the polynomial algebra in 27 variables. Using this representation and Shen's idea of mixed product, we construct a new functor from E ₆-Mod to E ₇-Mod. A condition for the functor to map a finite-dimensional irreducible E ₆-module to an infinite-dimensional irreducible E ₇-module is obtained. Our general framework also gives a direct polynomial extension from irreducible E ₆-modules to irreducible E ₇-modules, which can be used to derive Gel'fand–Zetlin bases for E ₇ from those for E ₆ that can be obtained from those for D ₅ according to our earlier work.     

The Zeros and the Final Value of a Polynomial Form

ABSTRACT

A polynomial form f, is a not necessarily linear map, from an infinite module over a ring 𝔷 to a finite abelian group of exponent n satisfying some additional conditions. Denote the zeros of f by Ω_f. We show it satisfies a weak closure condition. Among all 𝔷-submodules of finite index, there is a submodule B such that |f (B)| (the order of the subset f (B)) is as small as possible. f (B) is called the final value of f and D. S. Passman asks if f (B) is necessarily a subgroup of S. This paper shows that if the degree of f ≤ 2 then the final value is a subgroup and if the form f has arbitrary degree from an finitely generated infinite abelian group, then the final value is 0.     

Polynomial Pell's equation-II

The polynomial Pell's equation is X²−DY²=1, where D is a polynomial with integer coefficients and the solutions X,Y must be polynomials with integer coefficients. Let D=A²+2C be a polynomial in , where . Then for a prime, a necessary and sufficient condition for which the polynomial Pell's equation has a nontrivial solution is obtained. Furthermore, all solutions to the polynomial Pell's equation satisfying the above condition are determined.     

Polynomial Rings Over Symmetric Rings Need Not be Symmetric

Let R be a ring with identity. The polynomial ring over R is denoted by R[x] with x its indeterminate. It is shown that polynomial rings over symmetric rings need not be symmetric by an example.     

ACCP Rises to the Polynomial Ring if the Ring has Only Finitely Many Associated Primes

Abstract

We show for a commutative ring R with unity: If R satisfies the ascending chain condition on principal ideals (accp) and has only finitely many associated primes, then for any set of indeterminates X the polynomial ring R[X] also satisfies accp. Further we show that accp rises to the power series ring R[[X]] if R satisfies accp and the ascending chain condition on annihilators.     

An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems Over Symmetric Cones

This paper is based on a recent work by Kojima which extended sums of squares relaxations of polynomial optimization problems to polynomial semidefinite programs. Let and be a finite dimensional real vector space and a symmetric cone embedded in ; examples of and include a pair of the N-dimensional Euclidean space and its nonnegative orthant, a pair of the N-dimensional Euclidean space and N-dimensional second-order cones, and a pair of the space of m × m real symmetric (or complex Hermitian) matrices and the cone of their positive semidefinite matrices. Sums of squares relaxations are further extended to a polynomial optimization problem over , i.e., a minimization of a real valued polynomial a(x) in the n-dimensional real variable vector x over a compact feasible region , where b(x) denotes an - valued polynomial in x. It is shown under a certain moderate assumption on the -valued polynomial b(x) that optimal values of a sequence of sums of squares relaxations of the problem, which are converted into a sequence of semidefinite programs when they are numerically solved, converge to the optimal value of the problem. Research supported by Grant-in-Aid for Scientific Research on Priority Areas 16016234.     

Solutions of polynomial Pell's equation

Let D=F²+2G be a monic quartic polynomial in Z[x], where . Then for F/G∈Q[x], a necessary and sufficient condition for the solution of the polynomial Pell's equation X²−DY²=1 in Z[x] has been shown. Also, the polynomial Pell's equation X²−DY²=1 has nontrivial solutions X,Y∈Q[x] if and only if the values of period of the continued fraction of are 2, 4, 6, 8, 10, 14, 18, and 22 has been shown. In this paper, for the period of the continued fraction of is 4, we show that the polynomial Pell's equation has no nontrivial solutions X,Y∈Z[x].     

On polynomial digraphs

Let Φ(x,y) be a bivariate polynomial with complex coefficients. The zeroes of Φ(x,y) are given a combinatorial structure by considering them as arcs of a directed graph G(Φ). This paper studies some relationship between the polynomial Φ(x,y) and the structure of G(Φ).     

Length Four Polynomial Automorphisms

We study the structure of length four polynomial automorphisms of R[X, Y] when R is a unique factorization domain. The results from this study are used to prove that, if SL _m (R[X ₁, X ₂,…, X _n ]) = E _m (R[X ₁, X ₂,…, X _n ]) for all n, m ≥ 0, then all length four polynomial automorphisms of R[X, Y] that are commutators are stably tame.     

Cryptosystems based on semi-distributive algebras

We propose a new cryptographic scheme of ElGamal type. The scheme is based on algebraic systems defined in the paper—semialgebras (Sect. 2). The main examples are semialgebras of polynomial mappings over a finite field K, and their factor-semialgebras. Given such a semialgebra R, one chooses an invertible element a ∈ R ^* of finite order r, and a random integer s. One chooses also a finite dimensional K-submodule V of R. The 4-tuple (R, V, a, b) where b = a ^s forms the public key for the cryptosystem, while r and s form the secret key. A plain text can be viewed as a sequence of elements of the field K. That sequence is divided into blocks of length dim(V) which, in turn, correspond to uniquely determined elements X _i of V. We propose three different methods (A, B, and C, see Definition 1.1) of encoding/decoding the sequence of X _i . The complexity of cracking the proposed cryptosystem is based on the Discrete Logarithm Problem for polynomial mappings (see Sect. 1.1). No methods of cracking the problem, except for the “brute force” (see Sect. 1.1) with Ω(r) time, are known so far.