Generation of full cycles by a composition of NLFSRs

Non-linear feedback shift registers (NLFSRs) are a generalization of linear feedback shift registers in which a current state is a non-linear function of the previous state. The interest in NLFSRs is motivated by their ability to generate pseudo-random sequences which are typically hard to break with existing cryptanalytic methods. However, it is still not known how to construct large \(n\) -stage NLFSRs which generate full cycles of \(2^n\) possible states. This paper presents a method for generating full cycles by a composition of NLFSRs. First, we show that an \(n*k\) -stage register with period \(O(2^{2n})\) can be constructed from \(k\) NLFSRs with \(n\) -stages by adding to their feedback functions a logic block of size \(O(nk)\) , for \(k > 1\) . This logic block implements Boolean functions representing pairs of states whose successors have to be exchanged in order to join cycles. Then, we show how to join all cycles into one by using one more logic block of size \(O(nk)\) .     

On an extension of the Frobenius^{\prime } theorem about p-nilpotency of a finite group

Suppose that \(G\) is a finite group and \(H\) is a subgroup of \(G\) . \(H\) is said to be \(s\) -quasinormally embedded in \(G\) if for each prime \(p\) dividing the order of \(H\) , a Sylow \(p\) -subgroup of \(H\) is also a Sylow \(p\) -subgroup of some \(s\) -quasinormal subgroup of \(G\) . We fix in every non-cyclic Sylow subgroup \(P\) of \(G\) some subgroup \(D\) satisfying \(1<|D|<|P|\) and study the \(p\) -nilpotency of \(G\) under the assumption that every subgroup \(H\) of \(P\) with \(|H|=|D|\) is \(s\) -quasinormally embedded in \(G\) . Some recent results and the Frobenius \(^{\prime }\) theorem are generalized.     

On weakly closed subgroups of finite groups

Suppose that \(G\) is a finite group and \(H\) , \(K\) are subgroups of \(G\) . We say that \(H\) is weakly closed in \(K\) with respect to \(G\) if, for any \(g \in G\) such that \(H^{g}\le K\) , we have \(H^{g}=H\) . In particular, when \(H\) is a subgroup of prime-power order and \(K\) is a Sylow subgroup containing it, \(H\) is simply said to be a weakly closed subgroup of \(G\) or weakly closed in \(G\) . In the paper, we investigate the structure of finite groups by means of weakly closed subgroups.     

Scattered linear sets generated by collineations between pencils of lines

Let \(A\) and \(B\) be two points of \(\mathrm{{PG}}(2,q^n)\) , and let \(\Phi \) be a collineation between the pencils of lines with vertices \(A\) and \(B\) . In this paper, we prove that the set of points of intersection of corresponding lines under \(\Phi \) is either the union of a scattered \(\mathrm{{GF}}(q)\) -linear set of rank \(n+1\) with the line \(AB\) or the union of \(q-1\) scattered \(\mathrm{{GF}}(q)\) -linear sets of rank \(n\) with \(A\) and \(B\) . We also determine the intersection configurations of two scattered \(\mathrm{{GF}}(q)\) -linear sets of rank \(n+1\) of \(\mathrm{{PG}}(2,q^n)\) both meeting the line \(AB\) in a \(\mathrm{{GF}}(q)\) -linear set of pseudoregulus type with transversal points \(A\) and \(B\) .     

Characterization of ellipses as uniformly dense sets with respect to a family of convex bodies

Let \(K\subset \mathbb R ^N\) be a convex body containing the origin. A measurable set \(G\subset \mathbb R ^N\) with positive Lebesgue measure is said to be uniformly \(K\) -dense if, for any fixed \(r>0\) , the measure of \(G\cap (x+r K)\) is constant when \(x\) varies on the boundary of \(G\) (here, \(x+r K\) denotes a translation of a dilation of \(K\) ). We first prove that \(G\) must always be strictly convex and at least \(C^{1,1}\) -regular; also, if \(K\) is centrally symmetric, \(K\) must be strictly convex, \(C^{1,1}\) -regular and such that \(K=G-G\) up to homotheties; this implies in turn that \(G\) must be \(C^{2,1}\) -regular. Then for \(N=2\) , we prove that \(G\) is uniformly \(K\) -dense if and only if \(K\) and \(G\) are homothetic to the same ellipse. This result was already proven by Amar et al. in 2008 . However, our proof removes their regularity assumptions on \(K\) and \(G\) , and more importantly, it is susceptible to be generalized to higher dimension since, by the use of Minkowski’s inequality and an affine inequality, avoids the delicate computations of the higher-order terms in the Taylor expansion near \(r=0\) for the measure of \(G\cap (x+r\,K)\) (needed in 2008).     

The k-error linear complexity distribution for 2^n-periodic binary sequences

The linear complexity and the \(k\) -error linear complexity of a sequence have been used as important security measures for key stream sequence strength in linear feedback shift register design. By using the sieve method of combinatorics, we investigate the \(k\) -error linear complexity distribution of \(2^n\) -periodic binary sequences in this paper based on Games–Chan algorithm. First, for \(k=2,3\) , the complete counting functions for the \(k\) -error linear complexity of \(2^n\) -periodic binary sequences (with linear complexity less than \(2^n\) ) are characterized. Second, for \(k=3,4\) , the complete counting functions for the \(k\) -error linear complexity of \(2^n\) -periodic binary sequences with linear complexity \(2^n\) are presented. Third, as a consequence of these results, the counting functions for the number of \(2^n\) -periodic binary sequences with the \(k\) -error linear complexity for \(k = 2\) and \(3\) are obtained.     

On the commuting probability and supersolvability of finite groups

For a finite group \(G\) , let \(d(G)\) denote the probability that a randomly chosen pair of elements of \(G\) commute. We prove that if \(d(G)>1/s\) for some integer \(s>1\) and \(G\) splits over an abelian normal nontrivial subgroup \(N\) , then \(G\) has a nontrivial conjugacy class inside \(N\) of size at most \(s-1\) . We also extend two results of Barry, MacHale, and Ní Shé on the commuting probability in connection with supersolvability of finite groups. In particular, we prove that if \(d(G)>5/16\) then either \(G\) is supersolvable, or \(G\) isoclinic to \(A_4\) , or \(G/\mathbf{Z}(G)\) is isoclinic to \(A_4\) .     

Endomorphism rings of bimodules

Let \(M\) be an \(R\) - \(R\) -bimodule over a semi-prime right and left Goldie ring \(R\) . We investigate how non-singularity conditions on \(M_R\) are related to such conditions on \(_RM\) . In particular, we say an \(R\) - \(R\) -bimodule \(M\) such that \(_RM\) and \(M_R\) are non-singular has the right essentiality property if \(IM_R\) is essential in \(M_R\) for all essential right ideals \(I\) of \(R\) , and investigate several questions related to this property.     

On extensions of completely simple semigroups by groups

An example of an extension of a completely simple semigroup \(U\) by a group \(H\) is given which cannot be embedded into the wreath product of \(U\) by \(H\) . On the other hand, every central extension of \(U\) by \(H\) is shown to be embeddable in the wreath product of \(U\) by \(H\) , and any extension of \(U\) by \(H\) is proved to be embeddable in a semidirect product of a completely simple semigroup \(V\) by \(H\) where the maximal subgroups of \(V\) are direct powers of those of \(U\) .     

Approximation faible et principe de Hasse pour des espaces homogènes à stabilisateur fini résoluble

Let \(K\) be a global field and \(G\) a finite solvable \(K\) -group. Under certain hypotheses concerning the extension splitting \(G\) , we show that the homogeneous space \(V=G'/G\) with \(G'\) a semi-simple simply connected \(K\) -group has the weak approximation property. We use a more precise version of this result to prove the Hasse principle for homogeneous spaces \(X\) under a semi-simple simply connected \(K\) -group \(G'\) with finite solvable geometric stabilizer \({\bar{G}}\) , under certain hypotheses concerning the \(K\) -kernel (or \(K\) -lien) \(({\bar{G}},\kappa )\) defined by \(X\) .     

Some totally geodesic submanifolds of the nonlinear Grassmannian of a compact symmetric space

Let \(M\) and \(N\) be two connected smooth manifolds, where \(M\) is compact and oriented and \(N\) is Riemannian. Let \(\mathcal {E}\) be the Fréchet manifold of all embeddings of \(M\) in \(N\) , endowed with the canonical weak Riemannian metric. Let \(\sim \) be the equivalence relation on \(\mathcal {E}\) defined by \(f\sim g\) if and only if \(f=g\circ \phi \) for some orientation preserving diffeomorphism \(\phi \) of \(M\) . The Fréchet manifold \(\mathcal {S}= \mathcal {E}/_{\sim }\) of equivalence classes, which may be thought of as the set of submanifolds of \(N\) diffeomorphic to \(M\) and is called the nonlinear Grassmannian (or Chow manifold) of \(N\) of type \(M\) , inherits from \( \mathcal {E}\) a weak Riemannian structure. We consider the following particular case: \(N\) is a compact irreducible symmetric space and \(M\) is a reflective submanifold of \(N\) (that is, a connected component of the set of fixed points of an involutive isometry of \( N\) ). Let \(\mathcal {C}\) be the set of submanifolds of \(N\) which are congruent to \(M\) . We prove that the natural inclusion of \(\mathcal {C}\) in \(\mathcal {S}\) is totally geodesic.     

Neighbour-transitive codes in Johnson graphs

The Johnson graph \(J(v,k)\) has, as vertices, the \(k\) -subsets of a \(v\) -set \(\mathcal {V}\) and as edges the pairs of \(k\) -subsets with intersection of size \(k-1\) . We introduce the notion of a neighbour-transitive code in \(J(v,k)\) . This is a proper vertex subset \(\Gamma \) such that the subgroup \(G\) of graph automorphisms leaving \(\Gamma \) invariant is transitive on both the set \(\Gamma \) of ‘codewords’ and also the set of ‘neighbours’ of \(\Gamma \) , which are the non-codewords joined by an edge to some codeword. We classify all examples where the group \(G\) is a subgroup of the symmetric group \(\mathrm{Sym}\,(\mathcal {V})\) and is intransitive or imprimitive on the underlying \(v\) -set \(\mathcal {V}\) . In the remaining case where \(G\le \mathrm{Sym}\,(\mathcal {V})\) and \(G\) is primitive on \(\mathcal {V}\) , we prove that, provided distinct codewords are at distance at least \(3\) , then \(G\) is \(2\) -transitive on \(\mathcal {V}\) . We examine many of the infinite families of finite \(2\) -transitive permutation groups and construct surprisingly rich families of examples of neighbour-transitive codes. A major unresolved case remains.     

Bounding the exponent of a verbal subgroup

We deal with the following conjecture. If \(w\) is a group word and \(G\) is a finite group in which any nilpotent subgroup generated by \(w\) -values has exponent dividing \(e\) , then the exponent of the verbal subgroup \(w(G)\) is bounded in terms of \(e\) and \(w\) only. We show that this is true in the case where \(w\) is either the \(n\text{ th }\) Engel word or the word \([x^n,y_1,y_2,\ldots ,y_k]\) (Theorem A). Further, we show that for any positive integer \(e\) there exists a number \(k=k(e)\) such that if \(w\) is a word and \(G\) is a finite group in which any nilpotent subgroup generated by products of \(k\) values of the word \(w\) has exponent dividing \(e\) , then the exponent of the verbal subgroup \(w(G)\) is bounded in terms of \(e\) and \(w\) only (Theorem B).     

Fully inert subgroups of free Abelian groups

A subgroup \(H\) of an Abelian group \(G\) is called fully inert if \((\phi H + H)/H\) is finite for every \(\phi \in \mathrm{End}(G)\) . Fully inert subgroups of free Abelian groups are characterized. It is proved that \(H\) is fully inert in the free group \(G\) if and only if it is commensurable with \(n G\) for some \(n \ge 0\) , that is, \((H + nG)/H\) and \((H + nG)/nG\) are both finite. From this fact we derive a more structural characterization of fully inert subgroups \(H\) of free groups \(G\) , in terms of the Ulm–Kaplansky invariants of \(G/H\) and the Hill–Megibben invariants of the exact sequence \(0 \rightarrow H \rightarrow G \rightarrow G/H \rightarrow 0\) .     

The Ubiquity of the Orders of Fractional Semifields of Even Characteristic

To each non-square integer \(2^{2N+1}\ge 2^5\) there correspond semifields \(D\) of order of \(2^{2N+1}\) that contain \(\text{ GF}(4)\) . Hence there exist affine planes for each non-square order \(2^{2N+1}\ge 2^{5}\) that contain subaffine planes of order \(2^2\) . Moreover, there also exists semifields \(D_1\) and \(D_2\) , with \(|D_1|= |D_2| =|D|\) such that \(D_1\) is commutative and \(D_2\) is non-commutative but neither \(D_1\) nor \(D_2\) contains \(\text{ GF}(4)\) .     

A sufficient condition for zero entropy

We prove that a diffeomorphism \(f\) defined on a compact manifold has zero topological entropy if there are \(d\in {\mathbb {N}}\) and \(K>0\) such that \(\Vert Dg^{n_x}(x)\Vert \le Kn^d_x\) for every diffeomorphism \(g\) that is \(C^1\) close to \(f\) and every periodic point \(x\) of least period \(n_x\) of \(g\) .     

Independence Under the G-Expectation Framework

We show that, for two non-trivial random variables \(X\) and \(Y\) under a sublinear expectation space, if \(X\) is independent from \(Y\) and \(Y\) is independent from \(X\) , then \(X\) and \(Y\) must be maximally distributed.     

Low Complexity Methods For Discretizing Manifolds Via Riesz Energy Minimization

Let \(A\) be a compact \(d\) -rectifiable set embedded in Euclidean space \({\mathbb R}^p, d\le p\) . For a given continuous distribution \(\sigma (x)\) with respect to a \(d\) -dimensional Hausdorff measure on \(A\) , our earlier results provided a method for generating \(N\) -point configurations on \(A\) that have an asymptotic distribution \(\sigma (x)\) as \(N\rightarrow \infty \) ; moreover, such configurations are “quasi-uniform” in the sense that the ratio of the covering radius to the separation distance is bounded independently of \(N\) . The method is based upon minimizing the energy of \(N\) particles constrained to \(A\) interacting via a weighted power-law potential \(w(x,y)|x-y|^{-s}\) , where \(s>d\) is a fixed parameter and \(w(x,y)=\left( \sigma (x)\sigma (y)\right) ^{-({s}/{2d})}\) . Here we show that one can generate points on \(A\) with the aforementioned properties keeping in the energy sums only those pairs of points that are located at a distance of at most \(r_N=C_N N^{-1/d}\) from each other, with \(C_N\) being a positive sequence tending to infinity arbitrarily slowly. To do this, we minimize the energy with respect to a varying truncated weight \(v_N(x,y)=\Phi (|x-y|/r_N)\cdot w(x,y)\) , where \(\Phi :(0,\infty )\rightarrow [0,\infty )\) is a bounded function with \(\Phi (t)=0, t\ge 1\) , and \(\lim _{t\rightarrow 0^+}\Phi (t)=1\) . Under appropriate assumptions, this reduces the complexity of generating \(N\) -point “low energy” discretizations to order \(N C_N^d\) computations.     

Mean Squared Error Minimization for Inverse Moment Problems

We consider the problem of approximating the unknown density \(u\in L^2(\Omega ,\lambda )\) of a measure \(\mu \) on \(\Omega \subset \mathbb {R}^n\) , absolutely continuous with respect to some given reference measure \(\lambda \) , only from the knowledge of finitely many moments of \(\mu \) . Given \(d\in \mathbb {N}\) and moments of order \(d\) , we provide a polynomial \(p_d\) which minimizes the mean square error \(\int (u-p)^2d\lambda \) over all polynomials \(p\) of degree at most \(d\) . If there is no additional requirement, \(p_d\) is obtained as solution of a linear system. In addition, if \(p_d\) is expressed in the basis of polynomials that are orthonormal with respect to \(\lambda \) , its vector of coefficients is just the vector of given moments and no computation is needed. Moreover \(p_d\rightarrow u\) in \(L^2(\Omega ,\lambda )\) as \(d\rightarrow \infty \) . In general nonnegativity of \(p_d\) is not guaranteed even though \(u\) is nonnegative. However, with this additional nonnegativity requirement one obtains analogous results but computing \(p_d\ge 0\) that minimizes \(\int (u-p)^2d\lambda \) now requires solving an appropriate semidefinite program. We have tested the approach on some applications arising from the reconstruction of geometrical objects and the approximation of solutions of nonlinear differential equations. In all cases our results are significantly better than those obtained with the maximum entropy technique for estimating \(u\) .     

Optimal mass transport and symmetric representations of their cost functions

We consider Monge–Kantorovich problems corresponding to general cost functions \(c(x,y)\) but with symmetry constraints on a Polish space \(X\times X\) . Such couplings naturally generate anti-symmetric Hamiltonians on \(X\times X\) that are \(c\) -convex with respect to one of the variables. In particular, if \(c\) is differentiable with respect to the first variable on an open subset \(X\) in \( \mathbb {R}^d\) , we show that for every probability measure \(\mu \) on \(X\) , there exists a symmetric probability measure \(\pi _0\) on \(X\times X\) with marginals \(\mu \) , and an anti-symmetric Hamiltonian \(H\) such that \(\nabla _2H(y, x)=\nabla _1c(x,y)\) for \( \pi _0\) -almost all \((x,y) \in X \times X.\) If \(\pi _0\) is supported on a graph \((x, Sx)\) , then \(S\) is necessarily a \(\mu \) -measure preserving involution (i.e., \(S^2=I\) ) and \(\nabla _2H(x, Sx)=\nabla _1c(Sx,x)\) for \(\mu \) -almost all \(x \in X.\) For monotone cost functions such as those given by \(c(x,y)=\langle x, u(y)\rangle \) or \(c(x,y)=-|x-u(y)|^2\) where \(u\) is a monotone operator, \(S\) is necessarily the identity yielding a classical result by Krause, namely that \(u(x)=\nabla _2H(x, x)\) where \(H\) is anti-symmetric and concave-convex.