Some polynomials that are hard to compute

Using the result of Heintz and Sieveking [1], we show that the polynomials $\text{Σ}{}_{\mathrm{1?j?d}}\text{b}{}^{\mathrm{<mtext>1</mtext><mtext>i</mtext>}}\text{X}{}^{\mathrm{j}}$ with b positive real different from one, and Σ_1?j?dj^rX^j with r rational not integer, are hard to compute.     

Normal forms for nonautonomous difference equations

We extend Henry Poincaré's normal form theory for autonomous difference equations χ_{k + 1} = f(χ_k) to nonautonomous difference equations χ_{k + 1} = f_k(χ_k). Poincaré's nonresonance condition $\text{α}{}_{\mathrm{j}}\text{-П}{}^{\mathrm{n}}{}_{\mathrm{i=1}}\text{=1α}{}^{\mathrm{qi}}{}_{\mathrm{i}}\text{≠0}$ for eigenvalues is generalized to the new nonresonance condition λ_j∪$\text{α}{}_{\mathrm{j}}\text{⊔П}{}^{\mathrm{n}}{}_{\mathrm{i=1}}\text{α}{}^{\mathrm{qi}}{}_{\mathrm{i}}\text{≠0}$ for spectral intervals.     

Averaging shifted histograms

A method which consists in shifting different histograms of the same spectrum and then taking their average is presented in order to smooth the data and to increase the localization accuracy and separation of the peaks. The statistical properties of this method are investigated. The average of two histograms with shifted bin limits is studied. It is shown that for histograms with random bin limits, distributed according to

$\text{F}{}_{\mathrm{i}}\text{(x)=}\text{∫}\text{?∞}\text{x}\text{?}{}_{\mathrm{i}}\text{(ξ, μ}{}_{\mathrm{i}}\text{, σ)}\text{d}\text{ξ}$

; where the standard deviation σ is very small compared to the difference of the means (μ_i+1 ? μ_i) for ll i the zero order approximation to the variance of this histogram is given by:

$\text{var}\text{∽}\text{(H)=}\text{∑}\text{i=0}\text{m}\text{(A}{}_{\mathrm{i+1}}\text{?a}{}_{\mathrm{i}}\text{)}{}^2\text{F}{}_{\mathrm{i+1}}\text{(x)(1?F}{}_{\mathrm{i+1}}\text{(x))}$

, where

$\text{a}{}_{\mathrm{i}}\text{=}\text{1}\text{x}{}_{\mathrm{i=1}}\text{?x}{}_{\mathrm{i}}\text{∫}\text{x}{}_{\mathrm{i}}\text{x}{}_{\mathrm{i+1}}\text{g(ξ)}\text{d}\text{ξ}$

and g is an unknown function fitted by the histogram. Formula (1) gives also the relation:

$\text{v}\text{a}\text{?}\text{r}\text{(}\text{(H}{}_1\text{+ H}{}_2\text{)}\text{2}\text{) =}\text{1}\text{4}\text{(}\text{v}\text{a}\text{?}\text{r}\text{(H}{}_1\text{(x)) +}\text{v}\text{a}\text{?}\text{r}\text{(H}{}_2\text{(x))}$

, when H₁ and H₂ have stochastically independent bin limits.When the histogram H is considered as a spline function S of order one it is shown that for the minimization criterion with respect to the coefficient of the spline:

$\text{M}{}_1\text{=}\text{min}\text{∫}\text{x}{}_1\text{x}{}_{\mathrm{m+1}}\text{(g(x) ? S}{}_1\text{(x))}{}^2\text{d}\text{x}$

, the following result holds: $\text{M}{}_{\mathrm{a}}\text{?}{}^1{}_2\text{(M}{}_1\text{+ M}{}_2\text{)}$, where $\text{S}{}_{\mathrm{a}}\text{(x) =}{}^1{}_2\text{(S}{}_1\text{(x) + S}{}_2\text{(x))}$. If the number of shifted histograms tends to infinity, then

$\text{S}{}_{\mathrm{\infty }}\text{(x) = [Γ(x + h) + Γ(x ? h) ? 2Γ(x)]/h}{}^2$

, where $\text{Γ(x) =}\text{∫}\text{?∞}\text{x}\text{∫}\text{?∞}\text{η}\text{g(ξ)}\text{d}\text{ξ}\text{d}\text{η}$, and h is a constant bin size. Then

$\text{M}{}_{\mathrm{\infty }}\text{≈}\text{h}{}^4\text{144}\text{∫}\text{x}{}_1\text{x}{}_{\mathrm{m+1}}\text{g″}{}^2\text{(x)}\text{D}\text{x}$

. Extensions to two-dimensional histograms and to higher order (empirical distributions) are presented.     

The relation between information theory and the differential geometry approach to statistics

?encov has shown that the Riemannian metric on the probability simplex ∑x_i = 1 defined by $\text{(ds)}{}^2\text{=}\text{∑(dx}{}_{\mathrm{i}}\text{)}{}^2\text{x}{}_{\mathrm{i}}$ has an invariance property under certain probabilistically natural mappings. No other Riemannian metric has the same property. The geometry associated with this metric is shown to lead almost automatically to measures of divergence between probability distributions which are associated with Kullback, Bhattacharyya, and Matusita. Certain vector fields are associated in a natural way with random variables. The integral curves of these vector fields yield the maximum entropy or minimum divergence estimates of probabilities. Some other consequences of this geometric view are also explored.     

An optimal triangulation for second-order elliptic problems

Let Ω be a polygonal domain in $\text{R}{}^{\mathrm{n}}$, τ_h an associated triangulation and u_h the finite element solution of a well-posed second-order elliptic problem on (Ω, τ_h). Let M = {M_i}^{p + q}_{i = 1} be the set of nodes which defines the vertices of the triangulation τ_h: for each i,$\text{M}{}_{\mathrm{i}}\text{= {x}{}_{\mathrm{i}}{}^{\mathrm{l}}\text{¦1 ? l ?n}}$ in Rⁿ. The object of this paper is to provide a computational tool to approximate the best set of positions M? of the nodes and hence the best triangulation $\text{}\text{?}\text{gt}{}_{\mathrm{h}}$ which minimizes the solution error in the natural norm associated with the problem.The main result of this paper are theorems which provide explicit expressions for the partial derivatives of the associated energy functional with respect to the coordinates x_i^l, 1 ? l ? n, of each of the variable nodes M_i, i = 1,…, p.     

Asymptotic properties of minimax trees and game-searching procedures

The model most frequently used for evaluating the behavior of game-searching methods consists of a uniform tree of height h and a branching degree d, where the terminal positions are assigned random, independent and identically distributed values. This paper highlights some curious properties of such trees when h is very large and examines their implications on the complexity of various game-searching methods.If the terminal positions are assigned a WIN-LOSS status with the probabilities P₀ and 1 ? P₀, respectively, then the root node is almost a sure MIN or a sure LOSS, depending on whether P₀ is higher or lower than some fixed-point probability $\text{P1(d)}$. When the terminal positions are assigned continuous real values, the minimax value of the root node converges rapidly to a unique predetermined value $\text{v1}$, which is the $\text{(1 ? P1)-}\text{fractile}$ of the terminal distribution.Exploiting these properties we show that a game with WIN-LOSS terminals can be solved by examining, on the average, $\text{O}\text{[(d)}{}^{\mathrm{<mtext>h</mtext><mtext>2</mtext>}}\text{]}$ terminal positions if positions if $\text{P}{}_0\text{≠ P1}$ and $\text{O}\text{[(}\text{P1}\text{(1 ? P1)}\text{)}{}^{\mathrm{h}}\text{]}$ positions if $\text{P}{}_0\text{= P1}$, the former performance being optimal for all search algorithms. We further show that a game with continuous terminal values can be evaluated by examining an average of $\text{O}\text{[(}\text{P1}\text{(1 ? P1)}\text{)}{}^{\mathrm{h}}\text{]}$ positions, and that this is a lower bound for all directional algorithms. Games with discrete terminal values can, in almost all cases, be evaluated by examining an average of $\text{O}\text{[(d)}{}^{\mathrm{<mtext>h</mtext><mtext>2</mtext>}}\text{]}$ terminal positions. This performance is optimal and is also achieved by the ALPHA-BETA procedure.     

Improving loops and vanishing variables in long transportation problems

In this paper the following two results are presented: (1)A method which determines the optimal values of certain variables during the iterative solution process. The closer the current primal feasible solution is to the optimal solution, the greater the number of variables which may be determined. (2) For each current feasible solution (X_ij) of the given m × n transportation problem A, a feasible solution ($\text{X}\text{?}{}_{\mathrm{ij}}$) of an auxiliary m × m(m ?1) transportation problem $\text{A}\text{?}$ is constructed. Problem $\text{A}\text{?}$ is shown to be equivalent to an m(m ? 1) × m(m ? 1) assignment problem with two admissible cells per column. The optimally of (X_ij) is shown to imply the optimality of ($\text{X}\text{?}{}_{\mathrm{ij}}$) and conversely. The best “improving loops” (including the improving loops used in MODI) of $\text{A}\text{?}$ are shown to be the best “improving loops” of A as well.     

Matrix equations over rings

The main purpose of this work is to establish necessary conditions and sufficient conditions for the existence of a solution of matrix equations whose coefficient matrices have elements belonging to the ring $\text{R=}\text{C}\text{[z}{}_1\text{,z}{}_2\text{,…z}{}_{\mathrm{n}}\text{]}$ of polynomials in n variables with complex coefficients and the ring $\text{R=}\text{R}\text{[z}{}_1\text{,z}{}_2\text{,…z}{}_{\mathrm{n}}\text{]}{}^{\mathrm{n}}$ of rational functions a(z₁,z₂,…z_n)b(z₁,z₂,…,z_n)^?1 with real coefficients and b(z₁,z₂,…,z_n)≠0 for all (z₁,z₂,…,z_n) in Rⁿ. Results obtained are useful in multidimensional systems theory and elsewhere.     

Liquid-liquid solubility and critical phenomena in binary mixtures

By assuming a proportionality exists between a difference in Boltzmann factors and a difference in compositions, the following expression is developed for the mole fraction order parameter in symmetric binary liquid mixtures $\text{Δx = [1 ?}\text{exp}\text{E}\text{RT}{}_{\mathrm{c}}\text{(l?T}{}_{\mathrm{c}}\text{/T)]}{}^{\mathrm{\beta }}$ In the critical limit this expression reduces to the form for simple scaling fx253-fig 1 By treating the original components A and B as if they transfer between the phases in the form of aggregates with the empirical formulas A_mB_1?m and B_n, in which 0<m≤Landn>0, coexistence curves in diverse systems become symmetric and are fitted by the above expressions. Beta exponent values obtained from these fits range in value from 0.312±0.002 to 0.333±0.003.     

Mathematical foundations of Bézier's technique

Bezier's method is one of the most famous in computational geometry. In his book Numerical control Bezier gives excellent expositions of the mathematical foundations of this method. In this paper a new expression of the functions {f_n,i(u)}

$\text{f}{}_{\mathrm{n,i}}\text{(u)=1?}\text{Σ}\text{p=0}\text{i?1}\text{C}{}^{\mathrm{p}}{}_{\mathrm{n}}\text{u}{}^{\mathrm{p}}\text{(1?u)}{}^{\mathrm{n?p}}\text{(i=1,2,…,n)}$

is obtained.Using this formula, we have not only derived some properties of the functions {f_n,i(u)} (for instance $\text{f}{}_{\mathrm{n,n}}\text{(u) < f}{}_{\mathrm{n,n?1}}\text{(u)<...<f}{}_{\mathrm{n,1}}\text{(u)}\text{u}\text{? [0, 1]}$ and functions {f_n,i(u)} increase strictly at [0, 1] etc) but also simplified systematically all the mathematical discussions about Bezier's method.Finally we have proved the plotting theorem completely by matrix calculation.     

Crosscorrelation between linearly and nonlinearly distorted versions of a given signal

A given deterministic signal x(.) is distorted by passing it through a linear time-invariant filter and also by subjecting it to the action of an instantaneous nonlinearity. The resulting time crosscorrelation of the two distorted versions of the original signal is expressed by the function

$\text{R}{}_2\text{(s)?∫}{}_{\mathrm{?\infty }}{}^{\mathrm{\infty }}\text{?∫}{}_{\mathrm{?\infty }}{}^{\mathrm{\infty }}\text{g[x(t)]k(t?t′)x(t?s)dt dt′}$

, where x(.) is the given signal, k(.) is the nonnegative definite impulse response of the linear filter, and g(.) is the output-input characteristic of the zero-memory nonlinear device. The problem considered is that of determining conditions on the pair (x,g) such that R₂(s) ? R₂(0) for all s and any choice of nonnegative definite filter function k; the principal result is the formulation of a necessary and sufficient condition for R₂ to have a global maximum at the origin. In particular, the peak value occurs at the origin if and only if $\text{G}{}_{\mathrm{x}}{}^1\text{(ω)X(ω)}$ is real and nonnegative for all ω ? 0, where G_x(.) and X(.) are the Fourier transforms of g[x(.)] and x(.), respectively. An equivalent condition is that the correlation function

$\text{R}{}_2\text{(s)?∫}{}_{\mathrm{?\infty }}{}^{\mathrm{\infty }}\text{g[x(t)]x(t?s)dt}$

, previously studied by Richardson, be nonnegative definite.Several examples are given, and it is shown that, unlike the case for R₁(.), monotonicity of g(.) is not a sufficient condition for R₂(.) to have a global maximum at s = 0 independently of the choice of filter characteristic k. Certain extensions of these results are given for the case when x(.) is a Gaussian random input.     

Determination of a general economic location constant by monte carlo simulation

The problem of estimating the number of markets (or plants) to serve a set of sources in a given geographical area was considered. Markets were located so as to minimize total assembly cost which was considered a linear function of the weighted Euclidean distances between sources and markets. The following predictive function C_m was proposed for estimating the minimum total assembly cost for a given number of markets: $\text{C}{}_{\mathrm{m}}\text{= C}{}_1\text{?(}\text{m?1}\text{m}\text{)}{}^{\mathrm{k}}\text{(}\text{M}\text{M ? 1}\text{)}{}^{\mathrm{k}}\text{(C}{}_1\text{? C}{}_{\mathrm{M}}\text{),m = 1, 2, 3, …, M}$ where m = number of markets being located. M = maximum number of potential market sites. C₁ = minimum assembly cost when only one market is located. C_M = minimum assembly cost when all M markets are located. k = an undetermined constant which specifies the shape of the function.The validity of the C_m function and the range of the k constant were determined by computer Monte Carlo experimentation. The constant k, to a sufficient degree of approximation and ordinary use, was found independent of the number of sources and their distribution. A general economic location co     

On n-Dimensional Sequences. I

Let R be a commutative ring and let n ≥ 1. We study Γ(s), the generating function and Ann(s), the ideal of characteristic polynomials of s, an n-dimensional sequence over R .We express f(X₁,…,X_n) · Γ(s)(X^-1₁,…,X^-1_n) as a partitioned sum. That is, we give (i) a 2ⁿ-fold "border" partition (ii) an explicit expression for the product as a 2ⁿ-fold sum; the support of each summand is contained in precisely one member of the partition. A key summand is βo(f, s), the "border polynomial" of f and s, which is divisible by X₁ … X_n.We say that s is eventually rectilinear if the elimination ideals Ann(s)∩R[X_i] contain an f_i (X_i) for 1 ≤ i ≤ n. In this case, we show that Ann(s) is the ideal quotient ($\text{∑}{}^{\mathrm{n}}{}_{\mathrm{i}}\text{=1(fi) : βo(f, s)/(X}{}_1\text{… X}{}_{\mathrm{n}}\text{)}$).When R and R[[X₁, X₂ ,…, X_n]] are factorial domains (e.g. R a principal ideal domain or F [X₁,…, X_n]), we compute the monic generator γ_i of Ann(s) ∩ R[X_i] from known f_i ϵ Ann(s) ∩ R[X_i] or from a finite number of 1-dimensional linear recurring sequences over R. Over a field F this gives an O($\text{∏}{}_{\mathrm{n}}{}^{\mathrm{i}}\text{=1 δγ}{}^3{}_{\mathrm{i}}$) algorithm to compute an F-basis for Ann(s).     

On some convergence results for FDM with irregular mesh

The proof of convergence of the finite difference method with arbitrary irregular meshes for some class of elliptic problems is presented. By the use of the truncation error technique and stability analysis it was showed that $\text{max}{}_{\mathrm{i}}\text{¦u}{}^{\mathrm{i}}\text{? u}{}_{\mathrm{h}}{}^{\mathrm{i}}\text{¦? Ch}$, i.e., the solution u_h converges linearly with the size of the star. Correctness of this theorem was also confirmed by numerical tests.     

computer aided intuition in abstract algebra

Two examples are given in which the computer was used to supplement intuition in abstract algebra. In the first example, the computer was used to search Cayley tables of 4 element groupoids to find those which are 5-associative but not 4-associative. (n-associative means that the product of any n elements is independent of the way the factors are grouped by parentheses.) The computer generated examples suggested the existence of n element groupoids which are (2^n?2+1)-associative but not (2^n-2)-associative, for each integer n≧4.In the second example, the computer counted the numbers g₂(m) of invertible 2×2 matrices with entries chosen from the ring Z_mof integers, for m = 2, 3, 4,…, 18. The insight gained from these results led to a proof that there are

invertible n×n matrices over Z_m.Some applications to graduate and undergraduate instruction are indicated.