Divided differences for functions of two variables for irregularly spaced arguments

Divided differences forf (x, y) for completely irregular spacing of points (x _i ,y _i ) are developed here by a natural generalization of Newton's scheme. Existing bivariate schemes either iterate the one-dimensional scheme, thus constraining (x _i ,y _i ) to be at corners of rectangles, or give polynomials Σa _jk x ^j y ^k having more coefficients than interpolation conditions. Here the generalizedn ^th divided difference is defined by (1)\(\left[ {01... n} \right] = \sum\limits_{i = 0}^n {A_i f\left( {x_i , y_i } \right)} \) where (2)\(\sum\limits_{i = 0}^n {A_i x_i^j , y_i^k = 0} \), and 1 for the last or (n+1)^th equation, for every (j, k) wherej+k=0, 1, 2,... in the usual ascending order. The gen. div. diff. [01...n] is symmetric in (x _i ,y _i ), unchanged under translation, 0 forf (x, y) an, ascending binary polynomial as far asn terms, degree-lowering with respect to (X, Y) whenf(x, y) is any polynomialP(X+x, Y+y), and satisfies the 3-term recurrence relation (3) [01...n]=λ{[1...n]?[0...n?1]}, where (4) λ= |1...n|·|01...n?1|/|01...n|·|1...n?1|, the |...i...| denoting determinants inx _i ^j y _i ^k . The generalization of Newton's div. diff. formula is (5)

$$\begin{gathered} f\left( {x, y} \right) = f\left( {x_0 , y_0 } \right) - \frac{{\left| {\alpha 0} \right|}}{{\left| 0 \right|}}\left[ {01} \right] + \frac{{\left| {\alpha 01} \right|}}{{\left| {01} \right|}}\left[ {012} \right] - \frac{{\left| {\alpha 012} \right|}}{{\left| {012} \right|}}\left[ {0123} \right] + \cdots + \hfill \\ + \left( { - 1} \right)^n \frac{{\left| {\alpha 01 \ldots n - 1} \right|}}{{\left| {01 \ldots n - 1} \right|}}\left[ {01 \ldots n} \right] + \left( { - 1} \right)^{n + 1} \frac{{\left| {\alpha 01 \ldots n} \right|}}{{\left| {01 \ldots n} \right|}}\left[ {01 \ldots n} \right], \hfill \\ \end{gathered} $$     

Series by Haar system with monotone coefficients

Let χ = {χ _n } _n=0 ^∞ be the Haar system normalized in L ²(0, 1) and M = {M _s } _s=1 ^∞ be an arbitrary, increasing sequence of nonnegative integers. For any subsystem of χ of the form {φ _k } = χS = {χ _n } _n∈S , where S = S(M) = {n _k } _k=1 ^∞ = {n ∈ V[p]: p ∈ M}, V[0] = {1, 2} and V[p] = {2 ^p + 1, 2 ^p + 2, …, 2 ^p+1} for p = 1, 2, … a series of the form Σ _i=1 ^∞ a _i φ _i with a _i ↘ 0 is constructed, that is universal with respect to partial series in all classes L ^r (0, 1), r ∈ (0, 1), in the sense of a.e. convergence and in the metric ofL ^r (0, 1). The constructed series is universal in the class of all measurable, finite functions on [0, 1] in the sense of a.e. convergence. It is proved that there exists a series by Haar system with decreasing coefficients, which has the following property: for any ? > 0 there exists a measurable function µ(x), x ∈ [0, 1], such that 0 ≤ µ(x) ≤ 1 and |{x ∈ [0, 1], µ(x) ≠ = 1}| < ?, and the series is universal in the weighted space L _µ[0, 1] with respect to subseries, in the sense of convergence in the norm of L _µ[0, 1].     

The communication complexity of addition

Suppose each of k≤n ^o(1) players holds an n-bit number x _i in its hand. The players wish to determine if ∑ _i≤k x _i =s. We give a public-coin protocol with error 1% and communication O(k logk). The communication bound is independent of n, and for k≥3 improves on the O(k logn) bound by Nisan (Bolyai Soc. Math. Studies; 1993).     

Hausdorff dimension of the maximal run-length in dyadic expansion

For any x ∈ [0, 1), let x = [? ₁, ? ₂, …,] be its dyadic expansion. Call r _n (x):= max{j ? 1: ? _i+1 = … = ? _i+j = 1, 0 ? i ? n ? j} the n-th maximal run-length function of x. P.Erdös and A.Rényi showed that \(\mathop {\lim }\limits_{n \to \infty } \) r _n (x)/log₂ n = 1 almost surely. This paper is concentrated on the points violating the above law. The size of sets of points, whose runlength function assumes on other possible asymptotic behaviors than log₂ n, is quantified by their Hausdorff dimension.     

Norms on L of Periodic Interpolation Splines with Equidistant Nodes

We consider the set S _r,n of periodic (with period 1) splines of degree r with deficiency 1 whose nodes are at n equidistant points x_i=i / n. For n-tuples y = (y₀, ... , y_n-1), we take splines s _r,n (y, x) from S _r,n solving the interpolation problem

$$s_{r,n} (y,t_i ) = y_i,$$

where t _i = x _i if r is odd and t _i is the middle of the closed interval [x _i , x _i+1 ] if r is even. For the norms L _r,n ^* of the operator y → s _r,n (y, x) treated as an operator from l¹ to L¹ [0, 1] we establish the estimate

$$L_{r,n}^ * = \frac{4}{{\pi ^2 n}}log min(r,n) + O\left( {\frac{1}{n}} \right)$$

with an absolute constant in the remainder. We study the relationship between the norms L _r,n ^* and the norms of similar operators for nonperiodic splines.

     

New algorithm for computing the Hermite interpolation polynomial

Let x ₀, x ₁,? , x _n , be a set of n + 1 distinct real numbers (i.e., x _i ≠ x _j , for i ≠ j) and y _{i, k} , for i = 0,1,? , n, and k = 0 ,1 ,? , n _i , with n _i ≥ 1, be given of real numbers, we know that there exists a unique polynomial p _{N ? 1}(x) of degree N ? 1 where \(N={\sum }_{i=0}^{n}(n_{i}+1)\), such that \(p_{N-1}^{(k)}(x_{i})=y_{i,k}\), for i = 0,1,? , n and k = 0,1,? , n _i . P _N?1(x) is the Hermite interpolation polynomial for the set {(x _i , y _{i, k} ), i = 0,1,? , n, k = 0,1,? , n _i }. The polynomial p _N?1(x) can be computed by using the Lagrange polynomials. This paper presents a new method for computing Hermite interpolation polynomials, for a particular case n _i = 1. We will reformulate the Hermite interpolation polynomial problem and give a new algorithm for giving the solution of this problem, the Matrix Recursive Polynomial Interpolation Algorithm (MRPIA). Some properties of this algorithm will be studied and some examples will also be given.     

On the summability factors of infinite series

The author has established that if [λ_n] is a convex sequence such that the series Σn ^-1λ_n is convergent and the sequence {K _n} satisfies the condition |K _n|=O[log(n+1)]^k(C, 1),k?0, whereK _n denotes the (R, logn, 1) mean of the sequence {n log (n+1)a _n}, then the series Σlog(n+1)^1-kλ_n a _n is summable |R, logn, 1|. The result obtained for the particular casek=0 generalises a previous result of the author [1].     

Stability of Cubic and Quartic Functional Equations in Non-Archimedean Spaces

We prove generalized Hyers-Ulam–Rassias stability of the cubic functional equation f(kx+y)+f(kx?y)=k[f(x+y)+f(x?y)]+2(k ³?k)f(x) for all \(k\in \Bbb{N}\) and the quartic functional equation f(kx+y)+f(kx?y)=k ²[f(x+y)+f(x?y)]+2k ²(k ²?1)f(x)?2(k ²?1)f(y) for all \(k\in \Bbb{N}\) in non-Archimedean normed spaces.     

Searching for a Best Least Absolute Deviations Solution of an Overdetermined System of Linear Equations Motivated by Searching for a Best Least Absolute Deviations Hyperplane on the Basis of Given Data

We consider the problem of searching for a best LAD-solution of an overdetermined system of linear equations Xa=z, X∈?^m×n, m≥n, \(\mathbf{a}\in \mathbb{R}^{n}, \mathbf {z}\in\mathbb{R}^{m}\). This problem is equivalent to the problem of determining a best LAD-hyperplane x?a ^T x, x∈? ⁿ on the basis of given data \((\mathbf{x}_{i},z_{i}), \mathbf{x}_{i}= (x_{1}^{(i)},\ldots,x_{n}^{(i)})^{T}\in \mathbb{R}^{n}, z_{i}\in\mathbb{R}, i=1,\ldots,m\), whereby the minimizing functional is of the form

$F(\mathbf{a})=\|\mathbf{z}-\mathbf{Xa}\|_1=\sum_{i=1}^m|z_i-\mathbf {a}^T\mathbf{x}_i|.$

An iterative procedure is constructed as a sequence of weighted median problems, which gives the solution in finitely many steps. A criterion of optimality follows from the fact that the minimizing functional F is convex, and therefore the point a ^?∈? ⁿ is the point of a global minimum of the functional F if and only if 0∈?F(a ^?).

Motivation for the construction of the algorithm was found in a geometrically visible algorithm for determining a best LAD-plane (x,y)?αx+βy, passing through the origin of the coordinate system, on the basis of the data (x _i ,y _i ,z _i ),i=1,…,m.     

On the structure of large sum-free sets of integers

A set of integers is called sum-free if it contains no triple (x, y, z) of not necessarily distinct elements with x + y = z. In this paper, we provide a structural characterisation of sum-free subsets of {1, 2,..., n} of density at least 2/5 ? c, where c is an absolute positive constant. As an application, we derive a stability version of Hu’s Theorem [Proc. Amer. Math. Soc. 80 (1980), 711–712] about the maximum size of a union of two sum-free sets in {1, 2,..., n}. We then use this result to show that the number of subsets of {1, 2,..., n} which can be partitioned into two sum-free sets is Θ(2^4n/5), confirming a conjecture of Hancock, Staden and Treglown [arXiv:1701.04754].     

Automorphisms of metacyclic groups

A metacyclic group H can be presented as 〈α,β: αⁿ = 1, β^m = α^t, βαβ^?1 = α^r〉 for some n, m, t, r. Each endomorphism σ of H is determined by \(\sigma(\alpha)=\alpha^{x_1}\beta^{y_1}, \sigma(\beta)=\alpha^{x_2}\beta^{y_2}\) for some integers x₁, x₂, y₁, y₂. We give sufficient and necessary conditions on x₁, x₂, y₁, y₂ for σ to be an automorphism.     

Fast Algorithm of Square Rooting in Some Finite Fields of Odd Characteristic

It was proved that the complexity of square root computation in the Galois field GF(3^s), s = 2^kr, is equal to O(M(2^k)M(r)k + M(r) log₂r) + 2^kkr^1+o(1), where M (n) is the complexity of multiplication of polynomials of degree n over fields of characteristics 3. The complexity of multiplication and division in the field GF(3^s) is equal to O(M(2^k)M(r)) and O(M(2^k)M(r)) + r^1+o(1), respectively. If the basis in the field GF(3^r) is determined by an irreducible binomial over GF(3) or is an optimal normal basis, then the summands 2^kkr^1+o(1) and r^1+o(1) can be omitted. For M(n) one may take n log₂nψ(n) where ψ(n) grows slower than any iteration of the logarithm. If k grow and r is fixed, than all the estimates presented here have the form O_r (M (s) log ₂s) = s (log ₂s)²ψ(s).     

Diophantine inequality involving binary forms

Let d ? 3 be an integer, and set r = 2^d?1 + 1 for 3 ? d ? 4, \(\tfrac{{17}}{{32}} \cdot 2^d + 1\) for 5 ? d ? 6, r = d²+d+1 for 7 ? d ? 8, and r = d²+d+2 for d ? 9, respectively. Suppose that Φ _i (x, y) ∈ ?[x, y] (1 ? i ? r) are homogeneous and nondegenerate binary forms of degree d. Suppose further that λ₁, λ₂,..., λ _r are nonzero real numbers with λ₁/λ₂ irrational, and λ₁Φ₁(x₁, y₁) + λ₂Φ₂(x₂, y₂) + · · · + λ _r Φ _r (x _r , y _r ) is indefinite. Then for any given real η and σ with 0 < σ < 2^2?d, it is proved that the inequality

$$\left| {\sum\limits_{i = 1}^r {{\lambda _i}\Phi {}_i\left( {{x_i},{y_i}} \right) + \eta } } \right| < {\left( {\mathop {\max \left\{ {\left| {{x_i}} \right|,\left| {{y_i}} \right|} \right\}}\limits_{1 \leqslant i \leqslant r} } \right)^{ - \sigma }}$$

has infinitely many solutions in integers x₁, x₂,..., x _r , y₁, y₂,..., y _r . This result constitutes an improvement upon that of B. Q. Xue.

     

Asymptotic Analysis for Random Walks with Nonidentically Distributed Jumps Having Finite Variance

Let ξ₁,ξ₂,... be independent random variables with distributions F₁F₂,... in a triangular array scheme (F _i may depend on some parameter). Assume that Eξ _i = 0, Eξ _i ² < ∞, and put \(S_n = \sum {_{i = 1}^n \;} \xi _i ,\;\overline S _n = \max _{k \leqslant n} S_k\). Assuming further that some regularly varying functions majorize or minorize the “averaged” distribution \(F = \frac{1}{n}\sum {_{i = 1}^n F_i }\), we find upper and lower bounds for the probabilities P(S _n > x) and \(P(\bar S_n > x)\). We also study the asymptotics of these probabilities and of the probabilities that a trajectory {S _k } crosses the remote boundary {g(k)}; that is, the asymptotics of P(max_k≤n(S _k ? g(k)) > 0). The case n = ∞ is not excluded. We also estimate the distribution of the first crossing time.     

On the approximation of continuous functions of two variables

It is shown that if P _m ^α,β (x) (α, β > ?1, m = 0, 1, 2, …) are the classical Jaboci polynomials, then the system of polynomials of two variables {Ψ _mn ^α,β (x, y)} _m,n=0 ^r = {P _m ^α,β (x)P _n ^α,β (y)} _{m, n=0} ^r (r = m + n ≤ N ? 1) is an orthogonal system on the set Ω _N×N = ?ub;(x _i , y _i ) _i,j=0 ^N , where x _i and y _i are the zeros of the Jacobi polynomial P _n ^α,β (x). Given an arbitrary continuous function f(x, y) on the square [?1, 1]², we construct the discrete partial Fourier-Jacobi sums of the rectangular type S _{m, n, N} ^α,β (f; x, y) by the orthogonal system introduced above. We prove that the order of the Lebesgue constants ∥S _{m, n, N} ^α,β ∥ of the discrete sums S _{m, n, N} ^α,β (f; x, y) for ?1/2 < α, β < 1/2, m + n ≤ N ? 1 is O((mn) ^{q + 1/2}), where q = max?ub;α,β?ub;. As a consequence of this result, several approximate properties of the discrete sums S _{m, n, N} ^α,β (f; x, y) are considered.     

Planar Graded Lattices and the <Emphasis Type="Bold">c</Emphasis><Subscript>1</Subscript>-Median Property

Let L be a lattice of finite length, ξ = (x ₁,…, x _k )∈L ^k , and y ∈ L. The remoteness r(y, ξ) of y from ξ is d(y, x ₁)+?+d(y, x _k ), where d stands for the minimum path length distance in the covering graph of L. Assume, in addition, that L is a graded planar lattice. We prove that whenever r(y, ξ) ≤ r(z, ξ) for all z ∈ L, then y ≤ x ₁∨?∨x _k . In other words, L satisfies the so-called c ₁ -median property.     

Description of polygonal regions by polynomials of bounded degree

We show that every (possibly unbounded) convex polygon P in \({\mathbb{R}^2}\) with m edges can be represented by inequalities p ₁ ≥ 0, . . ., p _n ≥ 0, where the p _i ’s are products of at most k affine functions each vanishing on an edge of P and n = n(m, k) satisfies \({s(m, k) \leq n(m, k) \leq (1+\varepsilon_m) s(m, k)}\) with s(m,k) ? max {m/k, log₂ m} and \({\varepsilon_m \rightarrow 0}\) as \({m \rightarrow \infty}\). This choice of n is asymptotically best possible. An analogous result on representing the interior of P in the form p ₁ > 0, . . ., p _n >  0 is also given. For k ≤ m/log₂ m these statements remain valid for representations with arbitrary polynomials of degree not exceeding k.     

On Representation of a Solution to the Cauchy Problem by a Fourier Series in Sobolev-Orthogonal Polynomials Generated by Laguerre Polynomials

We consider the problem of representing a solution to the Cauchy problem for an ordinary differential equation as a Fourier series in polynomials l _r,k ^α (x) (k = 0, 1,...) that are Sobolev-orthonormal with respect to the inner product

$$\left\langle {f,g} \right\rangle = \sum\limits_{v = 0}^{r - 1} {{f^{(v)}}(0){g^{(v)}}} (0) + \int\limits_0^\infty {{f^{(r)}}(t)} {g^{(r)}}(t){t^\alpha }{e^{ - t}}dt$$

, and generated by the classical orthogonal Laguerre polynomials L _k ^α (x) (k = 0, 1,...). The polynomials l _r,k ^α (x) are represented as expressions containing the Laguerre polynomials L _n ^α?r (x). An explicit form of the polynomials l _r,k+r ^α (x) is established as an expansion in the powers x ^r+l , l = 0,..., k. These results can be used to study the asymptotic properties of the polynomials l _r,k ^α (x) as k→∞and the approximation properties of the partial sums of Fourier series in these polynomials.

     

Packing circles in the smallest circle: an adaptive hybrid algorithm

The circular packing problem (CPP) consists of packing n circles C _i of known radii r _i , i∈N={1,?…,?n}, into the smallest containing circle ?. The objective is to determine the coordinates (x _i ,?y _i ) of the centre of C _i , i∈N, as well as the radius r and centre (x,?y) of ?. CPP, which is a variant of the two-dimensional open-dimension problem, is NP hard. This paper presents an adaptive algorithm that incorporates nested partitioning within a tabu search and applies some diversification strategies to obtain a (near) global optimum. The tabu search is to identify the n circles’ ordering, whereas the nested partitioning is to determine the n circles’ positions that yield the smallest r. The computational results show the efficiency of the proposed algorithm.     

A generalized moment problem for self-adjoint operators

Let the sequence {λ _i } (i≧0) satisfy condition (1.1) and let {A _n} (n≧0) be a sequence of bounded self-adjoint operators over a complex Hilbert spaceH. We give a necessary and sufficient condition in order that {A _n} (n≧0) should possess the representation (1.2).