Complexity of prime-dimensional sequences over a finite field

V.?I. Arnold has recently defined the complexity of a sequence of n zeros and ones with the help of the operator of finite differences. In this paper we describe the results obtained for almost most complex sequences of elements of a finite field, whose dimension n is a prime number. We prove that, with n→∞, this property is inherent in almost all sequences, while the values of multiplicative functions possess this property with any n different from the characteristic of the field. We also describe the prime values of the parameter n which make the logarithmic function almost most complex. All these sequences reveal a stronger complexity; its algebraic sense is quite clear.     

On the symmetric properties of APN functions

We study the symmetric properties of APN functions as well as the structure and properties of the range of an arbitrary APN function. We prove that there is no permutation of variables that preserves the values of an APN function. Upper bounds for the number of symmetric coordinate Boolean functions in an APN function and its coordinate functions invariant under a cyclic shift are obtained. For n ≤ 6, some upper bounds for the maximal number of identical values of an APN function are given and a lower bound is found for different values of an arbitrary APN function of n variables.     

Relating three nonlinearity parameters of vectorial functions and building APN functions from bent functions

We survey the properties of two parameters introduced by C. Ding and the author for quantifying the balancedness of vectorial functions and of their derivatives. We give new results on the distribution of the values of the first parameter when applied to F + L, where F is a fixed function and L ranges over the set of linear functions: we show an upper bound on the nonlinearity of F by means of these values, we determine then the mean of these values and we show that their maximum is a nonlinearity parameter as well, we prove that the variance of these values is directly related to the second parameter. We briefly recall the known constructions of bent vectorial functions and introduce two new classes obtained with Gregor Leander. We show that bent functions can be used to build APN functions by concatenating the outputs of a bent (n, n/2)-function and of some other (n, n/2)-function. We obtain this way a general infinite class of quadratic APN functions. We show that this class contains the APN trinomials and hexanomials introduced in 2008 by L. Budaghyan and the author, and a class of APN functions introduced, in 2008 also, by Bracken et al.; this gives an explanation of the APNness of these functions and allows generalizing them. We also obtain this way the recently found Edel?CPott cubic function. We exhibit a large number of other sub-classes of APN functions. We eventually design with this same method classes of quadratic and non-quadratic differentially 4-uniform functions.     

New integral representations of nth order convex functions

In this paper we give an integral representation of an n-convex function f in general case without additional assumptions on function f. We prove that any n-convex function can be represented as a sum of two (n+1)-times monotone functions and a polynomial of degree at most n. We obtain a decomposition of n-Wright-convex functions which generalizes and complements results of Maksa and Páles (2009) [13]. We define and study relative n-convexity of n-convex functions. We introduce a measure of n-convexity of f. We give a characterization of relative n-convexity in terms of this measure, as well as in terms of nth order distributional derivatives and Radon-Nikodym derivatives. We define, study and give a characterization of strong n-convexity of an n-convex function f in terms of its derivative f(n+1)(x) (which exists a.e.) without additional assumptions on differentiability of f. We prove that for any two n-convex functions f and g, such that f is n-convex with respect to g, the function g is the support for the function f in the sense introduced by W?sowicz (2007) [29], up to polynomial of degree at most n.     

Lattice Algorithms for Multivariate L ∞ Approximation in the Worst-Case Setting

We approximate d-variate functions from weighted Korobov spaces with the error of approximation defined in the L _∞ sense. We study lattice algorithms and consider the worst-case setting in which the error is defined by its worst-case behavior over the unit ball of the space of functions. A lattice algorithm is specified by a generating (integer) vector. We propose three choices of such vectors, each corresponding to a different search criterion in the component-by-component construction. We present worst-case error bounds that go to zero polynomially with n ^?1, where n is the number of function values used by the lattice algorithm. Under some assumptions on the weights of the function space, the worst-case error bounds are also polynomial in d, in which case we have (polynomial) tractability, or even independent of d, in which case we have strong (polynomial) tractability. We discuss the exponents of n ^?1 and stress that we do not know if these exponents can be improved.     

Optimal recovery of functions analytical in a half-plane

On the class of functions analytical and bounded in a half-plane with bounded derivative of order n ≥ 0, we solve problems of optimal recovery of values of a function and its derivatives of order m ≥ 0, using the restriction of the spectral function. We obtain appropriate exact inequalities for functions analytical in a half-plane.     

Topologically inseparable functions II: Infinitary case

Given a set A and a function A: A → A, we study the set of all functions g: A → A that are continuous for all topologies for which f continuous. We prove that in a sense to be made precise in the text, for any essentially infinitary function f, any non-constant such g equals f ⁿ , for some n∈ ?. We also prove a similar result for the clone of n-ary functions from A ⁿ → A.     

Merging asymptotic expansions for cooperative gamblers in generalized St. Petersburg games

Merging asymptotic expansions are established for the distribution functions of suitably centered and normed linear combinations of winnings in a full sequence of generalized St. Petersburg games, where a linear combination is viewed as the share of any one of n cooperative gamblers who play with a pooling strategy. The expansions are given in terms of Fourier-Stieltjes transforms and are constructed from suitably chosen members of the classes of subsequential semistable infinitely divisible asymptotic distributions for the total winnings of the n players and from their pooling strategy, where the classes themselves are determined by the two parameters of the game. For all values of the tail parameter, the expansions yield best possible rates of uniform merge. Surprisingly, it turns out that for a subclass of strategies, not containing the averaging uniform strategy, our merging approximations reduce to asymptotic expansions of the usual type, derived from a proper limiting distribution. The Fourier-Stieltjes transforms are shown to be numerically invertible in general and it is also demonstrated that the merging expansions provide excellent approximations even for very small n.     

Optimal recovery of isotropic classes of rth differentiable multivariate functions

Estimates are given for the optimal recovery of functions in d variables, which are known to have (r?1)st absolutely continuous and rth bounded derivatives in any direction over, either a bounded convex d-dimensional body G, or which are periodic over a d dimensional lattice. The information is the values of the function and all its derivatives of order less than r at n points. We obtain some asymptotic estimates for this problem, and some exact results for several special cases which contain the results of Babenko, Borodachov, and Skorokhodov.     

Covering moving points with anchored disks

Consider a set of mobile clients represented by n points in the plane moving at constant speed along n different straight lines. We study the problem of covering all mobile clients using a set of k disks centered at k fixed centers. Each disk exists only at one instant and while it does, covers any client within its coverage radius. The task is to select an activation time and a radius for each disk such that every mobile client is covered by at least one disk. In particular, we study the optimization problem of minimizing the maximum coverage radius. First we prove that, although the static version of the problem is polynomial, the kinetic version is NP-hard. Moreover, we show that the problem is not approximable by a constant factor (unless P = NP). We then present a generic framework to solve it for fixed values of k, which in turn allows us to solve more general optimization problems. Our algorithms are efficient for constant values of k.     

Differentiability of the volume of a region enclosed by level sets

The level of a function f on Rn encloses a region. The volume of a region between two such levels depends on both levels. Fixing one of them the volume becomes a function of the remaining level. We show that if the function f is smooth, the volume function is again smooth for regular values of f. For critical values of f the volume function is only finitely differentiable. The initial motivation for this study comes from Radiotherapy, where such volume functions are used in an optimization process. Thus their differentiability properties become important.     

Laced Boolean functions and subset sum problems in finite fields

In this paper, we investigate some algebraic and combinatorial properties of a special Boolean function on n variables, defined using weighted sums in the residue ring modulo the least prime p≥n. We also give further evidence relating to a question raised by Shparlinski regarding this function, by computing accurately the Boolean sensitivity, thus settling the question for prime number values p=n. Finally, we propose a generalization of these functions, which we call laced functions, and compute the weight of one such, for every value of n.     

SOME PROPERTIES OF HOLOMORPHIC CLIFFORDIAN FUNCTIONS IN COMPLEX CLIFFORD ANALYSIS

In this article, we mainly develop the foundation of a new function theory of several complex variables with values in a complex Clifford algebra defined on some subdomains of Cn+1, so-called complex holomorphic Cliffordian functions. We define the complex holomorphic Cliffordian functions, study polynomial and singular solutions of the equation D△mf=0, obtain the integral representation formula for the complex holomorphic Cliffordian functions with values in a complex Clifford algebra defined on some submanifolds of Cn+1, deduce the Taylor expansion and the Laurent expansion for them and prove an invariance under an action of Lie group for them.     

Functions with derivatives given by polynomials in the function itself or a related function

We construct the set of holomorphic functions S ₁ = {f: Ω_f ? ? → ?} whose members have n-th order derivatives which are given by a polynomial of degree n+1 in the function itself. We also construct the set of holomorphic functions S ₂ = {g: Ω_g ? ? → ?} whose members have n-th order derivatives which are given by the product of the function itself with a polynomial of degree n in an element of S ₁. The union S ₁ ∪ S ₂ contains all the hyperbolic and trigonometric functions. We study the properties of the polynomials involved and derive explicit expressions for them. As particular results, we obtain explicit and elegant formulas for the n-th order derivatives of the hyperbolic functions tanh, sech, coth and csch and the trigonometric functions tan, sec, cot and csc.     

Parallel and k-out-of-n: G systems with nonidentical components and their mean residual life functions

A system with n independent components which has a k-out-of-n: G structure operates if at least k components operate. Parallel systems are 1-out-of-n: G systems, that is, the system goes out of service when all of its components fail. This paper investigates the mean residual life function of systems with independent and nonidentically distributed components. Some examples related to some lifetime distribution functions are given. We present a numerical example for evaluating the relationship between the mean residual life of the k-out-of-n: G system and that of its components.     

Newton's Problem of the Body of Minimal Resistance in the Class of Convex Developable Functions

We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height M > 0 [4] in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non–radial) minimizer in accordance with the results of [9]. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with n sides centered in the disc, and numerical experiments indicate that the natural number n > 2 is a non–decreasing function of M. The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height M.     

On the number of partitions of n into k different parts

We study the number of partitions of n into k different parts by constructing a generating function. As an application, we will prove mysterious identities involving convolution of divisor functions and a sum over partitions. By using a congruence property of the overpartition function, we investigate values of a certain convolution sum of two divisor functions modulo 8.     

Method of analytic continuation for the inverse spherical mean transform in constant curvature spaces

The following problem arises in thermoacoustic tomography and has intimate connection with PDEs and integral geometry. Reconstruct a function f supported in an n-dimensional ball B given the spherical means of f over all geodesic spheres centered on the boundary of B. We propose a new approach to this problem, which yields explicit reconstruction formulas in arbitrary constant curvature space, including euclidean space ? ⁿ , the n-dimensional sphere, and hyperbolic space. The main idea is analytic continuation of the corresponding operator families. The results are applied to inverse problems for a large class of Euler-Poisson-Darboux equations in constant curvature spaces of arbitrary dimension.     

A convex representation of totally balanced games

We analyze the least increment function, a convex function of n variables associated to an n-person cooperative game. Another convex representation of cooperative games, the indirect function, has previously been studied. At every point the least increment function is greater than or equal to the indirect function, and both functions coincide in the case of convex games, but an example shows that they do not necessarily coincide if the game is totally balanced but not convex. We prove that the least increment function of a game contains all the information of the game if and only if the game is totally balanced. We also give necessary and sufficient conditions for a function to be the least increment function of a game as well as an expression for the core of a game in terms of its least increment function.