Duality between quasi-concave functions and monotone linkage functions

A function F defined on the family of all subsets of a finite ground set E is quasi-concave, if F(X∪Y)≥min{F(X),F(Y)} for all X,Y⊆E. Quasi-concave functions arise in many fields of mathematics and computer science such as social choice, graph theory, data mining, clustering and other fields. The maximization of a quasi-concave function takes, in general, exponential time. However, if a quasi-concave function is defined by an associated monotone linkage function, then it can be optimized by a greedy type algorithm in polynomial time. Recently, quasi-concave functions defined as minimum values of monotone linkage functions were considered on antimatroids, where the correspondence between quasi-concave and bottleneck functions was shown Kempner and Levit (2003) [6]. The goal of this paper is to analyze quasi-concave functions on different families of sets and to investigate their relationships with monotone linkage functions.     

Specialization of Appell's functions to univariate hypergeometric functions

Univariate specializations of Appell's hypergeometric functions F₁, F₂, F₃, F₄ satisfy ordinary Fuchsian equations of order at most 4. In special cases, these differential equations are of order 2 and could be simple (pullback) transformations of Euler's differential equation for the Gauss hypergeometric function. The paper classifies these cases, and presents corresponding relations between univariate specializations of Appell's functions and univariate hypergeometric functions. The computational aspect and interesting identities are discussed.     

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.     

Construction of bent functions from near-bent functions

We give a construction of bent functions in dimension 2m from near-bent functions in dimension 2m−1. In particular, we give the first ever examples of non-weakly-normal bent functions in dimensions 10 and 12, which demonstrates the significance of our construction.     

Explicitly B-preinvex functions

This paper introduces a new class of functions, to be referred to as explicitly B-preinvex functions. Some properties of explicitly B-preinvex functions are established, e.g., any local minimum of an explicitly B-preinvex function is also a global one and the summation of two functions, which are both B-preinvex and explicitly B-preinvex, is also a B-preinvex function and an explicitly B-preinvex function. Furthermore, it is shown that the explicit B-preinvexity, together with the intermediate-point B-preinvexity, implies B-preinvexity, while the explicit B-preinvexity, together with a lower semicontinuity, implies the B-preinvexity.     

On classes of analytic functions defined by convolution with incomplete beta functions

Carlson and Shaffer [SIAM J. Math. Anal. 15 (1984) 737-745] defined a convolution operator L(a,c) on the class A of analytic functions involving an incomplete beta function ?(a,c;z) as L(a,c)f=?(a,c)?f. We use this operator to introduce certain classes of analytic functions in the unit disk and study their properties including some inclusion results, coefficient and radius problems. It is shown that these classes are closed under convolution with convex functions.     

Complete monotonicity of some functions involving polygamma functions

In the present paper, we establish necessary and sufficient conditions for the functions x^α|ψ⁽ⁱ⁾(x+β)| and α|ψ⁽ⁱ⁾(x+β)|−x|ψ⁽ⁱ⁺¹⁾(x+β)| respectively to be monotonic and completely monotonic on (0,∞), where i∈N, α>0 and β≥0 are scalars, and ψ⁽ⁱ⁾(x) are polygamma functions.     

A class of uniform functions and its relationship with the class of measurable functions

Borel, Lebesgue, and Hausdorff described all uniformly closed families of real-valued functions on a set T whose algebraic properties are just like those of the set of all continuous functions with respect to some open topology on T. These families turn out to be exactly the families of all functions measurable with respect to some σ-additive and multiplicative ensembles on T. The problem of describing all uniformly closed families of bounded functions whose algebraic properties are just like those of the set of all continuous bounded functions remained unsolved. In the paper, a solution of this problem is given with the help of a new class of functions that are uniform with respect to some multiplicative families of finite coverings on T. It is proved that the class of uniform functions differs from the class of measurable functions.     

Existence results and gap functions for the generalized equilibrium problem with composed functions

In this paper we provide first existence results for solutions of the generalized equilibrium problem with composed functions (GEPC) under generalized convexity assumptions. Then we construct by employing some tools specific to the theory of conjugate duality two gap functions for (GEPC). The importance of these gap functions is to be seen in the fact that they equivalently characterize the solutions of an equilibrium problem. We also prove that for some particular instances of (GEPC) the gap functions we introduce here become among others the celebrated Auslender’s and Giannessi’s gap functions.     

Boolean functions with MacWilliams duality

We introduce a new class of Boolean functions for which the MacWilliams duality holds, called MacWilliams-dual functions, by considering a dual notion on Boolean functions. By using the MacWilliams duality, we prove the Gleason-type theorem on MacWilliams-dual functions. We show that a collection of MacWilliams-dual functions contains all the bent functions and all formally self-dual functions. We also obtain the Pless power moments for MacWilliams-dual functions. Furthermore, as an application, we prove the nonexistence of bent functions in 2n variables with minimum degree n?k for any nonnegative integer k and n ≥ N with some positive integer N under a certain condition.     

Unimodular functions

We introduce some classes of pseudo-boolean functions (the so-called ‘unimodular’, ‘completely unimodular’ and ‘unate’ ones), whose maximizations over the binary n-cube is reducible to a maximal flow problem.All such classes of functions are generalizations of classes previously investigated by Rhys and Balinski.It is shown that in the quadratic case the above three classes coincide, and that they also coincide with the class of those pseudo-boolean functions f such that a certain signed graph G_f associated with f is balanced.The latter characterization leads to a polynomial recognition algorithm.When G_f is a (signed) tree, a linear-time maximization algorithm is available.     

Log-convexity and log-concavity of hypergeometric-like functions

We find sufficient conditions for log-convexity and log-concavity for the functions of the forms a?∑fkk(a)xk, a?∑fkΓ(a+k)xk and a?∑fkxk/k(a). The most useful examples of such functions are generalized hypergeometric functions. In particular, we generalize the Turán inequality for the confluent hypergeometric function recently proved by Barnard, Gordy and Richards and log-convexity results for the same function recently proved by Baricz. Besides, we establish a reverse inequality which complements naturally the inequality of Barnard, Gordy and Richards. Similar results are established for the Gauss and the generalized hypergeometric functions. A conjecture about monotonicity of a quotient of products of confluent hypergeometric functions is made.     

Hyper-bent functions and cyclic codes

Bent functions are those Boolean functions whose Hamming distance to the Reed-Muller code of order 1 equal 2^n-1-2^n/2-1 (where the number n of variables is even). These combinatorial objects, with fascinating properties, are rare. Few constructions are known, and it is difficult to know whether the bent functions they produce are peculiar or not, since no way of generating at random bent functions on 8 variables or more is known.The class of bent functions contains a subclass of functions whose properties are still stronger and whose elements are still rarer. Youssef and Gong have proved the existence of such hyper-bent functions, for every even n. We prove that the hyper-bent functions they exhibit are exactly those elements of the well-known PS_ap class, introduced by Dillon, up to the linear transformations x?δx, . Hyper-bent functions seem still more difficult to generate at random than bent functions; however, by showing that they all can be obtained from some codewords of an extended cyclic code H_n with small dimension, we can enumerate them for up to 10 variables. We study the non-zeroes of H_n and we deduce that the algebraic degree of hyper-bent functions is n/2. We also prove that the functions of class PS_ap are some codewords of weight 2^n-1-2^n/2-1 of a subcode of H_n and we deduce that for some n, depending on the factorization of 2ⁿ-1, the only hyper-bent functions on n variables are the elements of the class , obtained from PS_ap by composing the functions by the transformations x?δx, δ≠0, and by adding constant functions. We prove that non- hyper-bent functions exist for n=4, but it is not clear whether they exist for greater n. We also construct potentially new bent functions for n=12.     

Superpositions of elementary arithmetic functions

A new concise proof of the following theorem is found: the system of four functions {x + y, x ? y, [x/y, 2 ^x } induces the class of Kalmar elementary functions. An elimination mode of bounded summation is used in the proof.     

Decomposition of weighted pseudo-almost periodic functions

First, we show by constructing two counterexamples that the decomposition of weighted pseudo-almost periodic functions is not unique in general. Then we prove that the decomposition of such functions is unique if PAP₀(X,ρ) is translation invariant, but not necessarily unique without the assumption. Moreover, we give an example to show that the mean value under a certain weight ρ may not exist for all almost periodic functions. With these results, we answer some fundamental questions on weighted pseudo-almost periodic functions.     

Strongly convex functions of higher order

The notion of strongly n-convex functions with modulus c>0 is introduced and investigated. Relationships between such functions and n-convex functions in the sense of Popoviciu as well as generalized convex functions in the sense of Beckenbach are given. Characterizations by derivatives are presented. Some results on strongly Jensen n-convex functions are also given.     

Ring structures on groups of arithmetic functions

Using the theory of Witt vectors, we define ring structures on several well-known groups of arithmetic functions, which in another guise are formal Dirichlet series. The set of multiplicative arithmetic functions over a commutative ring R is shown to have a unique functorial ring structure for which the operation of addition is Dirichlet convolution and the operation of multiplication restricted to the completely multiplicative functions coincides with point-wise multiplication. The group of additive arithmetic functions over R also has a functorial ring structure. In analogy with the ghost homomorphism of Witt vectors, there is a functorial ring homomorphism from the ring of multiplicative functions to the ring of additive functions that is an isomorphism if R is a Q-algebra. The group of rational arithmetic functions, that is, the group generated by the completely multiplicative functions, forms a subring of the ring of multiplicative functions. The latter ring has the structure of a Bin(R)-algebra, where Bin(R) is the universal binomial ring equipped with a ring homomorphism to R. We use this algebra structure to study the order of a rational arithmetic function, as well the powersfα for α∈Bin(R) of a multiplicative arithmetic function f. For example, we prove new results about the powers of a given multiplicative arithmetic function that are rational. Finally, we apply our theory to the study of the zeta function of a scheme of finite type over Z.     

Algebras generated by inner functions

Let A be a uniform algebra on a compact space X. An inner function is a function in A unimodular on X. For three algebras of type H^∞ we prove A is generated by its inner functions. Whenever A is generated by its inner functions we prove the unit ball of A is the closed convex ball of the inner functions.