A finer classification of the unit sum number of the ring of integers of quadratic fields and complex cubic fields

The unit sum number, u(R), of a ring R is the least k such that every element is the sum of k units; if there is no such k then u(R) is ω or ∞ depending on whether the units generate R additively or not. Here we introduce a finer classification for the unit sum number of a ring and in this new classification we completely determine the unit sum number of the ring of integers of a quadratic field. Further we obtain some results on cubic complex fields which one can decide whether the unit sum number is ω or ∞. Then we present some examples showing that all possibilities can occur.     

Min-Wise Independent Families with Respect to any Linear Order

A set of permutations 𝒮 on a finite linearly ordered set Ω is said to be k-min-wise independent, k-MWI for short, if Pr (min (π(X)) = π(x)) = 1/|X| for every X ? Ω such that |X| ≤ k and for every x ∈ X. (Here π(x) and π(X) denote the image of the element x or subset X of Ω under the permutation π, and Pr refers to a probability distribution on 𝒮, which we take to be the uniform distribution.) We are concerned with sets of permutations which are k-MWI families for any linear order. Indeed, we characterize such families in a way that does not involve the underlying order. As an application of this result, and using the Classification of Finite Simple Groups, we deduce a complete classification of the k-MWI families that are groups, for k ≥ 3.     

Some properties of multivariate extreme value distributions and multivariate tail equivalence

Summary Denote byH ak-dimensional extreme value distribution with marginal distributionH _i (x)=Λ(x)=exp(−e ^−x ),x∈R ¹. Then it is proved thatH(x)=Λ(x ₁)...Λ(x _k ) for anyx=(x ₁, ...,x _k ) ∈R ^k , if and only if the equation holds forx=(0,...,0). Next some multivariate extensions of the results by Resnick (1971,J. Appl. Probab.,8, 136–156) on tail equivalence and asymptotic distributions of extremes are established.     

Solvability of fourth‐order Sturm‐Liouville problems with abstract linear functionals in boundary‐transmission conditions

This study deals with the solvability of one nonclassical boundary‐value problem for fourth‐order differential equation on two disjoint intervals I₁=(−1,0)and I₂=(0,1). The boundary conditions contain not only endpoints x=−1and x=1but also a point of interaction x=0, finite number internal points x_jki∈I_j and abstract linear functionals S_k. So, our problem is not a pure differential one. We investigate such important properties as isomorphism, Fredholmness and coerciveness with respect to the spectral parameter. Note that the obtained results are new even in the case of the boundary conditions without internal points x_jki and without abstract linear functionals S_k.     

Simultaneous approximation in number fields

Summary We present here the solution of a problem of J.-J. Sansuc together with a natural generalization of it. This problem of Sansuc is, given a number fieldk, to find the smallest positive integerm for which there exists a finitely generated subgroup of rankm ofk ^x having a dense image in (R _Q k)^x under the canonical embedding. This integer is the number of archimedean places ofk plus one.Oblatum 28-I-1992This work was partially supported by NSERC and FCAR grants     

Roots of the affine Cremona group

Let k ^[n] = k[x ₁,…, x _n ] be the polynomial algebra in n variables and let \mathbbAⁿ = \textSpec  \boldk^{[ n ]} {\mathbb{A}^n} = {\text{Spec}}\;{{\bold{k}}^{\left[ n \right]}} . In this note we show that the root vectors of \textAu\textt^*( \mathbbAⁿ ) {\text{Au}}{{\text{t}}^*}\left( {{\mathbb{A}^n}} \right) , the subgroup of volume preserving automorphisms in the affine Cremona group \textAut( \mathbbAⁿ ) {\text{Aut}}\left( {{\mathbb{A}^n}} \right) , with respect to the diagonal torus are exactly the locally nilpotent derivations x ^α (∂/∂x _i ), where x ^α is any monomial not depending on x _i . This answers a question posed by Popov.     

Relations between threshold and <Emphasis Type="Italic">k</Emphasis>-interval Boolean functions

Every k-interval Boolean function f can be represented by at most k intervals of integers such that vector x is a truepoint of f if and only if the integer represented by x belongs to one of these k (disjoint) intervals. Since the correspondence of Boolean vectors and integers depends on the order of bits an interval representation is also specified with respect to an order of variables of the represented function. Interval representation can be useful as an efficient representation for special classes of Boolean functions which can be represented by a small number of intervals. In this paper we study inclusion relations between the classes of threshold and k-interval Boolean functions. We show that positive 2-interval functions constitute a (proper) subclass of positive threshold functions and that such inclusion does not hold for any k>2. We also prove that threshold functions do not constitute a subclass of k-interval functions, for any k.     

A “joint?+?marginal” heuristic for 0/1 programs

We propose a heuristic for 0/1 programs based on the recent “joint?+?marginal” approach of the first author for parametric polynomial optimization. The idea is to first consider the n-variable (x ₁, . . . , x _n ) problem as a (n ? 1)-variable problem (x ₂, . . . , x _n ) with the variable x ₁ being now a parameter taking value in {0, 1}. One then solves a hierarchy of what we call “joint?+?marginal” semidefinite relaxations whose duals provide a sequence of polynomial approximations ${x_1\mapsto J_k(x_1)}$ that converges to the optimal value function J (x ₁) (as a function of the parameter x ₁). One considers a fixed index k in the hierarchy and if J _k (1) >?J _k (0) then one decides x ₁ =?1 and x ₁ = 0 otherwise. The quality of the approximation depends on how large k can be chosen (in general, for significant size problems, k = 1 is the only choice). One iterates the procedure with now a (n ? 2)-variable problem with one parameter ${x_2 \in \{0, 1\}}$ , etc. Variants are also briefly described as well as some preliminary numerical experiments on the MAXCUT, k-cluster and 0/1 knapsack problems.     

Leray-Schauder Degree Method in Functional Boundary Value Problems Depending on the Parameter

Using the Leray-Schauder degree method sufficient conditions for the one-parameter boundary value problem x″ = f(t, x, x′, λ), α(x) = A, x(0) ? x(1) = B, x′(0) ? x′(1) = C, are stated. The application is given for a class of functional boundary value problems for nonlinear third-order functional differential equations depending on the parameter.     

The Menger property for infinite ordered sets

It is shown that, if an ordered set P contains at most k pairwise disjoint maximal chains, where k is finite, then every finite family of maximal chains in P has a cutset of size at most k. As a corollary of this, we obtain the following Menger-type result that, if in addition, P contains k pairwise disjoint complete maximal chains, then the whole family, M (P), of maximal chains in P has a cutset of size k. We also give a direct proof of this result. We give an example of an ordered set P in which every maximal chain is complete, P does not contain infinitely many pairwise disjoint maximal chains (but arbitrarily large finite families of pairwise disjoint maximal chains), and yet M (P) does not have a cutset of size <x, where x is any given (infinite) cardinal. This shows that the finiteness of k in the above corollary is essential and disproves a conjecture of Zaguia.     

Ore Extensions of Ore Domains

Let R be a right Ore domain and φ a derivation or an automorphism of R. We determine the right Martindale quotient ring of the Ore extension R[t; φ] (Theorem 1.1). As an attempt to generalize both the Weyl algebra and the quantum plane, we apply this to rings R such that k[x] ? R ? k(x), where k is a field and x is a commuting variable. The Martindale Quotient quotient ring of R[t; φ] and its automorphisms are computed. In this way, we obtain a family of non-isomorphic infinite dimensional simple domains with all their automorphisms explicitly described.     

An algorithm for selecting a good value for the parameter c in radial basis function interpolation

The accuracy of many schemes for interpolating scattered data with radial basis functions depends on a shape parameter c of the radial basis function. In this paper we study the effect of c on the quality of fit of the multiquadric, inverse multiquadric and Gaussian interpolants. We show, numerically, that the value of the optimal c (the value of c that minimizes the interpolation error) depends on the number and distribution of data points, on the data vector, and on the precision of the computation. We present an algorithm for selecting a good value for c that implicitly takes all the above considerations into account. The algorithm selects c by minimizing a cost function that imitates the error between the radial interpolant and the (unknown) function from which the data vector was sampled. The cost function is defined by taking some norm of the error vector E = (E ₁, ... , E_N)^T where E _k = E_k = f_k - S^k x_k) and S _k is the interpolant to a reduced data set obtained by removing the point x _k and the corresponding data value f _k from the original data set. The cost function can be defined for any radial basis function and any dimension. We present the results of many numerical experiments involving interpolation of two dimensional data sets by the multiquadric, inverse multiquadric and Gaussian interpolants and we show that our algorithm consistently produces good values for the parameter c. This revised version was published online in June 2006 with corrections to the Cover Date.     

Positive linear operators generated by analytic functions

Let φ be a power series with positive Taylor coefficients {a _k } _k=0^∞ and non-zero radius of convergence r ≤ ∞. Let ξ _x , 0 ≤ x < r be a random variable whose values α _k , k = 0, 1, …, are independent of x and taken with probabilities a _k x ^k /φ(x), k = 0, 1, …. The positive linear operator (A _φ f)(x):= E[f(ξ _x )] is studied. It is proved that if E(ξ _x ) = x, E(ξ _x ²) = qx ² + bx + c, q, b, c ∈ R, q > 0, then A _φ reduces to the Szász-Mirakyan operator in the case q = 1, to the limit q-Bernstein operator in the case 0 < q < 1, and to a modification of the Lupaş operator in the case q > 1.     

The Partitioned Version of the Erdős—Szekeres Theorem

   Abstract. Let k≥ 4 . A finite planar point set X is called a convex k -clustering if it is a disjoint union of k sets X ₁ , . . . ,X _k of equal sizes such that x ₁ x ₂ . . . x _k is a convex k -gon for each choice of x ₁ ∈ X ₁ , . . . ,x _k ∈ X _k . Answering a question of Gil Kalai, we show that for every k≥ 4 there are two constants c=c(k) , c'=c'(k) such that the following holds. If X is a finite set of points in general position in the plane, then it has a subset X' of size at most c' such that X \ X' can be partitioned into at most c convex k -clusterings. The special case k=4 was proved earlier by Pór. Our result strengthens the so-called positive fraction Erdos—Szekeres theorem proved by Barany and Valtr. The proof gives reasonable estimates on c and c' , and it works also in higher dimensions. We also improve the previous constants for the positive fraction Erdos—Szekeres theorem obtained by Pach and Solymosi.     

Approximation of singularly perturbed parabolic equations in unbounded domains subject to piecewise smooth boundary conditions in the case of solutions that grow at infinity

The initial-boundary value problem in a domain on a straight line that is unbounded in x is considered for a singularly perturbed reaction-diffusion parabolic equation. The higher order derivative in the equation is multiplied by a parameter ɛ², where ɛ ∈ (0, 1]. The right-hand side of the equation and the initial function grow unboundedly as x → ∞ at a rate of O(x ²). This causes the unbounded growth of the solution at infinity at a rate of O(Ψ(x)), where Ψ(x) = x ² + 1. The initialboundary function is piecewise smooth. When ɛ is small, a boundary and interior layers appear, respectively, in a neighborhood of the lateral part of the boundary and in a neighborhood of the characteristics of the reduced equation passing through the discontinuity points of the initial function. In the problem under examination, the error of the grid solution grows unboundedly in the maximum norm as x → ∞ even for smooth solutions when ɛ is fixed. In this paper, the proximity of solutions of the initial-boundary value problem and its grid approximations is considered in the weighted maximum norm ∥·∥ ^w with the weighting function Ψ⁻¹(x); in this norm, the solution of the initial-boundary value problem is ɛ-uniformly bounded. Using the method of special grids that condense in a neighborhood of the boundary layer or in neighborhoods of the boundary and interior layers, special finite difference schemes are constructed and studied that converge ɛ-uniformly in the weighted norm. It is shown that the convergence rate considerably depends on the type of nonsmoothness in the initial-boundary conditions. Grid approximations of the Cauchy problem with the right-hand side and the initial function growing as O(Ψ(x)) that converge ɛ-uniformly in the weighted norm are also considered.     

On Hilbert’s solution of Waring’s problem

In 1909, Hilbert proved that for each fixed k, there is a number g with the following property: Every integer N ≥ 0 has a representation in the form N = x ₁ ^k + x ₂ ^k + … + x _g ^k , where the x _i are nonnegative integers. This resolved a conjecture of Edward Waring from 1770. Hilbert’s proof is somewhat unsatisfying, in that no method is given for finding a value of g corresponding to a given k. In his doctoral thesis, Rieger showed that by a suitable modification of Hilbert’s proof, one can give explicit bounds on the least permissible value of g. We show how to modify Rieger’s argument, using ideas of F. Dress, to obtain a better explicit bound. While far stronger bounds are available from the powerful Hardy-Littlewood circle method, it seems of some methodological interest to examine how far elementary techniques of this nature can be pushed.     

A globally convergent inexact Newton method with a new choice for the forcing term

In inexact Newton methods for solving nonlinear systems of equations, an approximation to the step s _k of the Newton’s system J(x _k )s=−F(x _k ) is found. This means that s _k must satisfy a condition like ‖F(x _k )+J(x _k )s _k ‖≤η _k ‖F(x _k )‖ for a forcing term η _k ∈[0,1). Possible choices for η _k have already been presented. In this work, a new choice for η _k is proposed. The method is globalized using a robust backtracking strategy proposed by Birgin et al. (Numerical Algorithms 32:249–260, 2003), and its convergence properties are proved. Several numerical experiments with boundary value problems are presented. The numerical performance of the proposed algorithm is analyzed by the performance profile tool proposed by Dolan and Moré (Mathematical Programming Series A 91:201–213, 2002). The results obtained show a competitive inexact Newton method for solving academic and applied problems in several areas. Supported by FAPESP, CNPq, PRONEX-Optimization.     

Stieltjes Moment Problems and the Friedrichs Extension of a Positive Definite Operator

For an indeterminate Stieltjes moment sequence the multiplication operator Mp(x) = xp(x) is positive definite and has self-adjoint extensions. Exactly one of these extensions has the same lower bound as M, the so-called Friedrichs extension. The spectral measure of this extension gives a certain solution to the moment problem and we identify the corresponding parameter value in the Nevanlinna parametrization of all solutions to the moment problem. In the case where σ is indeterminate in the sense of Stieltjes, relations between the (Nevanlinna matrices of) entire functions associated with the measures t^kdσ(t) are derived. The growth of these entire functions is also investigated.     

Using genetic algorithms to optimize nearest neighbors for data mining

Case-based reasoning (CBR) is widely used in data mining for managerial applications because it often shows significant promise for improving the effectiveness of complex and unstructured decision making. There are, however, some limitations in designing appropriate case indexing and retrieval mechanisms including feature selection and feature weighting. Some of the prior studies pointed out that finding the optimal k parameter for the k-nearest neighbor (k-NN) is also one of the most important factors for designing an effective CBR system. Nonetheless, there have been few attempts to optimize the number of neighbors, especially using artificial intelligence (AI) techniques. This study proposes a genetic algorithm (GA) approach to optimize the number of neighbors to combine. In this study, we apply this novel model to two real-world cases involving stock market and online purchase prediction problems. Experimental results show that a GA-optimized k-NN approach may outperform traditional k-NN. In addition, these results also show that our proposed method is as good as or sometime better than other AI techniques in performance-comparison.