The linear complexity of a class of binary sequences with optimal autocorrelation

Binary sequences with optimal autocorrelation and large linear complexity have important applications in cryptography and communications. Very recently, a class of binary sequences of period 4p with optimal autocorrelation was proposed by interleaving four suitable Ding–Helleseth–Lam sequences (Des. Codes Cryptogr.,  https://doi.org/10.1007/s10623-017-0398-5), where p is an odd prime with \(p \equiv 1(\bmod 4)\). The objective of this paper is to determine the minimal polynomial and the linear complexity of this class of binary optimal sequences via a sequence polynomial approach. It turns out that this class of sequences has quite good linear complexity.     

Variations on average character degrees and p-nilpotence

We prove that if p is an odd prime, G is a solvable group, and the average value of the irreducible characters of G whose degrees are not divisible by p is strictly less than 2(p + 1)/(p + 3), then G is p-nilpotent. We show that there are examples that are not p-nilpotent where this bound is met for every prime p. We then prove a number of variations of this result.     

A characterizing property of CP-groups

Let G be a finite group. It is proved that if, for every prime p, the number of nonidentity p-elements of G is divisible by the p′-part of |G|, then all element orders of G are prime powers.     

Parametric AE-solution sets to the parametric linear systems with multiple right-hand sides and parametric matrix equation A(p)X = B(p)

In this paper, the parametric matrix equation A(p)X = B(p) whose elements are linear functions of uncertain parameters varying within intervals are considered. In this matrix equation A(p) and B(p) are known m-by-m and m-by-n matrices respectively, and X is the m-by-n unknown matrix. We discuss the so-called AE-solution sets for such systems and give some analytical characterizations for the AE-solution sets and a sufficient condition under which these solution sets are bounded. We then propose a modification of Krawczyk operator for parametric systems which causes reduction of the computational complexity of obtaining an outer estimation for the parametric united solution set, considerably. Then we give a generalization of the Bauer-Skeel and the Hansen-Bliek-Rohn bounds for enclosing the parametric united solution set which also enables us to reduce the computational complexity, significantly. Also some numerical approaches based on Gaussian elimination and Gauss-Seidel methods to find outer estimations for the parametric united solution set are given. Finally, some numerical experiments are given to illustrate the performance of the proposed methods.     

A polynomial–exponential equation related to the Ramanujan–Nagell equation

For any given odd prime p and a fixed positive integer D prime to p, we study the equation \(x^2+D^m=p^n\) in positive integers x, m and n. We use a classical work of Dem’janenko in 1965 on a certain quadratic Diophantine equation together with some results concerning the existence of primitive divisors of Lucas sequences to examine our equation when D is a product of \(p-1\) and a square.     

Asymptotic analysis on the normalized <Emphasis Type="Italic">k</Emphasis>-error linear complexity of binary sequences

Linear complexity and k-error linear complexity are the important measures for sequences in stream ciphers. This paper discusses the asymptotic behavior of the normalized k-error linear complexity \({L_{n,k}(\underline{s})/n}\) of random binary sequences \({\underline{s}}\) , which is based on one of Niederreiter’s open problems. For k = n θ, where 0 ≤ θ ≤ 1/2 is a fixed ratio, the lower and upper bounds on accumulation points of \({L_{n,k}(\underline{s})/n}\) are derived, which holds with probability 1. On the other hand, for any fixed k it is shown that \({\lim_{n\rightarrow\infty} L_{n,k}(\underline{s})/n = 1/2}\) holds with probability 1. The asymptotic bounds on the expected value of normalized k-error linear complexity of binary sequences are also presented.     

A solvability criterion for finite groups

We show that if for every prime p, the normalizer of a Sylow p-subgroup of a finite group G admits a p-solvable supplement, then G is solvable. This generalizes a solvability criterion of Hall which asserts that a finite group G is solvable if and only if G has a Hall p′-subgroup for every prime p.     

New optimal binary sequences with period 4<Emphasis Type="Italic">p</Emphasis> via interleaving Ding–Helleseth–Lam sequences

Binary sequences play important roles in radar, communication, and cryptography. Finding new binary sequences with optimal autocorrelation value/magnitude has been an interesting research topic in sequence design. Ding–Helleseth–Lam sequences are such a class of binary sequences of period p, where p is an odd prime with \(p\equiv 1(\bmod ~4)\). The objective of this paper is to present a construction of binary sequences of period 4p via interleaving four suitable Ding–Helleseth–Lam sequences. This construction generates new binary sequences with optimal autocorrelation magnitude, which can not be produced by earlier ones.     

2-Recognizability by prime graph of <Emphasis Type="Italic">PSL</Emphasis>(2, <Emphasis Type="Italic">p</Emphasis><Superscript>2</Superscript>)

Let G be a finite group and let Γ(G) be the prime graph of G. Assume p prime. We determine the finite groups G such that Γ(G) = Γ(PSL(2, p ²)) and prove that if p ≠ 2, 3, 7 is a prime then k(Γ(PSL(2, p ²))) = 2. We infer that if G is a finite group satisfying |G| = |PSL(2, p ²)| and Γ(G) = Γ(PSL(2, p ²)) then G ? PSL(2, p ²). This enables us to give new proofs for some theorems; e.g., a conjecture of W. Shi and J. Bi. Some applications are also considered of this result to the problem of recognition of finite groups by element orders.     

Camina pairs that are not <Emphasis Type="Italic">p</Emphasis>-closed

We show for every prime p that there exists a Camina pair (G, N), where N is a p-group and G is not p-closed.     

On finite groups for which the lattice of <Emphasis Type="Italic">S</Emphasis>-permutable subgroups is distributive

Let p be a prime and let P be a Sylow p-subgroup of a finite nonabelian group G. Let bcl(G) be the size of the largest conjugacy classes of the group G. We show that if p is an odd prime but not a Mersenne prime or if P does not involve a section isomorphic to the wreath product \({Z_p \wr Z_p}\), then \({|P/O_p(G)| \leq bcl(G)}\).     

On <Emphasis Type="Italic">r</Emphasis>-recognition by prime graph of <Emphasis Type="Italic">B</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>(3) where <Emphasis Type="Italic">p</Emphasis> is an odd prime

Let G be a finite group. The prime graph Γ(G) of G is defined as follows. The vertices of Γ(G) are the primes dividing the order of G and two distinct vertices p and p′ are joined by an edge if there is an element in G of order pp′. We denote by k(Γ(G)) the number of isomorphism classes of finite groups H satisfying Γ(G) = Γ(H). Given a natural number r, a finite group G is called r-recognizable by prime graph if k(Γ(G)) =  r. In Shen et al. (Sib. Math. J. 51(2):244–254, 2010), it is proved that if p is an odd prime, then B _p (3) is recognizable by element orders. In this paper as the main result, we show that if G is a finite group such that Γ(G) = Γ(B _p (3)), where p > 3 is an odd prime, then \({G\cong B_p(3)}\) or C _p (3). Also if Γ(G) = Γ(B ₃(3)), then \({G\cong B_3(3), C_3(3), D_4(3)}\), or \({G/O_2(G)\cong {\rm Aut}(^2B_2(8))}\). As a corollary, the main result of the above paper is obtained.     

A class of constacyclic codes over a finite field-II

Let \(\mathbb{F}_q\) be a finite field with q = p ^m elements, where p is any prime and m ≥ 1. In this paper, we explicitly determine all the μ-constacyclic codes of length ? ⁿ over \(\mathbb{F}_q\), where ? is an odd prime coprime to p and the order of μ is a power of ?. All the repeated-root λ- constacyclic codes of length ? ⁿ p ^s over \(\mathbb{F}_q\) are also determined for any nonzero λ in \(\mathbb{F}_q\). As examples all the λ-constacyclic codes of length 3 ⁿ p ^s over \(\mathbb{F}_q\) for p = 5, 7, 11, 19 for n ≥ 1, s ≥ 1 are derived. We also obtain all the self-orthogonal negacyclic codes of length ? ⁿ over \(\mathbb{F}_q\) when q is odd prime power and give some illustrative examples.     

On locally finite Cpp-groups

A group G is called a Cpp-group for a prime number p, if G has elements of order p and the centralizer of every non-trivial p-element of G is a pgroup. In this paper we prove that the only infinite locally finite simple groups that are Cpp-groups are isomorphic either to PSL(2,K) or, if p = 2, to Sz(K), with K a suitable algebraic field over GF(p). Using this fact, we also give some structure theorems for infinite locally finite Cpp-groups.     

Complexities of normal bases constructed from Gauss periods

Let q be a power of a prime p, and let \(r=nk+1\) be a prime such that \(r\not \mid q\), where n and k are positive integers. Under a simple condition on q, r and k, a Gauss period of type (n, k) is a normal element of \({\mathbb {F}}_{q}^{n}\) over \({\mathbb {F}}_q\); the complexity of the resulting normal basis of \({\mathbb {F}}_{q}^{n}\) over \({\mathbb {F}}_q\) is denoted by C(n, k; p). Recent works determined C(n, k; p) for \(k\le 7\) and all qualified n and q. In this paper, we show that for any given \(k>0\), C(n, k; p) is given by an explicit formula except for finitely many primes \(r=nk+1\) and the exceptional primes are easily determined. Moreover, we describe an algorithm that allows one to compute C(n, k; p) for the exceptional primes \(r=nk+1\). Our numerical results cover C(n, k; p) for \(k\le 20\) and all qualified n and q.     

On finite groups with prime-power order <Emphasis Type="Italic">S</Emphasis>-quasinormally embedded subgroups

A subgroup H of a finite group G 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. In this paper we investigate the structure of finite groups that have some S-quasinormally embedded subgroups of prime-power order, and new criteria for p-nilpotency are obtained.     

Divisibility properties of hyperharmonic numbers

We extend Wolstenholme’s theorem to hyperharmonic numbers. Then, we obtain infinitely many congruence classes for hyperharmonic numbers using combinatorial methods. In particular, we show that the numerator of any hyperharmonic number in its reduced fractional form is odd. Then we give quantitative estimates for the number of pairs (n, r) lying in a rectangle where the corresponding hyperharmonic number \({ h_n^{(r)} }\) is divisible by a given prime number p. We also provide p-adic value lower bounds for certain hyperharmonic numbers. It is an open problem that given a prime number p, there are only finitely many harmonic numbers h _n which are divisible by p. We show that if we go to the higher levels r ≥  2, there are infinitely many hyperharmonic numbers \({ h_n^{(r)} }\) which are divisible by p. We also prove a finiteness result which is effective.     

Complete weight enumerators of a family of three-weight linear codes

Linear codes have been an interesting topic in both theory and practice for many years. In this paper, for an odd prime p, we present the explicit complete weight enumerator of a family of p-ary linear codes constructed with defining set. The weight enumerator is an immediate result of the complete weight enumerator, which shows that the codes proposed in this paper are three-weight linear codes. Additionally, all nonzero codewords are minimal and thus they are suitable for secret sharing.     

Algorithmic tests and randomness with respect to a class of measures

This paper offers some new results on randomness with respect to classes of measures, along with a didactic exposition of their context based on results that appeared elsewhere. We start with the reformulation of the Martin-Löf definition of randomness (with respect to computable measures) in terms of randomness deficiency functions. A formula that expresses the randomness deficiency in terms of prefix complexity is given (in two forms). Some approaches that go in another direction (from deficiency to complexity) are considered. The notion of Bernoulli randomness (independent coin tosses for an asymmetric coin with some probability p of head) is defined. It is shown that a sequence is Bernoulli if it is random with respect to some Bernoulli measure B _p . A notion of “uniform test” for Bernoulli sequences is introduced which allows a quantitative strengthening of this result. Uniform tests are then generalized to arbitrary measures. Bernoulli measures B _p have the important property that p can be recovered from each random sequence of B _p . The paper studies some important consequences of this orthogonality property (as well as most other questions mentioned above) also in the more general setting of constructive metric spaces.     

Division algebras of prime degree with infinite genus

The genus gen(D) of a finite-dimensional central division algebra D over a field F is defined as the collection of classes [D′] ∈ Br(F), where D′ is a central division F-algebra having the same maximal subfields as D. For any prime p, we construct a division algebra of degree p with infinite genus. Moreover, we show that there exists a field K such that there are infinitely many nonisomorphic central division K-algebras of degree p and any two such algebras have the same genus.