Some estimates of thenth difference quotient of a function analytic in a convex region

Vilnius Technical University, Saulètekio 11, 2600 Vilnius, Lithuania. Translated from Lietuvos Matematikos Rinkinys, Vol. 35, No. 4, pp. 489–501, October–December, 1995.     

On the number of queries necessary to identify a permutation

Let p and q be two permutations over {1, 2,…, n}. We denote by m(p, q) the number of integers i, 1 ≤ i ≤ n, such that p(i) = q(i). For each fixed permutation p, a query is a permutation q of the same size and the answer a(q) to this query is m(p, q). We investigate the problem of finding the minimum number of queries required to identify an unknown permutation p. A polynomial-time algorithm that identifies a permutation of size n by O(n · log₂n) queries is presented. The lower bound of this problem is also considered. It is proved that the problem of determining the size of the search space created by a given set of queries and answers is #P-complete. Since this counting problem is essential for the analysis of the lower bound, a complete analysis of the lower bound appears infeasible. We conjecture, based on some preliminary analysis, that the lower bound is Ω(n · log₂n).     

Functions with a finite number of negative squares on semigroups

We consider indefinite functions on semigroups and their relation to representations in spaces with an indefinite metric. Special attention is given to functions of finite rank, where the space of representation is of finite dimension, and to functions for which the corresponding representation consists of bounded operators in Pontrjagin spaces.The authors wish to thankMarco Thill for useful remarks.     

Sums of squares in real analytic rings

Let be an analytic ring. We show: (1) has finite Pythagoras number if and only if its real dimension is , and (2) if every positive semidefinite element of is a sum of squares, then is real and has real dimension .

     

Sums of two squares in analytic rings

We study analytic singularities for which every positive semidefinite analytic function is a sum of two squares of analytic functions. This is a basic useful property of the plane, but difficult to check in other cases; in particular, what about , , or ? In fact, the unique positive examples we can find are the Brieskorn singularity, the union of two planes in 3-space and the Whitney umbrella. Conversely, we prove that a complete intersection with that property (other than the seven embedded surfaces already mentioned) must be a very simple deformation of the two latter, namely, In particular, except for the stems and , all singularities are real rational double points. Received April 4, 1997; in final form September 25, 1997     

A reliable argument principle algorithm to find the number of zeros of an analytic function in a bounded domain

Summary The argument principle is a natural and simple method to determine the number of zeros of an analytic functionf(z) in a bounded domainD. N, the number of zeros (counting multiplicities) off(z), is 1/2 times the change in Argf(z) asz moves along the closed contour D. Since the range of Argf(z) is (–, ] a critical point in the computational procedure is to assure that the discretization of D, {z _i ,i=1, ...,M}, is such that . Discretization control which may violate this inequality can lead to an unreliable algorithm. Mathematical theorems derived for the discretization of D lead to a completely reliable algorithm to computeN. This algorithm also treats in an elementary way the case when a zero is on or near the contour D. Numerical examples are given for the reliable algorithm formulated here and it is pointed out in these examples how inadequate discretization control can lead to failure of other algorithms.Dedicated to Professor Ivo Babuka in commemoration of his sixtieth birthdayThis research is part of the doctoral dissertation of this author     

On the number of zeros of an analytic perturbation of the identically zero function on a compact set

An upper bound for the number of isolated zeros of an analytic perturbation f(z, t) of the function f(z, 0) ≡ 0 on a compact set {z ∈ K ? ?} is obtained for small values of the parameter t ∈ ? ⁿ . The bound depends on an information about the Bautin ideal for the Taylor expansion of the function f with respect to z at one point of the compact set K (e.g., at 0) and on the maximal absolute value of f in a neighborhood of K.     

On the number of Sudoku squares

We provide an upper bound on the number of $n^2\times n^2$ Sudoku squares, and explain intuitively why there is reason to believe that the bound is tight up to a multiplicative factor of a much smaller order of magnitude. A similar bound is established for Sudoku squares with rectangular regions.     

The number of distinct latin squares as a group-theoretical constant

It is shown that the number l_n of all distinct Latin squares of the nth order appears as a structure constant of the algebra defined on the Magic squares of the same order. The algebra is isomorphic to the algebra of double cosets of the symmetric group of degree n² with respect to the intransitive subgroup of all substitutions in the n sets of transitivity, each set being of cardinality n. The representation theory makes it possible then to express l_n in terms of eigenvalues of a certain element of the algebra.     

On bounded functions with a finite number of negative squares

In the case of a locally compact abelian groupG we give a characterization of bounded continuous functions onG which have a finite number of negative squares. We show that these functions can be regarded in a certain sense as a special case of positive definite functions.