Improving the high order nonlinearity lower bound for Boolean functions with given algebraic immunity

Algebraic immunity is a recently introduced cryptographic parameter for Boolean functions used in stream ciphers. If pAI(f) and pAI(f⊕1) are the minimum degree of all annihilators of f and f⊕1 respectively, the algebraic immunity AI(f) is defined as the minimum of the two values. Several relations between the new parameter and old ones, like the degree, the r-th order nonlinearity and the weight of the Boolean function, have been proposed over the last few years.In this paper, we improve the existing lower bounds of the r-th order nonlinearity of a Boolean function f with given algebraic immunity. More precisely, we introduce the notion of complementary algebraic immunity defined as the maximum of pAI(f) and pAI(f⊕1). The value of can be computed as part of the calculation of AI(f), with no extra computational cost. We show that by taking advantage of all the available information from the computation of AI(f), that is both AI(f) and , the bound is tighter than all known lower bounds, where only the algebraic immunity AI(f) is used.     

A note on shadowing with chain transitivity

Let f : X → X be a continuous map of a compact metric space X. The map f induces in a natural way a map f_M on the space M(X) of probability measures on X, and a transformation f_K on the space K(X) of closed subsets of X. In this paper, we show that if (X, f) is a chain transitive system with shadowing property, then exactly one of the following two statements holds:

(a)

fⁿ and (f_K)ⁿ are syndetically sensitive for all n ? 1.

(b)

fⁿ and (f_K)ⁿ are equicontinuous for all n ? 1.

In particular, we show that for a continuous map f : X → X of a compact metric space X with infinite elements, if f is a chain transitive map with the shadowing property, then fⁿ and (f_K)ⁿ are syndetically sensitive for all n ? 1. Also, we show that if f_M (resp. f_K) is chain transitive and syndetically sensitive, and f_M (resp. f_K) has the shadowing property, then f is sensitive.In addition, we introduce the notion of ergodical sensitivity and present a sufficient condition for a chain transitive system (X, f) (resp. (M(X), f_M)) to be ergodically sensitive. As an application, we show that for a L-hyperbolic homeomorphism f of a compact metric space X, if f has the AASP, then fⁿ is syndetically sensitive and multi-sensitive for all n ? 1.     

A distribution property of the solutions of a congruence modulo a large prime

A regularity in the distribution of the solutions of the congruence f(X₁ ,…, X_n)  0 (modp) is shown.     

Minimal ranks of some quaternion matrix expressions with applications

Suppose that p(X, Y) = A − BX − X^(∗)B^(∗) − CYC^(∗) and q(X, Y) = A − BX + X^(∗)B^(∗) − CYC^(∗) are quaternion matrix expressions, where A is persymmetric or perskew-symmetric. We in this paper derive the minimal rank formula of p(X, Y) with respect to pair of matrices X and Y = Y^(∗), and the minimal rank formula of q(X, Y) with respect to pair of matrices X and Y = −Y^(∗). As applications, we establish some necessary and sufficient conditions for the existence of the general (persymmetric or perskew-symmetric) solutions to some well-known linear quaternion matrix equations. The expressions are also given for the corresponding general solutions of the matrix equations when the solvability conditions are satisfied. At the same time, some useful consequences are also developed.     

Uniformity over primes of tamely ramified splittings

We fix a prime p and let f(X) vary over all monic integer polynomials of fixed degree n. Given any possible shape of a tamely ramified splitting of p in an extension of degree n, we prove that there exists a rational function φ(X)∈ℚ(X) such that the density of the monic integer polynomials f(X) for which the splitting of p has the given shape in ℚ[X]/f(X) is φ(p) (here reducible polynomials can be neglected). As a corollary, we prove that, for p≥n, the density of irreducible monic polynomials of degree n in ℤ _p [X] is the value at p of a rational function φ _n (X)∈ℚ(X). All rational functions involved are effectively computable. Received: 15 September 1998 / Revised version: 21 October 1999     

Maps preserving the nilpotency of products of operators

Let B(X) be the algebra of all bounded linear operators on the Banach space X, and let N(X) be the set of nilpotent operators in B(X). Suppose ?:B(X)→B(X) is a surjective map such that A,B∈B(X) satisfy AB∈N(X) if and only if ?(A)?(B)∈N(X). If X is infinite dimensional, then there exists a map f:B(X)→C?{0} such that one of the following holds:

(a)

There is a bijective bounded linear or conjugate-linear operator S:X→X such that ? has the form A?S[f(A)A]S^-1.

(b)

The space X is reflexive, and there exists a bijective bounded linear or conjugate-linear operator S : X′ → X such that ? has the form A ? S[f(A)A′]S⁻¹.

If X has dimension n with 3 ? n < ∞, and B(X) is identified with the algebra M_n of n × n complex matrices, then there exist a map f:M_n→C?{0}, a field automorphism ξ:C→C, and an invertible S ∈ M_n such that ? has one of the following forms:

     

Inner functions as improving multipliers

If X⊂Y are two classes of analytic functions in the unit disk D and θ is an inner function, θ is said to be (X,Y)-improving, if every function f∈X satisfying fθ∈Y must actually satisfy fθ∈X. This notion has been recently introduced by K.M. Dyakonov. In this paper we study the (X,Y)-improving inner functions for several pairs of spaces (X,Y). In particular, we prove that for any p∈(0,1) the (Qp,BMOA)-improving inner functions and the (Qp,B)-improving inner functions are precisely the inner functions which belong to the space Qp. Here, B is the Bloch space. We also improve some results of Dyakonov on the subject regarding Lipschitz spaces and Besov spaces.     

Group-valued continuous functions with the topology of pointwise convergence

Let G be a topological group with the identity element e. Given a space X, we denote by Cp(X,G) the group of all continuous functions from X to G endowed with the topology of pointwise convergence, and we say that X is: (a) G-regular if, for each closed set F⊆X and every point x∈X?F, there exist f∈Cp(X,G) and g∈G?{e} such that f(x)=g and f(F)⊆{e}; (b) G^?-regular provided that there exists g∈G?{e} such that, for each closed set F⊆X and every point x∈X?F, one can find f∈Cp(X,G) with f(x)=g and f(F)⊆{e}. Spaces X and Y are G-equivalent provided that the topological groups Cp(X,G) and Cp(Y,G) are topologically isomorphic.We investigate which topological properties are preserved by G-equivalence, with a special emphasis being placed on characterizing topological properties of X in terms of those of Cp(X,G). Since R-equivalence coincides with l-equivalence, this line of research “includes” major topics of the classical Cp-theory of Arhangel'ski? as a particular case (when G=R).We introduce a new class of TAP groups that contains all groups having no small subgroups (NSS groups). We prove that: (i) for a given NSS group G, a G-regular space X is pseudocompact if and only if Cp(X,G) is TAP, and (ii) for a metrizable NSS group G, a G^?-regular space X is compact if and only if Cp(X,G) is a TAP group of countable tightness. In particular, a Tychonoff space X is pseudocompact (compact) if and only if Cp(X,R) is a TAP group (of countable tightness). Demonstrating the limits of the result in (i), we give an example of a precompact TAP group G and a G-regular countably compact space X such that Cp(X,G) is not TAP.We show that Tychonoff spaces X and Y are T-equivalent if and only if their free precompact Abelian groups are topologically isomorphic, where T stays for the quotient group R/Z. As a corollary, we obtain that T-equivalence implies G-equivalence for every Abelian precompact group G. We establish that T-equivalence preserves the following topological properties: compactness, pseudocompactness, σ-compactness, the property of being a Lindelöf Σ-space, the property of being a compact metrizable space, the (finite) number of connected components, connectedness, total disconnectedness. An example of R-equivalent (that is, l-equivalent) spaces that are not T-equivalent is constructed.     

On the existence of continuous (approximate) roots of algebraic equations

The present paper considers the existence of continuous roots of algebraic equations with coefficients being continuous functions defined on compact Hausdorff spaces. For a compact Hausdorff space X, C(X) denotes the Banach algebra of all continuous complex-valued functions on X with the sup norm ∥⋅_∥∞. The algebra C(X) is said to be algebraically closed if each monic algebraic equation with C(X) coefficients has a root in C(X). First we study a topological characterization of a first-countable compact (connected) Hausdorff space X such that C(X) is algebraically closed. The result has been obtained by Countryman Jr, Hatori-Miura and Miura-Niijima and we provide a simple proof for metrizable spaces.Also we consider continuous approximate roots of the equation zn−f=0 with respect to z, where f∈C(X), and provide a topological characterization of compact Hausdorff space X with dimX?1 such that the above equation has an approximate root in C(X) for each f∈C(X), in terms of the first ?ech cohomology of X.     

Atomic decomposition and boundedness criterion of operators on multi-parameter hardy spaces of homogeneous type

The main purpose of this paper is to derive a new ( p, q)-atomic decomposition on the multi-parameter Hardy space Hp (X1 × X2 ) for 0 p0 p ≤ 1 for some p0 and all 1 q ∞, where X1 × X2 is the product of two spaces of homogeneous type in the sense of Coifman and Weiss. This decomposition converges in both Lq (X1 × X2 ) (for 1 q ∞) and Hardy space Hp (X1 × X2 ) (for 0 p ≤ 1). As an application, we prove that an operator T1, which is bounded on Lq (X1 × X2 ) for some 1 q ∞, is bounded from Hp (X1 × X2 ) to Lp (X1 × X2 ) if and only if T is bounded uniformly on all (p, q)-product atoms in Lp (X1 × X2 ). The similar boundedness criterion from Hp (X1 × X2 ) to Hp (X1 × X2 ) is also obtained.     

Left inverses of matrices with polynomial decay

It is known that the algebra of Schur operators on ?² (namely operators bounded on both ?¹ and ?^∞) is not inverse-closed. When ?²=?²(X) where X is a metric space, one can consider elements of the Schur algebra with certain decay at infinity. For instance if X has the doubling property, then Q. Sun has proved that the weighted Schur algebra Aω(X) for a strictly polynomial weight ω is inverse-closed. In this paper, we prove a sharp result on left-invertibility of the these operators. Namely, if an operator A∈Aω(X) satisfies ‖Afp_‖?‖fp_‖, for some 1?p?∞, then it admits a left-inverse in Aω(X). The main difficulty here is to obtain the above inequality in ?². The author was both motivated and inspired by a previous work of Aldroubi, Baskarov and Krishtal (2008) [1], where similar results were obtained through different methods for X=Zd, under additional conditions on the decay.     

Exact number of positive solutions for semipositone problems

This paper is concerned with the exact number of positive solutions for the boundary value problem ^′(|y^′|^p−2y^′)+λf(y)=0 and y(−1)=y(1)=0, where p>1 and λ>0 is a positive parameter. We consider the case in which both f(u) and g(u)=(p−1)f(u)−uf^′(u) change sign exactly once from negative to positive on (0,∞).     

Extensions of a theorem of Cauchy-Liouville

We deal with the equations Δpu+f(u)=0 and Δpu+(p−1)g(u)p|∇u|+f(u)=0 in RN, where g(t) is a continuous function in (0,∞), p>1 and f(t) is a smooth function for t>0. Under appropriate conditions on g and f we show that the corresponding equation cannot have nontrivial non-negative entire solutions.     

Marcinkiewicz-summability of multi-dimensional Fourier transforms and Fourier series

A generalization of Marcinkiewicz-summability of multi-dimensional Fourier transforms and Fourier series is investigated with the help of a continuous function θ. Under some weak conditions on θ we show that the maximal operator of the Marcinkiewicz-θ-means of a tempered distribution is bounded from Hp(Xd) to Lp(Xd) for all d/(d+α)<p?∞ and, consequently, is of weak type (1,1), where 0<α?1 is depending only on θ and X=R or X=T. As a consequence we obtain a generalization of a summability result due to Marcinkiewicz and Zhizhiashvili for d-dimensional Fourier transforms and Fourier series, more exactly, the Marcinkiewicz-θ-means of a function f∈L₁(Xd) converge a.e. to f. Moreover, we prove that the Marcinkiewicz-θ-means are uniformly bounded on the spaces Hp(Xd) and so they converge in norm (d/(d+α)<p<∞). Similar results are shown for conjugate functions. Some special cases of the Marcinkiewicz-θ-summation are considered, such as the Fejér, Cesàro, Weierstrass, Picar, Bessel, de La Vallée-Poussin, Rogosinski and Riesz summations.     

Positive solutions for the one-dimensional p-Laplacian

In this paper, the criterion for the existence of at least one positive solution of the one-dimensional p-Laplacian (b(t)Φ(u)′ + c(t)f(u) = 0, are obtained, where Φ(u) = |u|^p−1u, p > 0 is a constant, and b(t) > 0 for t > 0. The method used in this paper is shooting method.     

On the Hyers-Ulam-Rassias stability of functional equations in n-variables

In this paper we investigate a generalization of the Hyers-Ulam-Rassias stability for a functional equation of the form f(φ(X))=?(X)f(X)+ψ(X) and the stability in the sense of Ger for the functional equation of the form f(φ(X))=?(X)f(X), where X lie in n-variables. As a consequence, we obtain a stability result in the sense of Hyers-Ulam-Rassias, Gǎvruta, and Ger for some well-known equations such as the gamma, beta, and G-function type's equations.     

Generic uniqueness of equilibrium points

Let X be a nonempty, convex and compact subset of normed linear space E (respectively, let X be a nonempty, bounded, closed and convex subset of Banach space E and A be a nonempty, convex and compact subset of X) and f:X×X→R be a given function, the uniqueness of equilibrium point for equilibrium problem which is to find x^∗∈X (respectively, x^∗∈A) such that f(x^∗,y)≥0 for all y∈X (respectively, f(x^∗,y)≥0 for all y∈A) is studied with varying f (respectively, with both varying f and varying A). The results show that most of equilibrium problems (in the sense of Baire category) have unique equilibrium point.     

Ordinals and set-valued zero-selections for hyperspaces

A continuous zero-selection f for the Vietoris hyperspace F(X) of the nonempty closed subsets of a space X is a Vietoris continuous map f:F(X)→X which assigns to every nonempty closed subset an isolated point of it. It is well known that a compact space X has a continuous zero-selection if and only if it is an ordinal space, or, equivalently, if X can be mapped onto an ordinal space by a continuous one-to-one surjection. In this paper, we prove that a compact space X has an upper semi-continuous set-valued zero-selection for its Vietoris hyperspace F(X) if and only if X can be mapped onto an ordinal space by a continuous finite-to-one surjection.