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.     

An example on strong shift equivalence of positive integral matrices

The following matrices are considered $$A_k = \left( {\begin{array}{*{20}c} k \\ 1 \\ \end{array} \begin{array}{*{20}c} 2 \\ k \\ \end{array} } \right), B_k \left( {\begin{array}{*{20}c} {k - 1} \\ 1 \\ \end{array} \begin{array}{*{20}c} 1 \\ {k + 1} \\ \end{array} } \right),k \in \mathbb{N},$$ which are strong shift equivalent in the sense ofWilliams [7]. In case \(k + \sqrt 2 \) is a prime number of the algebraic field \(\mathbb{Q}(\sqrt 2 )\) matrices are defined which determine the possible choices of rank two matrices connectingA _k andB _k in the sense of strong shift equivalence. A complete list of all these matrices is given.     

The number of strictly increasing mappings of fences

Let X and Y be fences of size n and m, respectively and n, m be either both even or both odd integers (i.e., |m-n| is an even integer). Let \(r = \left\lfloor {{{(n - 1)} \mathord{\left/ {\vphantom {{(n - 1)} 2}} \right. \kern-0em} 2}} \right\rfloor\) . If 1<n<-m then there are \(a_{n,m} = (m + 1)2^{n - 2} - 2(n - 1)(\begin{array}{*{20}c} {n - 2} \\ r \\ \end{array} )\) of strictly increasing mappings of X to Y. If 1<-m<-n<-2m and s=1/2(n?m) then there are a _n,m+b _n,m+c _n of such mappings, where $$\begin{gathered} b_{n,m} = 8\sum\limits_{i = 0}^{s - 2} {\left( {\begin{array}{*{20}c} {m + 2i + 1} \\ l \\ \end{array} } \right)4^{s - 2 - 1} } \hfill \\ {\text{ }}c_n = \left\{ \begin{gathered} \left( {\begin{array}{*{20}c} {n - 1} \\ {s - 1} \\ \end{array} } \right){\text{ if both }}n,m{\text{ are even;}} \hfill \\ {\text{ 0 if both }}n,m{\text{ are odd}}{\text{.}} \hfill \\ \end{gathered} \right. \hfill \\ \end{gathered} $$      

On the representation theory of Möbius groups inR n*

We will solve several fundamental problems of Möbius groupsM(R ⁿ) which have been matters of interest such as the conjugate classification, the establishment of a standard form without finding the fixed points and a simple discrimination method. Let \(g = \left[ {\begin{array}{*{20}c} a &; b \\ c &; d \\ \end{array} } \right]\) be a Clifford matrix of dimensionn, c ≠ 0. We give a complete conjugate classification and prove the following necessary and sufficient conditions:g is f.p.f. (fixed points free) iff \(g \sim \left[ {\begin{array}{*{20}c} \alpha &; 0 \\ c &; {\alpha '} \\ \end{array} } \right]\) , |α|<1 and |E?AE ¹| ≠ 0;g is elliptic iff \(g \sim \left[ {\begin{array}{*{20}c} \alpha &; \beta \\ c &; {\alpha '} \\ \end{array} } \right]\) , |α| <1 and |E?AE ¹|=0;g is parabolic iff \(g \sim \left[ {\begin{array}{*{20}c} \alpha &; 0 \\ c &; {\alpha '} \\ \end{array} } \right]\) , |α|=1; andg is loxodromic iff \(g \sim \left[ {\begin{array}{*{20}c} \alpha &; \beta \\ c &; {\alpha '} \\ \end{array} } \right]\) , |α| >1 or rank (E?AE ¹) ≠ rank (E?AE ¹,ac ^?1+c ^?1 d), where α is represented by the solutions of certain linear algebraic equations and satisfies $\left| {c^{ - 1} \alpha '} \right| = \left| {\left( {E - AE^1 } \right)^{ - 1} \left( {\alpha c^{ - 1} + c^{ - 1} \alpha '} \right)} \right|.$      

Maximizing a correlational ratio for linear extensions of posets

Let ρ=P(12)/P(12|13), where P(ij) is the probability that i precedes j in a randomly chosen linear extension of a partially ordered set ({1,2,...,n}, ≤) in which points 1, 2 and 3 are mutually incomparable. A previous paper by the author (Order 1, 127 (1984)) proved that ρ≤1. The present paper considers the maximization of ρ for each n≥3. It shows that, with \(\alpha _n = \left\lfloor {(n + 3)/2} \right\rfloor \) , the maximum ρ is at least $$\left[ {\alpha _n \left( {\begin{array}{*{20}c} n \\ {\alpha _n } \\ \end{array} } \right) - n} \right]/\left[ {\alpha _n \left( {\begin{array}{*{20}c} n \\ {\alpha _n } \\ \end{array} } \right) - \alpha _n } \right]$$ . Evidence that this value cannot be exceeded is given. It is also proved that the smallest possible value of P(231)+P(321) is $$1/\left( {\begin{array}{*{20}c} n \\ {\left\lfloor {\left( {n + 1} \right)/2} \right\rfloor } \\ \end{array} } \right)$$ .     

An explicit formula for |FM(1+1+n)|

We show that the number of elements in FM(1+1+n), the modular lattice freely generated by two single elements and an n-element chain, is 1 $$\frac{1}{{6\sqrt 2 }}\sum\limits_{k = 0}^{n + 1} {\left[ {2\left( {\begin{array}{*{20}c} {2k} \\ k \\ \end{array} } \right) - \left( {\begin{array}{*{20}c} {2k} \\ {k - 2} \\ \end{array} } \right)} \right]} \left( {\lambda _1^{n - k + 2} - \lambda _2^{n - k + 2} } \right) - 2$$ , where \(\lambda _{1,2} = {{\left( {4 \pm 3\sqrt 2 } \right)} \mathord{\left/ {\vphantom {{\left( {4 \pm 3\sqrt 2 } \right)} 2}} \right. \kern-0em} 2}\) .     

Matrix semigroups—generators and relations

Some presentations for the semigroups of all 2×2 matrices and all 2×2 matrices of determinant 0 or 1 over the field GF(p) (p prime) are given. In particular, if <a, b, c‖ R> is any (semigroup) presentation for the general linear group in terms of generators $$A = \left( {\begin{array}{*{20}c} 1 & 0 \\ 1 & 1 \\ \end{array} } \right),B = \left( {\begin{array}{*{20}c} 1 & 1 \\ 0 & 1 \\ \end{array} } \right),C = \left( {\begin{array}{*{20}c} 1 & 0 \\ 0 & \xi \\ \end{array} } \right),$$ where ζ is a primitive root of 1 modulop, then the presentation $$\langle a,b,c,t|R,t^2 = ct = tc = t,tba^{p - 1} t = 0,b^{\xi - 1} atb = a^{\xi - 1} tb^\xi a^{1 - \xi - 1} \rangle $$ defines the semigroup of all 2×2 matrices over GF (2,p) in terms of generatorsA, B, C and $$T = \left( {\begin{array}{*{20}c} 1 & 0 \\ 0 & 0 \\ \end{array} } \right).$$ Generating sets and ranks of various matrix semigroups are also found.     

Eigenvalues of the Dirac operator in the continuous spectrum

Functionsp(x) andq(x) for which the Dirac operator $$Dy = \left( {\begin{array}{*{20}c} {\begin{array}{*{20}c} 0 \\ { - 1} \\ \end{array} } & {\begin{array}{*{20}c} 1 \\ 0 \\ \end{array} } \\ \end{array} } \right)\frac{{dy}}{{dx}} + \left( {\begin{array}{*{20}c} {p(x) q(x)} \\ {q(x) - p(x)} \\ \end{array} } \right)y = \lambda y, y = \left( {\begin{array}{*{20}c} {y_1 } \\ {y_2 } \\ \end{array} } \right), y_1 (0) = 0,$$ has a countable number of eigenvalues in the continuous spectrum are constructed.     

On the normalizing multiplier of the generalized Jackson kernel

We consider the question of evaluating the normalizing multiplier $$\gamma _{n,k} = \frac{1}{\pi }\int_{ - \pi }^\pi {\left( {\frac{{sin\tfrac{{nt}}{2}}}{{sin\tfrac{t}{2}}}} \right)^{2k} dt} $$ for the generalized Jackson kernel J _n,k (t). We obtain the explicit formula $$\gamma _{n,k} = 2\sum\limits_{p = 0}^{\left[ {k - \tfrac{k}{n}} \right]} {( - 1)\left( {\begin{array}{*{20}c} {2k} \\ p \\ \end{array} } \right)\left( {\begin{array}{*{20}c} {k(n + 1) - np - 1} \\ {k(n - 1) - np} \\ \end{array} } \right)} $$ and the representation $$\gamma _{n,k} = \sqrt {\frac{{24}}{\pi }} \cdot \frac{{(n - 1)^{2k - 1} }}{{\sqrt {2k - 1} }}\left[ {1\frac{1}{8} \cdot \frac{1}{{2k - 1}} + \omega (n,k)} \right],$$ , where $$\left| {\omega (n,k)} \right| < \frac{4}{{(2k - 1)\sqrt {ln(2k - 1)} }} + \sqrt {12\pi } \cdot \frac{{k^{\tfrac{3}{2}} }}{{n - 1}}\left( {1 + \frac{1}{{n - 1}}} \right)^{2k - 2} .$$ .     

On cyclic compositions of positive integers

Say that two compositions of n into k parts are related if they differ only by a cyclic shift. This defines an equivalence relation on the set of such compositions. Let ${\left\langle \begin{array}{c}n \\ k\end{array} \right\rangle}$ denote the number of distinct corresponding equivalence classes, that is, the number of cyclic compositions of n into k parts. We show that the sequence ${\left\langle\begin{array}{c}n \\ k\end{array}\right\rangle}$ is log-concave and prove some results concerning ${\left\langle \begin{array}{c}n \\ k \end{array} \right\rangle}$ modulo two.     

On Ramsey—Turán type theorems for hypergraphs

LetH ^r be anr-uniform hypergraph. Letg=g(n;H ^r ) be the minimal integer so that anyr-uniform hypergraph onn vertices and more thang edges contains a subgraph isomorphic toH ^r . Lete =f(n;H ^r ,εn) denote the minimal integer such that everyr-uniform hypergraph onn vertices with more thane edges and with no independent set ofεn vertices contains a subgraph isomorphic toH ^r . We show that ifr>2 andH ^r is e.g. a complete graph then $$\mathop {\lim }\limits_{\varepsilon \to 0} \mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} f(n;H^r ,\varepsilon n) = \mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} g(n;H^r )$$ while for someH ^r with \(\mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} g(n;H^r ) \ne 0\) $$\mathop {\lim }\limits_{\varepsilon \to 0} \mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} f(n;H^r ,\varepsilon n) = 0$$ . This is in strong contrast with the situation in caser=2. Some other theorems and many unsolved problems are stated.     

Metric theorems related to the Kronecker-Weyl theorem modm

Let (Ω, ?,P) be the infinite product of identical copies of the unit interval probability space. For a Lebesgue measurable subsetI of the unit interval, let \(A(N,I,\omega ) = \# \left\{ {n \leqslant N|\omega _n \varepsilon I} \right\}\) , where ω=(ω₁,ω₂,...). For integersm>1, and 0≤r<m, define $$\varepsilon (k,r,m,I,\omega ) = \left\{ {\begin{array}{*{20}c} {1\,if\,A(k,I,\omega ) \equiv r(\bmod m)} \\ {0\,otherwise} \\ \end{array} } \right.$$ and $$\eta (k,m,I,\omega ) = \left\{ {\begin{array}{*{20}c} {1\,if\,(A(k,I,\omega ),m) \equiv 1} \\ {0\,otherwise.} \\ \end{array} } \right.$$ A theorem ofK. L. Chung yields an iterated logarithm law and a central limit theorem for sums of the variables ε(k) and η(k).     

On a second-order matrix differential operator

We consider the second-order matrix differential operator $$N = \left( {\begin{array}{*{20}c} { - \frac{d}{{dx}}\left( {p_0 \frac{d}{{dx}}} \right) + p_1 } \\ r \\ \end{array} \begin{array}{*{20}c} r \\ { - \frac{d}{{dx}}\left( {q_0 \frac{d}{{dx}}} \right) + q_1 } \\ \end{array} } \right)$$ determined by the expression Nφ, [0 ?x < ∞), where \(\phi = \left( {\begin{array}{*{20}c} U \\ V \\ \end{array} } \right)\) . It has been proved that if p₀, q₀, p₁, q₁,r satisfy certain conditions, then N is in the limit point case at ∞. It has been also shown that certain differential operators in the Hilbert space L² of vectors, generated by the operator N, are symmetric and self-adjoint.     

A decomposition of the universal embedding space for the near polygon {{\mathbb H}_n}

Let ${{\mathbb H}_n, n \geq 1}$ , be the near 2n-gon defined on the 1-factors of the complete graph on 2n?+?2 vertices, and let e denote the absolutely universal embedding of ${{\mathbb H}_n}$ into PG(W), where W is a ${\frac{1}{n+2} \left(\begin{array}{c}2n+2 \\ n+1\end{array}\right)}$ -dimensional vector space over the field ${{\mathbb F}_2}$ with two elements. For every point z of ${{\mathbb H}_n}$ and every ${i \in {\mathbb N}}$ , let Δ _i (z) denote the set of points of ${{\mathbb H}_n}$ at distance i from z. We show that for every pair {x, y} of mutually opposite points of ${{\mathbb H}_n, W}$ can be written as a direct sum ${W_0 \oplus W_1 \oplus \cdots \oplus W_n}$ such that the following four properties hold for every ${i \in \{0,\ldots,n \}}$ : (1) ${\langle e(\Delta_i(x) \cap \Delta_{n-i}(y)) \rangle = {\rm PG}(W_i)}$ ; (2) ${\left\langle e \left( \bigcup_{j \leq i} \Delta_j(x) \right) \right\rangle = {\rm PG}(W_0 \oplus W_1 \oplus \cdots \oplus W_i)}$ ; (3) ${\left\langle e \left( \bigcup_{j \leq i} \Delta_j(y) \right) \right\rangle = {\rm PG}(W_{n-i}\oplus W_{n-i+1} \oplus \cdots \oplus W_n)}$ ; (4) ${\dim(W_i) = |\Delta_i(x) \cap \Delta_{n-i}(y)| = \left(\begin{array}{c}n \\ i\end{array}\right)^2 - \left(\begin{array}{c}n \\ i-1\end{array}\right) \cdot \left(\begin{array}{c}n \\ i+1\end{array}\right)}$ .     

A note on the mean value of L-series

Using Hilbert’s inequality, we give a new asymptotic formula (uniform inq andT) for $$\mathop \Sigma \limits_{\begin{array}{*{20}c} {\chi (mod q)} \hfill \\ {\chi primitive} \hfill \\ \end{array} } \smallint _T^{2T} |L(\tfrac{1}{2} + it,\chi )^4 |dt$$      

Enumerating rooted simple planar maps

The main purpose of this paper is to find the number of combinatorially distinct rooted simpleplanar maps,i.e.,maps having no loops and no multi-edges,with the edge number given.We haveobtained the following results.1.The number of rooted boundary loopless planar [m,2]-maps.i.e.,maps in which there areno loops on the boundaries of the outer faces,and the edge number is m,the number of edges on theouter face boundaries is 2,is(?)for m≥1.G_0~N=0.2.The number of rooted loopless planar [m,2]-maps is(?)3.The number of rooted simple planar maps with m edges H_m~s satisfies the following recursiveformula:(?)where H_m~(NL) is the number of rooted loopless planar maps with m edges given in [2].4.In addition,γ(i,m),i≥1,are determined by(?)for m≥i.γ(i,j)=0,when i>j.     

Probability thatn random points are in convex position

We show thatn random points chosen independently and uniformly from a parallelogram are in convex position with probability $$\left( {\frac{{\left( {\begin{array}{*{20}c} {2n - 2} \\ {n - 1} \\ \end{array} } \right)}}{{n!}}} \right)^2 $$ . A finite set of points in the plane is calledconvex if its points are vertices of a convex polygon. In this paper we show the following results:     

Irrational Factor of Order k and ITS Connections With k-Free Integers

We introduce an irrational factor of order k defined by \({I_{k}(n) ={\prod_{i=1}^{l}} p_{i}^{\beta_{i}}}\) , where \({n = \prod_{i=1}^{l} p_{i}^{\alpha_{i}}}\) is the factorization of n and \({\beta_{i} = \left\{\begin{array}{ll}\alpha_i, \quad \quad {\rm if} \quad \alpha_i < k \\ \frac{1}{\alpha_i},\quad \quad {\rm if} \quad \alpha_i \geqq k \end{array}\right.}\) . It turns out that the function \({\frac{I_{k} (n)}{n}}\) well approximates the characteristic function of k-free integers. We also derive asymptotic formulas for \({\prod_{v=1}^{n} I_{k}(v)^{\frac{1}{n}}, \sum_{n \leqq x} I_{k}(n)}\) and \({\sum_{n \leqq x} (1 - \frac{n}{x}) I_{k}(n)}\) .     

On the numerical evaluation of a sum involving binomial coefficients

An efficient way to evaluate \(\sum\limits_{j = k}^n {( - 1)^{j - k - 1} \left( {\begin{array}{*{20}c} n \\ j \\ \end{array} } \right)\left( {\begin{array}{*{20}c} {j - 1} \\ {k - 1} \\ \end{array} } \right)} \ln j\) is described. This sum, connected with the logarithmic Weibull distribution, is hard to evaluate directly, because the binomial coefficients become quite large, and then the alternating signs cause severe loss of significant figures. By converting the sum to an integral, we avoid this difficulty.     

Über verallgemeinerte Momente additiver Funktionen

In this paper we give characterizations of additive functionsf, for which $$\mathop {\lim \sup }\limits_{x \to \infty } x^{ - 1} \sum\limits_{n \leqslant x} {\varphi (|f(n)|)}$$ is bounded, where φ: ?⁺ → ?⁺ is monotone and or $$\begin{array}{*{20}c} {\varphi (x) = c^x } & {(x \in \mathbb{R}).} \\ \end{array}$$ A typical example is φ (x)=x ^a (a>0) forx≥0.