On designated-weight Boolean functions with highest algebraic immunity

Algebraic immunity has been considered as one of cryptographically significant properties for Boolean functions. In this paper, we study ∑d-1 i=0 (ni)-weight Boolean functions with algebraic immunity achiev-ing the minimum of d and n - d + 1, which is highest for the functions. We present a simpler sufficient and necessary condition for these functions to achieve highest algebraic immunity. In addition, we prove that their algebraic degrees are not less than the maximum of d and n - d + 1, and for d = n1 +2 their nonlinearities equalthe minimum of ∑d-1 i=0 (ni) and ∑ d-1 i=0 (ni). Lastly, we identify two classes of such functions, one having algebraic degree of n or n-1.     

The normal ΔH-matrices with connection to some Jacobi-like methods

The ΔH-matrices appear in the context of certain maximization and minimization problems. The following purely algebraic problem, arising in connection with certain norm-reducing Jacobi-type algorithms is treated: When is a normal ΔH-matrix diagonal? Final results are obtained in the cases n = 3 and n = 4, and in general for the attractive normal ΔH-matrices.     

Quaternionic pryms and Hodge classes

Abelian varieties of dimension 2n on which a definite quaternion algebra acts are parametrized by symmetrical domains of dimension n(n−1)/2. Such abelian varieties have primitive Hodge classes in the middle dimensional cohomology group. In general, it is not clear that these are cycle classes. In this paper we show that a particular 6-dimensional family of such 8-folds are Prym varieties and we use the method of Schoen to show that all Hodge classes on the general abelian variety in this family are algebraic. We also consider Hodge classes on certain 5-dimensional subfamilies and relate these to the Hodge conjecture for abelian 4-folds.     

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.     

Determination of the limits for multivariate rational functions

The purpose of this paper is to solve the problem of determining the limits of multivariate rational functions.It is essential to decide whether or not limxˉ→0f g=0 for two non-zero polynomials f,g∈R[x1,...,xn]with f(0,...,0)=g(0,...,0)=0.For two such polynomials f and g,we establish two necessary and sufcient conditions for the rational functionf g to have its limit 0 at the origin.Based on these theoretic results,we present an algorithm for deciding whether or not lim(x1,...,xn)→(0,...,0)f g=0,where f,g∈R[x1,...,xn]are two non-zero polynomials.The design of our algorithm involves two existing algorithms:one for computing the rational univariate representations of a complete chain of polynomials,another for catching strictly critical points in a real algebraic variety.The two algorithms are based on the well-known Wu’s method.With the aid of the computer algebraic system Maple,our algorithm has been made into a general program.In the final section of this paper,several examples are given to illustrate the efectiveness of our algorithm.     

Enumeration of arrays of a given size

Enumeration of arrays whose row and column sums are specified have been studied by a number of people. It has been determined that the function that enumerates square arrays of dimension n, whose rows and columns sum to a fixed non-negative integer r, is a polynomial in r of degree (n ? 1)².In this paper we consider rectangular arrays whose rows sum to a fixed non-negative integer r and whose columns sum to a fixed non-negative integer s, determined by ns = mr. in particular, we show that the functions which enumerate 2 × n and 3 × n arrays with fixed row sums $\text{nr}\text{(2, n)}$ and $\text{nr}\text{(3, n)}$, where the symbol (a, b) denotes the greatest common divisor of a and b, and fixed column sums, are polynomials in r of degrees (n ? 1) and 2(n ? 1) respectively. We have found simple formulas to evaluate these polynomials for negative values, - r, and we show that for certain small negative integers our polynomials will always be zero. We also considered the generating functions of these polynomials and show that they are rational functions of degrees less than zero, whose denominators are of the forms (1 ? y)ⁿ and (1 ? y)²ⁿ?1 respectively and whose numerators are polynomials in y whose coefficients satisfy certain properties. In the last section we list the actual polynomials and generating functions in the 2 × n and 3 × n cases for small specific values of n.     

Several classes of even-variable 1-resilient rotation symmetric Boolean functions with high algebraic degree and nonlinearity

Recent research shows that the class of rotation symmetric Boolean functions is potentially rich in functions of cryptographic significance. In this paper, some classes of 2m-variable (m is an odd integer) 1-resilient rotation symmetric Boolean functions are got, whose nonlinearity and algebraic degree are studied. For the first time, we obtain 2m-variable 1-resilient rotation symmetric Boolean functions having high nonlinearity and optimal algebraic degree. In addition, we obtain a class of non-linear rotation symmetric 1-resilient function for every $n\ge 5$, and a class of quadratic rotation symmetric $(k?1)$-resilient function of $n=3k$ variables, where k is an integer.     

Archimedean zeta integrals on GL n × GL m and SO2n+1 × GL m

In this paper, we evaluate archimedean zeta integrals for automorphic L-functions on GL _n × GL _n-1+? and on SO_2n+1 × GL _n+? , for ? = ?1, 0, and 1. In each of these cases, the zeta integrals in question may be expressed as Mellin transforms of products of class one Whittaker functions. Here, we obtain explicit expressions for these Mellin transforms in terms of Gamma functions and Barnes integrals. When ? = 0 or ? = 1, the archimedean zeta integrals amount to integrals over the full torus. We show that, as has been predicted by Bump for such domains of integration, these zeta integrals are equal to the corresponding local L-factors—which are simple rational combinations of Gamma functions. (In the cases of GL _n × GL _n-1 and GL _n × GL _n this has, in large part, been shown previously by the second author of the present work, though the results here are more general in that they do not require the assumption of trivial central characters. Our techniques here are also quite different. New formulas for GL(n, R) Whittaker functions, obtained recently by the authors of this work, allow for substantially simplified computations). In the case ? = ?1, we express our archimedean zeta integrals explicitly in terms of Gamma functions and certain Barnes-type integrals. These evaluations rely on new recursive formulas, derived herein, for GL(n, R) Whittaker functions. Finally, we indicate an approach to certain unramified calculations, on SO_2n+1 × GL _n and SO_2n+1 × GL _n+1, that parallels our method herein for the corresponding archimedean situation. While the unramified theory has already been treated using more direct methods, we hope that the connections evoked herein might facilitate future archimedean computations.     

Asymptotic distributions of functions of the eigenvalues of sample covariance matrix and canonical correlation matrix in multivariate time series

Let S = (1/n) Σ_t=1ⁿ X(t) X(t)′, where X(1), …, X(n) are p × 1 random vectors with mean zero. When X(t) (t = 1, …, n) are independently and identically distributed (i.i.d.) as multivariate normal with mean vector 0 and covariance matrix Σ, many authors have investigated the asymptotic expansions for the distributions of various functions of the eigenvalues of S. In this paper, we will extend the above results to the case when {X(t)} is a Gaussian stationary process. Also we shall derive the asymptotic expansions for certain functions of the sample canonical correlations in multivariate time series. Applications of some of the results in signal processing are also discussed.     

Solving Linear Systems Whose Elements Are Nonlinear Functions of Intervals

The paper addresses the problem of solving linear algebraic systems the elements of which are, in the general case, nonlinear functions of a given set of independent parameters taking on their values within prescribed intervals. Three kinds of solutions are considered: (i) outer solution, (ii) interval hull solution, and (iii) inner solution. A simple direct method for computing a tight outer solution to such systems is suggested. It reduces, essentially, to inverting a real matrix and solving a system of real linear equations whose size n is the size of the original system. The interval hull solution (which is a NP-hard problem) can be easily determined if certain monotonicity conditions are fulfilled. The resulting method involves solving n+1 interval outer solution problems as well as 2n real linear systems of size n. A simple iterative method for computing an inner solution is also given. A numerical example illustrating the applicability of the methods suggested is solved.     

Boolean functions with maximum algebraic immunity: further extensions of the Carlet–Feng construction

The algebraic immunity of Boolean functions is studied in this paper. More precisely, having the prominent Carlet–Feng construction as a starting point, we propose a new method to construct a large number of functions with maximum algebraic immunity. The new method is based on deriving new properties of minimal codewords of the punctured Reed–Muller code \(\mathrm{RM}^{\star }(\lfloor \frac{n-1}{2}\rfloor ,n)\) for any n, allowing—if n is odd—for efficiently generating large classes of new functions that cannot be obtained by other known constructions. It is shown that high nonlinearity, as well as good behavior against fast algebraic attacks, is also attainable.     

Extrapolating the mean-values of multiplicative functions

It is shown that certain commonly occurring conditions may be factored out of sums of multiplicative arithmetic functions.A function is arithmetic if it is defined on the positive integers. Those complex-valued arithmetic functions g which satisfy the relation g(ab) = g(a)g(b) for all coprime pairs of positive integers a, b are here called multiplicative. In this paper g will be a multiplicative function which satisfies |g(n)| ≤ 1 for all positive integers n.     

Schläfli modular equations for generalized Weber functions

Sets of appropriately normalized eta quotients, that we call level n Weber functions, are defined, and certain identities generalizing Weber function identities are proved for these functions. Schläfli type modular equations are explicitly obtained for Generalized Weber Functions associated with a Fricke group Γ⁰(n)⁺, for n=2,3,5,7,11,13 and 17.     

Generalized Büchi’s problem for algebraic functions and meromorphic functions

Büchi’s nth power problem asks is there a positive integer M such that any sequence ${(x_1^n,\ldots ,x_M^n)}$ of nth powers of integers with nth difference equal to n! is necessarily a sequence of nth powers of successive integers. In this paper, we study an analogue of this problem for meromorphic functions and algebraic functions.     

On the homotopy type of CW-complexes with aspherical fundamental group

This paper is concerned with the homotopy type distinction of finite CW-complexes. A (G,n)-complex is a finite n-dimensional CW-complex with fundamental-group G and vanishing higher homotopy-groups up to dimension n−1. In case G is an n-dimensional group there is a unique (up to homotopy) (G,n)-complex on the minimal Euler-characteristic level χmin(G,n). For every n we give examples of n-dimensional groups G for which there exist homotopically distinct (G,n)-complexes on the level χmin(G,n)+1. In the case where n=2 these examples are algebraic.     

Bounding the number of zeros of certain Abelian integrals

In this paper we prove a criterion that provides an easy sufficient condition in order for any nontrivial linear combination of n Abelian integrals to have at most n+k−1 zeros counted with multiplicities. This condition involves the functions in the integrand of the Abelian integrals and it can be checked, in many cases, in a purely algebraic way.     

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.     

Convex subsets of 2n and bounded truth-table reducibility

Let 2ⁿ be the set of n-tuples of 0's and 1's, partially ordered componentwise. A characterization is given of the possible decompositions of arbitrary subsets of 2ⁿ as disjoint unions of sets which are convex in this ordering; this result is used to obtain a decomposition theorem for Boolean functions in terms of monotone functions. The second half of the paper contains applications to recursion theory; in particular, canonical forms for certain minimum-norm bounded-truth-table reductions are obtained.     

Algebraic dichotomies with an application to the stability of Riemann solutions of conservation laws

Recently, there has been some interest on the stability of waves where the functions involved grow or decay at an algebraic rate m|x|. In this paper we define the so-called algebraic dichotomy that may aid in treating such problems. We discuss the basic properties of the algebraic dichotomy, methods of detecting it, and calculating the power of the weight function.We present several examples: (1) The Bessel equation. (2) The n-degree Fisher type equation. (3) Hyperbolic conservation laws in similarity coordinates. (4) A system of conservation laws with a Dafermos type viscous regularization. We show that the linearized system generates an analytic semigroup in the space of algebraic decay functions. This example motivates our work on algebraic dichotomies.     

A resultant system as the set of coefficients of a single resultant

Explicit expressions for polynomials forming a homogeneous resultant system of a set of m+1 homogeneous polynomial equations in n+1<m+1 variables are given. These polynomials are obtained as coefficients of a homogeneous resultant for an appropriate system of n+1 equations in n+1 variables, which is explicitly constructed from the initial system. Similar results are obtained for mixed resultant systems of sets of n + 1 sections of line bundles on a projective variety of dimension n < m. As an application, an algorithm determining whether one of the orbits under an action of an affine irreducible algebraic group on a quasi-affine variety is contained in the closure of another orbit is described.