Abstract: Publication date: July 2017 Source:Finite Fields and Their Applications, Volume 46 Author(s): Nurdagül Anbar, Wilfried Meidl For c ∈ F 2 n , a c-bent4 function f from the finite field F 2 n to F 2 is a function with a flat spectrum with respect to the unitary transform V f c , which is designed to describe the component functions of modified planar functions. For c = 0 the transform V f c reduces to the conventional Walsh transform, and hence a 0-bent4 function is bent. In this article we generalize the concept of partially bent functions to the transforms V f c . We show that every quadratic function is partially bent, and hence it is plateaued with respect to any of the transforms V f c . In detail we analyse two quadratic monomials. The first has values as small as possible in its spectra with respect to all transforms V f c , and the second has a flat spectrum for a large number of c. Moreover, we show that every quadratic function is c-bent4 for at least three distinct c. In the last part we analyse a cubic monomial. We show that it is c-bent4 only for c = 1 , the function is then called negabent, which shows that non-quadratic functions exhibit a different behaviour.

Abstract: Publication date: July 2017 Source:Finite Fields and Their Applications, Volume 46 Author(s): Zhi-Wei Sun In this paper we study some sophisticated supercongruences involving dual sequences. For n = 0 , 1 , 2 , … define d n ( x ) = ∑ k = 0 n ( n k ) ( x k ) 2 k and s n ( x ) = ∑ k = 0 n ( n k ) ( x k ) ( x + k k ) = ∑ k = 0 n ( n k ) ( − 1 ) k ( x k ) ( − 1 − x k ) . For any odd prime p and p-adic integer x, we determine ∑ k = 0 p − 1 ( ± 1 ) k d k ( x ) 2 and ∑ k = 0 p − 1 ( 2 k + 1 ) d k ( x ) 2 modulo p 2 ; for example, we establish the new p-adic congruence ∑ k = 0 p − 1 ( − 1 ) k d k ( x ) 2 ≡ ( − 1 ) 〈 x 〉 p ( mod p 2 ) , where 〈 x 〉 p denotes the least nonnegative integer r with x ≡ r ( mod p ) . For any prime p > 3 and p-adic integer x, we determine PubDate: 2017-04-23T07:06:14Z

Abstract: Publication date: July 2017 Source:Finite Fields and Their Applications, Volume 46 Author(s): Elif Segah Oztas, Bahattin Yildiz, Irfan Siap In this work we introduce a novel approach to find reversible codes over different alphabets, using so-called coterm polynomials and a module-construction. We obtain many optimal reversible codes with these constructions. In an attempt to apply the constructions to the DNA, we identify k-bases of DNA with elements in the ring R 2 k = F 2 [ u ] / ( u 2 k − 1 ) , and by using a form of coterm polynomials, we are able to solve the reversibility and complement problems in DNA codes over this ring. With a freedom on the choice of k we are able to embed any DNA code in a suitable ring, giving an algebraic structure to the DNA codes. We are also able to find reversible and reversible-complement codes that are not necessarily linear cyclic codes.

Abstract: Publication date: July 2017 Source:Finite Fields and Their Applications, Volume 46 Author(s): Qi Cheng, Shuhong Gao, J. Maurice Rojas, Daqing Wan Suppose q is a prime power and f ∈ F q [ x ] is a univariate polynomial with exactly t monomial terms and degree < q − 1 . To establish a finite field analogue of Descartes' Rule, Bi, Cheng, and Rojas (2013) proved an upper bound of 2 ( q − 1 ) t − 2 t − 1 on the number of cosets in F q ⁎ needed to cover the roots of f in F q ⁎ . Here, we give explicit f with root structure approaching this bound: When q is a perfect ( t − 1 ) -st power we give an explicit t-nomial vanishing on q t − 2 t − 1 distinct cosets of F q ⁎ . Over prime fields F p , computational data we provide suggests that it is harder to construct explicit sparse polynomials with many roots. Nevertheless, assuming the Generalized Riemann Hypothesis, we find explicit trinomials having Ω ( log p log log p ) distinct roots in F p .

Abstract: Publication date: July 2017 Source:Finite Fields and Their Applications, Volume 46 Author(s): Abhishek Bhowmick, Thái Hoàng Lê, Yu-Ru Liu We prove a character sum estimate in F q [ t ] and answer a question of Shparlinski.

Abstract: Publication date: July 2017 Source:Finite Fields and Their Applications, Volume 46 Author(s): Ron Evans, Mark Van Veen Let n > 1 be an integer, and let F p denote a field of p elements for a prime p ≡ 1 ( mod n ) . By 2015, the question of existence or nonexistence of n-th power residue difference sets in F p had been settled for all n < 24 . We settle the case n = 24 by proving the nonexistence of 24-th power residue difference sets in F p . We also prove the nonexistence of qualified 24-th power residue difference sets in F p . The proofs make use of a Mathematica program which computes formulas for the cyclotomic numbers of order 24 in terms of parameters occurring in quadratic partitions of p.

Abstract: Publication date: July 2017 Source:Finite Fields and Their Applications, Volume 46 Author(s): Mariusz Kwiatkowski, Mark Pankov Let Γ k ( V ) be the Grassmann graph formed by k-dimensional subspaces of an n-dimensional vector space over the finite field F q consisting of q elements and 1 < k < n − 1 . Denote by Γ ( n , k ) q the restriction of the Grassmann graph to the set of all non-degenerate linear [ n , k ] q codes. We describe maximal cliques of the graph Γ ( n , k ) q and show that every automorphism of this graph is induced by a monomial semilinear automorphism of V.

Abstract: Publication date: July 2017 Source:Finite Fields and Their Applications, Volume 46 Author(s): B.K. Dass, Namita Sharma, Rashmi Verma The paper begins by giving a counter example to show that the algorithm for construction of new perfect poset codes from a given perfect poset code by removal of a coordinate as given by Lee (2004) [11] does not hold. The algorithm has been improved and generalized to obtain new perfect poset block codes from a given perfect poset block code. The modified necessary and sufficient conditions for the construction of new perfect poset codes have been derived as a particular case. A bound has been obtained on the height of poset P s that turns a given π-code into r-perfect ( P s , π ) -code. We show that there does not exist a poset which admits the binary Simplex code of order 3 to be a 2-perfect poset code. Also, all the poset structures which admit the extended ternary Golay code to be a 3-perfect poset code have been classified.

Abstract: Publication date: July 2017 Source:Finite Fields and Their Applications, Volume 46 Author(s): Ilaria Cardinali, Luca Giuzzi A k-polar Grassmannian is a geometry having as pointset the set of all k-dimensional subspaces of a vector space V which are totally isotropic for a given non-degenerate bilinear form μ defined on V. Hence it can be regarded as a subgeometry of the ordinary k-Grassmannian. In this paper we deal with orthogonal line Grassmannians and with symplectic line Grassmannians, i.e. we assume k = 2 and μ to be a non-degenerate symmetric or alternating form. We will provide a method to efficiently enumerate the pointsets of both orthogonal and symplectic line Grassmannians. This has several nice applications; among them, we shall discuss an efficient encoding/decoding/error correction strategy for line polar Grassmann codes of either type.

Abstract: Publication date: July 2017 Source:Finite Fields and Their Applications, Volume 46 Author(s): M. Calderini, M. Sala, I. Villa APN permutations in even dimension are vectorial Boolean functions that play a special role in the design of block ciphers. We study their properties, providing some general results and some applications to the low-dimension cases. In particular, we prove that none of their components can be quadratic. For an APN vectorial Boolean function (in even dimension) with all cubic components we prove the existence of a component having a large number of balanced derivatives. Using these restrictions, we obtain the first theoretical proof of the non-existence of APN permutations in dimension 4. Moreover, we derive some constraints on APN permutations in dimension 6.

Abstract: Publication date: July 2017 Source:Finite Fields and Their Applications, Volume 46 Author(s): Yongbo Xia, Chunlei Li Based on a generic construction, two classes of ternary three-weight linear codes are obtained from a family of power functions, including some APN power functions. The weight distributions of these linear codes are determined by studying the properties of some exponential sums related to the power functions.

Abstract: Publication date: July 2017 Source:Finite Fields and Their Applications, Volume 46 Author(s): Danyao Wu, Pingzhi Yuan, Cunsheng Ding, Yuzhen Ma Permutation polynomials are an interesting subject of mathematics and have applications in other areas of mathematics and engineering. In this paper, we determine all permutation trinomials over F 2 m in Zieve's paper [30]. We prove a conjecture proposed by Gupta and Sharma in [8] and obtain some new permutation trinomials over F 2 m . Finally, we show that some classes of permutation trinomials with parameters are QM equivalent to some known permutation trinomials.

Abstract: Publication date: July 2017 Source:Finite Fields and Their Applications, Volume 46 Author(s): Liqing Xu, Hao Chen Binary constant weight codes have important applications in various topics and have been studied for many years. Optimal or near-optimal binary constant weight codes of small lengths have been determined. In this paper we propose an improvement of the Ericson–Zinoviev construction of binary constant weight codes from q-ary codes. By applying this improvement to Reed–Solomon codes, some new or optimal binary constant weight codes are presented. In particular new binary constant weight codes A ( 64 , 10 , 8 ) ≥ 4112 and A ( 64 , 12 , 8 ) ≥ 522 are constructed. We also give explicitly constructed binary constant weight codes which improve the Gilbert and the Graham–Sloane lower bounds asymptotically in a small range of parameters. Some new binary constant weight codes constructed from algebraic-geometric codes by applying our this improvement are also presented.

Abstract: Publication date: July 2017 Source:Finite Fields and Their Applications, Volume 46 Author(s): Hengzhou Xu, Baoming Bai, Dan Feng, Cheng Sun Motivated by the works on the girth of Tanner ( 3 , 5 ) and ( 3 , 7 ) quasi-cyclic (QC) low-density parity-check (LDPC) codes done by S. Kim et al. and M. Gholami et al., respectively, we analyze the cycles of Tanner ( 3 , 11 ) QC LDPC codes and present the sufficient and necessary conditions for the existence of cycles of lengths 4, 6, 8, and 10 in Tanner ( 3 , 11 ) QC LDPC codes. By checking these conditions, the girth values of Tanner ( 3 , 11 ) QC LDPC codes are derived.

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Qiang Wang In this note, we give a shorter proof of the result of Zheng, Yu, and Pei on the explicit formula of inverses of generalized cyclotomic permutation polynomials over finite fields. Moreover, we characterize all these cyclotomic permutation polynomials that are involutions. Our results provide a fast algorithm (only modular operations are involved) to generate many classes of generalized cyclotomic permutation polynomials, their inverses, and involutions.

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Hyun Jin Kim, Yoonjin Lee We develop a construction method of isodual codes over G F ( q ) , where q is a prime power; we construct isodual codes over G F ( q ) of length 2 n + 2 from isodual codes over G F ( q ) of length 2n. Using this method, we find some isodual codes over G F ( q ) , where q = 2 , 3 and 5. In more detail, we obtain binary isodual codes of lengths 32, 34, 36, 38, and 40, where all these codes of lengths 32, 34, and 36 are optimal and some codes of length 38 are optimal. We note that all these binary isodual codes are not self-dual codes, and in particular, in the case of length 38 all their weight enumerators are different from those of binary self-dual codes of the same length; in fact, four binary isodual codes of length 38 are formally self-dual even codes. We construct isodual codes over G F ( 3 ) and G F ( 5 ) of lengths 4, 6, and 8 as well.

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Ute Spreckels Let A be a principally polarized CM abelian variety of dimension d defined over a number field F containing the CM-field K. Let ℓ be a prime number unramified in K / Q . The Galois group G ℓ of the ℓ-division field of A lies in a maximal torus of the general symplectic group of dimension 2d over F ℓ . Relying on a method of Weng, we explicitly write down this maximal torus as a matrix group. We restrict ourselves to the case that G ℓ equals the maximal torus. If p is a prime ideal in F with p p , let A p be the reduction of A modulo p . By counting matrices with eigenvalue 1 in G ℓ we obtain a formula for the density of primes p such that the ℓ-rank of A p ( F p ) is at least 1. Thereby we generalize results of Koblitz and Weng who computed this density for d = 1 and 2. Both authors gave conjectural formulae for the number of primes p with norm less than n such that A p ( F p ) has prime order. We describe the involved heuristics, generalize these conjectures to arbitrary d and provide examples with d = 3 .

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Kyung-Ah Shim, Cheol-Min Park, Namhun Koo Public-Key Cryptography (PKC) based on multivariate quadratic equations is one of the most promising alternatives for classical PKC after the eventual coming of quantum computers. Recently, Shen and Tang proposed a new MQ-signature scheme, RGB, based on three types of variables, Red(r), Green(g) and Blue(b). They claimed that signing for RGB is faster than that of UOV and Rainbow. At ACISP 2016, Tang et al. implemented RGB on S5PV210 and MT6582 microprocessors at 64, 80, 96, 118 and 128-bit security levels for practical use. Their results are much more efficient than other MQ-signature schemes, so RGB is very appealing for resource-limited devices. We show that RGB with their suggested parameters at 64, 80, 96, 118 and 128 security levels are entirely broken by key recovery attacks using good keys. From a practical point of view, we are able to break their parameters at 64, 80, 96, 118 and 128 security levels in less than 0.48 seconds, 1.7 seconds, 90.68 seconds, 11 minutes and 6.82 hours, respectively. Consequently, we show that signing and the key sizes for RGB with secure parameter sets are much slower and larger than those of UOV and Rainbow.

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Ashkan Nikseresht Let A = F [ x ] 〈 f ( x ) 〉 , where f ( x ) is a monic polynomial over a finite field F . In this paper, we study the relation between A-codes and their duals. In particular, we state a counterexample and a correction to a theorem of Berger and El Amrani (2014) [3] and present an efficient algorithm to find a system of generators for the dual of a given A-code. Also we characterize self-dual A-codes of length 2 and investigate when the F -dual of A-codes are A-codes.

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Gaopeng Jian, Rongquan Feng, Hongfeng Wu The generalized Hamming weights of a linear code have been extensively studied since Wei first use them to characterize the cryptography performance of a linear code over the wire-tap channel of type II. In this paper, we investigate the generalized Hamming weights of three classes of linear codes constructed through defining sets and determine them partly for some cases. Particularly, in the semiprimitive case we solve a problem left in Yang et al. (2015) [30].

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Shuxing Li The generalized Hamming weights (GHWs) are fundamental parameters of linear codes. GHWs are of great interest in many applications since they convey detailed information of linear codes. In this paper, we continue the work of [10] to study the GHWs of a family of cyclic codes with arbitrary number of nonzeroes. The weight hierarchy is determined by employing a number-theoretic approach.

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Jan Tuitman We introduce a new algorithm to compute the zeta function of a curve over a finite field. This method extends previous work of ours to all curves for which a good lift to characteristic zero is known. We develop all the necessary bounds, analyse the complexity of the algorithm and provide a complete implementation.

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Nuh Aydin, Ajdin Halilović Cyclic codes and their various generalizations, such as quasi-twisted (QT) codes, have a special place in algebraic coding theory. Among other things, many of the best-known or optimal codes have been obtained from these classes. In this work we introduce a new generalization of QT codes that we call multi-twisted (MT) codes and study some of their basic properties. Presenting several methods of constructing codes in this class and obtaining bounds on the minimum distances, we show that there exist codes with good parameters in this class that cannot be obtained as QT or constacyclic codes. This suggests that considering this larger class in computer searches is promising for constructing codes with better parameters than currently best-known linear codes. Working with this new class of codes motivated us to consider a problem about binomials over finite fields and to discover a result that is interesting in its own right.

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Boran Kim, Yoonjin Lee We completely determine the minimum Lee weights of cyclic self-dual codes over a Galois ring G R ( p 2 , m ) of length p k , where m and k are positive integers and p is a prime number. We obtain all cyclic self-dual codes over G R ( 2 2 , 1 ) ≅ Z 4 of lengths 16 and 32 with their Lee weight enumerators. We also find cyclic self-dual codes over G R ( 3 2 , 1 ) ≅ Z 9 (respectively, G R ( 3 2 , 2 ) ) of lengths up to 27 (respectively, 9). Most of the cyclic self-dual codes we found are extremal with respect to the Lee weights.

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Momonari Kudo, Shushi Harashita This paper contains a complete study of superspecial curves of genus 4 in characteristic p ≤ 7 . We prove that there does not exist a superspecial curve of genus 4 in characteristic 7. This is a negative answer to the genus 4 case of the problem proposed by Ekedahl [9] in 1987. This implies the non-existence of maximal curve of genus 4 over F 49 , which updates the table at manypoints.org . We give an algorithm to enumerate superspecial nonhyperelliptic curves in arbitrary p ≥ 5 , and for p ≤ 7 we execute it with our implementation on a computer algebra system Magma. Our result in p = 5 re-proves the uniqueness of maximal curves of genus 4 over F 25 , see [11] for the original theoretical proof. In Appendix, we present a general method determining Hasse–Witt matrices of curves which are complete intersections.

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): K. Kim, J. Namgoong, I. Yie In [8], G. Kyureghyan showed that the function F ( x ) = x + γ f ( x ) is a permutation of F q m when f : F q m → F q is a function, γ ∈ F q m is a b-linear translator for f for some b ( ≠ − 1 ) ∈ F q . His idea has been extended in [19] by Qin et al. and in [9] by M. Kyureghyan and Abrahamyan to finitely many function–linear translator pairs. In this paper, we study the permutations generated by function–linear translator pairs along G. Kyureghyan's idea and prove that these permutations form groups whose group structures are well understood.

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Fengwei Li, Qin Yue, Fengmei Liu Let α be a primitive element of a finite field F r , where r = q m 1 m 2 and gcd ( m 1 , m 2 ) = d , so α 1 = α r − 1 q m 1 − 1 and α 2 = α r − 1 q m 2 − 1 are primitive elements of F q m 1 and F q m 2 , respectively. Let e be a positive integer such that gcd ( e , q m 2 − 1 q d − 1 ) = 1 , F q m 2 = F q ( α 2 e ) , and α 1 and α 2 e are not conjugates over F q . We define a cyclic code C = { c ( a , b ) : a ∈ F q m 1 , b ∈ F q m 2 } , c ( a , b ) = ( T 1 ( a α 1 i ) + T 2 ( b α 2 e i ) ) i = 0 n − 1 , where ... PubDate: 2017-01-11T21:07:45Z

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): John B. Little The theory of affine geometries over the rings Z / 〈 q − 1 〉 can be used to understand the properties of toric and generalized toric codes over F q . The standard generator matrices of these codes are produced by evaluating collections of monomials in m variables at the points of the algebraic torus ( F q ⁎ ) m . The exponent vector of such a monomial can be viewed as a point in one of these affine geometries and the minimum distance of the resulting code is strongly tied to the lines in the finite geometry that contain those points. We argue that this connection is, in fact, even more direct than the connection with the lattice geometry of those exponent vectors considered as elements of Z 2 or R 2 . This point of view should be useful both as a way to visualize properties of these codes and as a guide to heuristic searches for good codes constructed in this fashion. In particular, we will use these ideas to see a reason why these constructions have been so successful over the field F 8 , but less successful in other cases.

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Shantian Cheng We introduce a new method from number fields and codes to construct dense packings in the Euclidean spaces. Via the canonical Q -embedding of arbitrary number field K into R [ K : Q ] , both the prime ideal p and its residue field κ can be embedded as discrete subsets in R [ K : Q ] . Thus we can concatenate the embedding image of the Cartesian product of n copies of p together with the image of a length n code over κ. This concatenation leads to a packing in the Euclidean space R n [ K : Q ] . Moreover, we extend the single concatenation to multiple concatenations to obtain dense packings and asymptotically good packing families. For instance, with the help of Magma, we construct a 256-dimensional packing denser than the Barnes–Wall lattice BW256.

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Cunsheng Ding, Cuiling Fan, Zhengchun Zhou Cyclic Reed–Solomon codes, a type of BCH codes, are widely used in consumer electronics, communication systems, and data storage devices. This fact demonstrates the importance of BCH codes – a family of cyclic codes – in practice. In theory, BCH codes are among the best cyclic codes in terms of their error-correcting capability. A subclass of BCH codes are the narrow-sense primitive BCH codes. However, the dimension and minimum distance of these codes are not known in general. The objective of this paper is to determine the dimension and minimum distances of two classes of narrow-sense primitive BCH codes with designed distances δ = ( q − 1 ) q m − 1 − 1 − q ⌊ ( m − 1 ) / 2 ⌋ and δ = ( q − 1 ) q m − 1 − 1 − q ⌊ ( m + 1 ) / 2 ⌋ . The weight distributions of some of these BCH codes are also reported. As will be seen, the two classes of BCH codes are sometimes optimal and sometimes among the best linear codes known.

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Shudi Yang, Chuangqiang Hu The Weierstrass semigroups and pure gaps can be helpful in constructing codes with better parameters. In this paper, we investigate explicitly the minimal generating set of the Weierstrass semigroups associated with several totally ramified places over arbitrary Kummer extensions. Applying the techniques provided by Matthews in her previous work, we extend the results of specific Kummer extensions studied in the literature. Some examples are included to illustrate our results.

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Sunghan Bae, Pyung-Lyun Kang, Chengju Li Let r i be positive integers and R i = Z 2 [ x ] / 〈 x r i − 1 〉 for 1 ≤ i ≤ ℓ . Denote R = R 1 × R 2 × ⋯ × R ℓ . Generalized quasi-cyclic (GQC) code C of length ( r 1 , r 2 , … , r ℓ ) over Z 2 can be viewed as Z 2 [ x ] -submodule of R . In this paper, we investigate the algebraic structure of C by presenting its normalized generating set. We also present a method to determine the normalized generating set of the dual code of C , which is derived from the normalized generating set of C .

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Sami Omar, Saber Bouanani In a previous paper [4], we extended the Li criterion for the Riemann hypothesis for a function field K of genus g over a finite field F q . More recently, further numerical computations of the Li coefficients for the Dirichlet and Hecke L-functions have led to the conjecture that they are positive and increasing under the Riemann hypothesis. In this paper, we show the that the Li coefficients λ K ( n ) for the function field K are increasing in n.

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Jaydeep Chipalkatti Let P 2 denote the projective plane over a finite field F q . A pair of nonsingular conics ( A , B ) in the plane is said to satisfy the Poncelet triangle condition if, considered as conics in P 2 ( F ‾ q ) , they intersect transversally and there exists a triangle inscribed in A and circumscribed around B . It is shown in this article that a randomly chosen pair of conics satisfies the triangle condition with asymptotic probability 1 / q . We also make a conjecture based upon computer experimentation which predicts this probability for tetragons, pentagons and so on up to enneagons.

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Xuemei Zhang, Yaojun Chen, T.C. Edwin Cheng For two given graphs G 1 and G 2 , the Ramsey number R ( G 1 , G 2 ) is the smallest integer N such that for any graph of order N, either G contains a copy of G 1 or its complement contains a copy of G 2 . Let C m be a cycle of length m and K 1 , n a star of order n + 1 . Parsons (1975) [6] shows that R ( C 4 , K 1 , n ) ≤ n + ⌊ n − 1 ⌋ + 2 for all n ≥ 2 and the equality holds if n is the square of a prime power. Let q be a prime power. In this paper, we first construct a graph Γ q on q 2 − 1 vertices without C 4 by using the Galois field F q , and then we prove that R ( C 4 , K 1 , ( q − 1 ) 2 + t ) = ( q − 1 ) 2 + q + t for q ≥ 4 is even and t = 1 , 0 , − 2 , and R ( C 4 , K 1 , q ( q − 1 ) − t ) = q 2 − t for q ≥ 5 is odd and t = 2 , 4 , . . . , 2 ⌈ q 4 ⌉ .

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Minjia Shi, Liqin Qian, Lin Sok, Nuh Aydin, Patrick Solé We first define a new Gray map from R = Z 4 + u Z 4 to Z 4 2 , where u 2 = 1 and study ( 1 + 2 u ) -constacyclic codes over R. Also of interest are some properties of ( 1 + 2 u ) -constacyclic codes over R. Considering their Z 4 images, we prove that the Gray images of ( 1 + 2 u ) -constacyclic codes of length n over R are cyclic codes of length 2n over Z 4 . In many cases the latter codes have better parameters than those in the online database of Aydin and Asamov. We also give a corrected version of a table of new cyclic R-codes published by Özen et al. [7].

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Hai Q. Dinh, Bac T. Nguyen, Songsak Sriboonchitta Finite commutative semi-simple rings are direct sum of finite fields. In this study, we investigate the algebraic structure of λ-constacyclic codes over such finite semi-simple rings. Among others, necessary and sufficient conditions for the existence of self-dual, LCD, and Hermitian dual-containing λ-constacyclic codes over finite semi-simple rings are provided. Using the CSS and Hermitian constructions, quantum MDS codes over finite semi-simple rings are constructed.

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Nastja Cepak, Pascale Charpin, Enes Pasalic We show that many infinite classes of permutations over finite fields can be constructed via translators with a large choice of parameters. We first characterize some functions having linear translators, based on which several families of permutations are then derived. Extending the results of [9], we give in several cases the compositional inverse of these permutations. The connection with complete permutations is also utilized to provide further infinite classes of permutations. Moreover, we propose new tools to study permutations of the form x ↦ x + ( x p m − x + δ ) s and a few infinite classes of permutations of this form are proposed.

Abstract: Publication date: May 2017 Source:Finite Fields and Their Applications, Volume 45 Author(s): Zhengbang Zha, Lei Hu, Shuqin Fan Permutation trinomials of the form x r h ( x 2 m − 1 ) over F 2 2 m are investigated in this paper, which is a further study on a recent work of Gupta and Sharma. Based on some bijections over the unit circle of F 2 2 m with order 2 m + 1 , the two conjectures proposed by Gupta and Sharma are confirmed and several new permutation trinomials are presented.

Abstract: Publication date: March 2017 Source:Finite Fields and Their Applications, Volume 44 Author(s): Megumi Asada, Eva Fourakis, Sarah Manski, Nathan McNew, Steven J. Miller, Gwyneth Moreland Several recent papers have considered the Ramsey-theoretic problem of how large a subset of integers can be without containing any 3-term geometric progressions. This problem has also recently been generalized to number fields, determining bounds on the greatest possible density of ideals avoiding geometric progressions. We study the analogous problem over F q [ x ] , first constructing a set greedily which avoids these progressions and calculating its density, and then considering bounds on the upper density of subsets of F q [ x ] which avoid 3-term geometric progressions. This new setting gives us a parameter q to vary and study how our bounds converge to 1 as it changes, and positive characteristic introduces some extra combinatorial structure that increases the tractability of common questions in this area.

Abstract: Publication date: March 2017 Source:Finite Fields and Their Applications, Volume 44 Author(s): Cícero Carvalho, Victor G.L. Neumann In this paper we determine many values of the second least weight of codewords, also known as the next-to-minimal Hamming weight, for a type of affine variety codes, obtained by evaluating polynomials of degree up to d on the points of a cartesian product of n subsets of a finite field F q . Such codes firstly appeared in a work by O. Geil and C. Thomsen (see [12]) as a special case of the so-called weighted Reed–Muller codes, and later appeared independently in a work by H. López, C. Rentería-Marquez and R. Villarreal (see [16]) named as affine cartesian codes. Our work extends, to affine cartesian codes, the results obtained by Rolland in [17] for generalized Reed–Muller codes.

Abstract: Publication date: March 2017 Source:Finite Fields and Their Applications, Volume 44 Author(s): Gábor Korchmáros, Pietro Speziali Hermitian functional and differential codes defined over divisors with strong combinatorial and algebraic properties have often good performance. Here, those arising from the 2-transitive orbit of PGL ( 2 , q ) on the Hermitian curve are investigated. In several cases, such codes have better minimum distance compared with the Goppa lower bound. Results on their automorphism groups are also given.

Abstract: Publication date: March 2017 Source:Finite Fields and Their Applications, Volume 44 Author(s): Adel N. Alahmadi, David G. Glynn Many important graphs are bipartite and cubic (i.e. bipartite and trivalent, or “bicubic”). We explain concisely how the Hamilton cycles of this type of graph are characterized by a single determinantal condition over GF ( 2 ) . Thus algebra may be used to derive results such as those of Bosák, Kotzig, and Tutte that were originally proved differently.

Abstract: Publication date: March 2017 Source:Finite Fields and Their Applications, Volume 44 Author(s): Igor E. Shparlinski, Andreas J. Weingartner Given a polynomial g of positive degree over a finite field, we show that the proportion of polynomials of degree n, which can be written as h + g k , where h is an irreducible polynomial of degree n and k is a nonnegative integer, has order of magnitude 1 / deg g .

Abstract: Publication date: March 2017 Source:Finite Fields and Their Applications, Volume 44 Author(s): Kenneth A. Ward We determine the representation of the Galois group for the cyclotomic function fields in characteristic p > 0 induced by the natural action on the space of holomorphic differentials via construction of an explicit canonical basis of differentials. This includes those cases which present wild ramification and finite automorphism groups with non-cyclic p-part, which have remained elusive. We also obtain information on the gap sequences of ramified primes and extend these results to rank one Drinfel'd modules.

Abstract: Publication date: March 2017 Source:Finite Fields and Their Applications, Volume 44 Author(s): Myriam Maldonado-Ramírez, Martha Rzedowski-Calderón, Gabriel Villa-Salvador Let k be a rational congruence function field and consider a finite separable extension K / k . We consider the extension K / k satisfying the following condition. For each prime in k at least one prime in K above it is tamely ramified. Then, except for constants, we find the genus field K g e of K / k . In general, we describe the genus field of a global function field. We present some applications and examples of the main results.

Abstract: Publication date: March 2017 Source:Finite Fields and Their Applications, Volume 44 Author(s): Shudi Yang, Zheng-An Yao, Chang-An Zhao Cyclic codes have attracted a lot of research interest for decades as they have efficient encoding and decoding algorithms. In this paper, for an odd prime p, we investigate two classes of p-ary cyclic codes for special cases and determine their weight distributions explicitly. The results show that both codes have at most five nonzero weights.

Abstract: Publication date: March 2017 Source:Finite Fields and Their Applications, Volume 44 Author(s): Libo Wang, Baofeng Wu, Zhuojun Liu In this paper, some classes of permutation polynomials of the form ( x p m − x + δ ) s + L ( x ) over the finite field F p 2 m are investigated by determining the number of solutions of certain equations, where L ( x ) = x or x p m + x . More precisely, for an integer s satisfying s ( p m + 1 ) ≡ p m + 1 (mod p 2 m − 1 ), we give four classes of permutation polynomials of the form ( x 2 m + x + δ ) s + x over F 2 2 m , and five classes of permutation polynomials of the form ( x 3 m − x + δ ) s + x 3 m + x over F 3 2 m , respectively.