Authors:Giorgos Kapetanakis Abstract: In this note, we employ the techniques of Swan (Pac J Math 12(3):1099–1106, 1962) with the purpose of studying the parity of the number of the irreducible factors of the penatomial \(X^n+X^{3s}+X^{2s}+X^{s}+1\in \mathbb {F}_2[X]\) , where s is even and \(n>3s\) . Our results imply that if \(n \not \equiv \pm 1 \pmod {8}\) , then the polynomial in question is reducible. PubDate: 2019-01-02 DOI: 10.1007/s00200-018-0378-7

Authors:Sayaka Ishizuki; Michio Oyamaguchi; Masahiko Sakai Abstract: This paper presents a counterexample for the open conjecture whether innermost joinability of all critical pairs ensures confluence of innermost terminating term rewriting systems. We then show that innermost joinability of all normalized instances of the critical pairs is a necessary and sufficient condition. Using this condition, we give a decidable sufficient condition for confluence of innermost terminating systems. Finally, we enrich the condition by introducing the notion of left-stable rules. As a corollary, confluence of innermost terminating left-weakly-shallow TRSs is shown to be decidable. PubDate: 2019-01-02 DOI: 10.1007/s00200-018-0377-8

Authors:Dongmei Huang; Chunming Tang; Yanfeng Qi; Maozhi Xu Abstract: In this paper, we first discuss the bentness of a large class of quadratic Boolean functions in polynomial form \(f(x)=\sum _{i=1}^{{n}/{2}-1}\mathrm {Tr}^n_1(c_ix^{1+2^i})+ \mathrm {Tr}_1^{n/2}(c_{n/2}x^{1+2^{n/2}})\) , where n is even, \(c_i\in \mathrm {GF}(2^n)\) for \(1\le i \le {n}/{2}-1\) and \(c_{n/2}\in \mathrm {GF}(2^{n/2})\) . The bentness of these functions can be connected with linearized permutation polynomials. Hence, methods for constructing quadratic bent functions are given. Further, we consider a subclass of quadratic Boolean functions of the form \(f(x)=\sum _{i=1}^{{m}/{2}-1}\mathrm {Tr}^n_1(c_ix^{1+2^{ei}})+ \mathrm {Tr}_1^{n/2}(c_{m/2}x^{1+2^{n/2}})\) , where \(n=em\) , m is even, and \(c_i\in \mathrm {GF}(2^e)\) . The bentness of these functions is characterized and some methods for deriving new quadratic bent functions are given. Finally, when m and e satisfy some conditions, we determine the number of these quadratic bent functions. PubDate: 2019-01-01 DOI: 10.1007/s00200-018-0376-9

Authors:Amaro Barreal; Capi Corrales Rodrigáñez; Camilla Hollanti Pages: 371 - 391 Abstract: Algebraic space–time coding—a powerful technique developed in the context of multiple-input multiple-output (MIMO) wireless communications—has profited tremendously from tools from Class Field Theory and, more concretely, the theory of central simple algebras and their orders. During the last decade, the study of space–time codes for practical applications, and more recently for future generation (5G \(+\) ) wireless systems, has provided a practical motivation for the consideration of many interesting mathematical problems. One such problem is the explicit computation of orders of central simple algebras with small discriminants. In this article, we consider the most interesting asymmetric MIMO channel setups and, for each treated case, we provide explicit pairs of fields and a corresponding non-norm element giving rise to a cyclic division algebra whose natural order has the minimum possible discriminant. PubDate: 2018-11-01 DOI: 10.1007/s00200-017-0348-5 Issue No:Vol. 29, No. 5 (2018)

Authors:Javad Doliskani Pages: 393 - 407 Abstract: For an elliptic curve E over a finite field \(\mathbb {F}_q\) , where q is a prime power, we propose new algorithms for testing the supersingularity of E. Our algorithms are based on the polynomial identity testing problem for the p-th division polynomial of E. In particular, an efficient algorithm using points of high order on E is given. PubDate: 2018-11-01 DOI: 10.1007/s00200-018-0349-z Issue No:Vol. 29, No. 5 (2018)

Authors:Qian Liu; Yujuan Sun; WeiGuo Zhang Pages: 409 - 431 Abstract: Permutation polynomials have important applications in cryptography, coding theory, combinatorial designs, and other areas of mathematics and engineering. Finding new classes of permutation polynomials is therefore an interesting subject of study. In this paper, for an integer s satisfying \(s=\frac{q^n-1}{2}+q^r\) , we give six classes of permutation polynomials of the form \((ax^{q^m}-bx+\delta )^s+L(x)\) over \(\mathbb {F}_{q^n}\) , and for s satisfying \(s(p^m-1)\equiv p^m-1\ (mod\ p^n-1)\) or \(s(p^{{\frac{k}{2}}m}-1)\equiv p^{km}-1 (mod\ p^n-1)\) , we propose three classes of permutation polynomials of the form \((aTr_m^n(x)+\delta )^s+L(x)\) over \(\mathbb {F}_{p^n}\) , respectively. PubDate: 2018-11-01 DOI: 10.1007/s00200-018-0350-6 Issue No:Vol. 29, No. 5 (2018)

Authors:Kondwani Magamba; John A. Ryan Abstract: We obtain an upper bound on the number of extended irreducible q-ary Goppa codes of degree r and length \(q^n+1\) , where \(q=p^t\) and n and \(r>2\) are prime numbers. PubDate: 2018-11-21 DOI: 10.1007/s00200-018-0375-x

Authors:Mustafa Uçkun; Ebubekir İnan Abstract: This article introduces approximately \(\varGamma \) -semigroups, approximately \(\varGamma \) -ideals and approximately upper \(\varGamma \) -ideals in proximal relator spaces. Some properties of descriptively approximations are investigated using by object description \(\varGamma \) -homomorphism. Furthermore, an example of approximately \(\varGamma \) -semigroup with working on digital images. PubDate: 2018-11-10 DOI: 10.1007/s00200-018-0374-y

Authors:Nurettin Bağırmaz Abstract: In this paper, we firstly introduce the notion of a near approximations in a group, which is an extended notion of a rough approximations in a group. Then we define lower and upper near subgroups based on normal subgroups in a group and give some properties of such subgroups. Furthermore, we obtain a comparison between these types of approximations and the approximation introduced by Kuroki and Wang (Inf Sci 90:203–220, 1996). PubDate: 2018-11-08 DOI: 10.1007/s00200-018-0373-z

Authors:Koji Chinen Abstract: Zeta functions for linear codes were defined by Iwan Duursma in 1999 as generating functions for the Hamming weight enumerators of linear codes. They were generalized to the case of some invariant polynomials and so-called the formal weight enumerators by the present author. One of the most important problems from the applicable point of view is whether extremal weight enumerators satisfy the Riemann hypothesis. In this article, we show there exist extremal polynomials of the weight enumerator type, not being related to existing codes, which are invariant under the MacWilliams transform and do not satisfy the Riemann hypothesis. Such examples are contained in a certain invariant polynomial ring which is found by the use of the binomial moment. We determine the group which fixes the ring. To formulate the extremal property, we also establish an analog of the Mallows–Sloane bound for a certain sequence of the members in the ring. PubDate: 2018-10-10 DOI: 10.1007/s00200-018-0372-0

Authors:Xiaoqiang Wang; Dabin Zheng; Hongwei Liu Abstract: In this paper, several classes of two-weight or three-weight linear codes over \( {{\mathbb {F}}}_p\) from quadratic or non-quadratic functions are constructed and their weight distributions are determined. From the constructed codes, we obtain some optimal linear codes with respect to the Singleton bound and the Griesmer bound. These two- or three-weight linear codes may have applications in secret sharing, authentication codes, association schemes and strongly regular graphs. PubDate: 2018-05-24 DOI: 10.1007/s00200-018-0359-x

Authors:Krzysztof Ziemiański Abstract: Let K be an arbitrary semi-cubical set that can be embedded in a standard cube. Using Discrete Morse Theory, we construct a CW-complex that is homotopy equivalent to the space \(\vec {P}(K)_v^w\) of directed paths between two given vertices v, w of K. In many cases, this construction is minimal: the cells of the constructed CW-complex are in 1–1 correspondence with the generators of the homology of \(\vec {P}(K)_v^w\) . PubDate: 2018-05-23 DOI: 10.1007/s00200-018-0360-4

Authors:Joris van der Hoeven Abstract: In this paper, we will present several algorithms for computing with D-algebraic power series. Such power series are specified by one or more algebraic differential equations and a sufficient number of initial conditions. The emphasis is not on the efficient computation of coefficients of such power series (various techniques are known for that), but rather on the ability to decide whether expressions involving D-algebraic power series are zero. We will both consider univariate and multivariate series and, besides the usual ring operations and differentiation, we will also consider composition, implicitly determined power series and monomial transformations. PubDate: 2018-05-03 DOI: 10.1007/s00200-018-0358-y

Authors:Shanding Xu; Xiwang Cao; Guangkui Xu; Chunming Tang Abstract: Direct-sequence spread spectrum and frequency-hopping (FH) spread spectrum are two main spread-coding technologies. Frequency-hopping sequences (FHSs) achieving the well-known Lempel–Greenberger bound play an important part in FH code-division multiple-access systems. Our objective is to construct more FHSs with new parameters attaining the above bound. In this paper, two classes of FHSs are proposed by means of two partitions of \({{\mathbb {Z}}_{v}}\) , where v is an odd positive integer. It is shown that all the constructed FHSs are optimal with respect to the Lempel–Greenberger bound. By choosing appropriate injective functions, infinitely many optimal FHSs can be recursively obtained. Above all, these FHSs have new parameters which are not covered in the former literature. PubDate: 2018-04-13 DOI: 10.1007/s00200-018-0356-0

Authors:Yanfeng Qi; Chunming Tang; Dongmei Huang Abstract: This paper considers two classes of p-ary functions studied by Li et al. (IEEE Trans Inf Theory 59(3):1818–1831, 2013). The first class of p-ary functions is of the form $$\begin{aligned} f(x)=Tr^n_1\left( a x^{l(q-1)}+b x^{\left( l+\frac{q+1}{2}\right) (q-1)}\right) +\epsilon x^{\frac{q^2-1}{2}}. \end{aligned}$$ Another class of p-ary functions is of the form $$\begin{aligned} f(x)={\left\{ \begin{array}{ll} \sum ^{q-1}_{i=0} Tr^n_1(a x^{(ri+s)(q-1)})+\epsilon x^{\frac{q^2-1}{2}},&{} x\ne 0,\\ f(0),&{} x=0. \end{array}\right. } \end{aligned}$$ We generalize Li et al.’s results, give necessary conditions for two classes of bent functions, and present more explicit characterization of these regular bent functions for different cases. PubDate: 2018-04-07 DOI: 10.1007/s00200-018-0357-z

Authors:J. Wolfmann Abstract: We introduce a construction of binary 3-weight codes and near-bent functions from 2-weight projective codes. PubDate: 2018-04-04 DOI: 10.1007/s00200-018-0354-2

Authors:Fei Li Abstract: Firstly, we give a formula on the generalized Hamming weights of linear codes constructed generically by defining sets. Secondly, by choosing properly the defining set we obtain a class of cyclotomic linear codes and then present two alternative formulas for calculating their generalized Hamming weights. Lastly, we determine their weight distributions and generalized Hamming weights partially. Especially, we solve the generalized Hamming weights completely in one case. PubDate: 2018-04-02 DOI: 10.1007/s00200-018-0355-1

Authors:Yanping Wang; Zhengbang Zha; Weiguo Zhang Abstract: Permutation trinomials over finite fields are of great interest for their simple algebraic forms and important applications in many areas of mathematics and engineering. In this paper, six new classes of permutation trinomials over \(\mathbb {F}_{3^{3k}}\) are presented based on the multivariate method. Their permutation properties are proved by using the resultant elimination method. PubDate: 2018-03-20 DOI: 10.1007/s00200-018-0353-3

Authors:Yuan Cao; Yonglin Cao; Fang-Wei Fu Abstract: Let m, e be positive integers, p a prime number, \(\mathbb {F}_{p^m}\) be a finite field of \(p^m\) elements and \(R=\mathbb {F}_{p^m}[u]/\langle u^e\rangle \) which is a finite chain ring. For any \(\omega \in R^\times \) and positive integers k, n satisfying \(\mathrm{gcd}(p,n)=1\) , we prove that any \((1+\omega u)\) -constacyclic code of length \(p^kn\) over R is monomially equivalent to a matrix-product code of a nested sequence of \(p^k\) cyclic codes with length n over R and a \(p^k\times p^k\) matrix \(A_{p^k}\) over \(\mathbb {F}_p\) . Using the matrix-product structures, we give an iterative construction of every \((1+\omega u)\) -constacyclic code by \((1+\omega u)\) -constacyclic codes of shorter lengths over R. PubDate: 2018-03-06 DOI: 10.1007/s00200-018-0352-4

Authors:Francis N. Castro; Luis A. Medina; Pantelimon Stănică Abstract: Exponential sums of symmetric Boolean functions are linear recurrent with integer coefficients. This was first established by Cai, Green and Thierauf in the mid nineties. Consequences of this result has been used to study the asymptotic behavior of symmetric Boolean functions. Recently, Cusick extended it to rotation symmetric Boolean functions, which are functions with good cryptographic properties. In this article, we put all these results in the general context of Walsh transforms and some of its generalizations (nega–Hadamard transform, for example). Precisely, we show that Walsh transforms, for which exponential sums are just an instance, of symmetric and rotation symmetric Boolean functions satisfy linear recurrences with integer coefficients. We also provide a closed formula for the Walsh transform and nega–Hadamard transform of any symmetric Boolean functions. Moreover, using the techniques presented in this work, we show that some families of rotation symmetric Boolean functions are not bent when the number of variables is sufficiently large and provide asymptotic evidence to a conjecture of Stănică and Maitra. PubDate: 2018-02-20 DOI: 10.1007/s00200-018-0351-5