Search

After a brief review of existing results on permutation binomials of finite fields, we introduce the notion of equivalence among permutation binomials (PBs) and describe how to bring a PB to its canonical form under equivalence. We then focus on PBs of $\Bbb F_{q^2}$ of the form $X^n(X^{d(q-1)}+a)$, where $n$ and $d$ are positive integers and $a\in\Bbb F_{q^2}^*$. Our contributions include two nonexistence results: (1) If $q$ is even and sufficiently large and $a^{q+1}\ne 1$, then $X^n(X^{3(q-1)}+a)$ is not a PB of $\Bbb F_{q^2}$. (2) If $2\le d\mid q+1$, $q$ is sufficiently large and $a^{q+1}\ne 1$, then $X^n(X^{d(q-1)}+a)$ is not a PB of $\Bbb F_{q^2}$ under certain additional conditions. (1) partially confirms a recent conjecture by Tu et al. (2) is an extension of a previous result with $n=1$., Comment: 26 pages

Let ${R}_{q}({r},{n})$ be the ${r}$ th order ${q}$ -ary Reed-Muller code of length ${q}^{n}$ , which is the set of functions from ${\mathbb {F}}_{q}^{n}$ to ${\mathbb {F}}_{q}$ represented by polynomials of degree $\le {r}$ in ${\mathbb {F}}_{q}[{X}_{1}, {\dots },{X}_{n}]$ . The affine linear group $AGL({n},{\mathbb {F}}_{q})$ acts naturally on ${R}_{q}({r},{n})$ . We derive two formulas concerning the number of orbits of this action: (i) an explicit formula for the number of AGL orbits of ${R}_{q}({n}({q}-1),{n})$ , and (ii) an asymptotic formula for the number of AGL orbits of ${R}_{2}({n},{n})/{R}_{2}(1,{n})$ . The number of AGL orbits of ${R}_{2}({n},{n})$ has been numerically computed by several authors for ${n}\le 31$ ; the binary case of result (i) is a theoretic solution to the question. Result (ii) answers a question by MacWilliams and Sloane.

Let Fq(x) be the field of rational functions over Fq and treat PGL(2,Fq) as the group of degree one rational functions in Fq(x) equipped with composition. PGL(2,Fq) acts on Fq(x) from the r...

Recently, rational functions of degree three that permute the projective line $\Bbb P^1(\Bbb F_q)$ over a finite field $ \Bbb F_q$ were determined by Ferraguti and Micheli. In the present paper, using a different method, we determine all rational functions of degree four that permute the $\Bbb P^1(\Bbb F_q)$., 12 pages. Sporadic PRs with small q's are determines. Typos in v1 are corrected

A formula discovered by L. Carlitz in 1935 finds an interesting application in permutation rational functions of finite fields. It allows us to determine all rational functions of degree three that permute the projective line $\Bbb P^1(\Bbb F_q)$ over $\Bbb F_q$, a result previously obtained by Ferraguti and Micheli through a different method. It also allows us to determine all rational functions of degree four that permute $\Bbb P^1(\Bbb F_q)$ under a certain condition. (A complete determination of all rational functions of degree four that permute $\Bbb P^1(\Bbb F_q)$ without any condition will appear in a separate forthcoming paper.), 13 pages

Let $p$ be a prime and $n$ be a positive integer, and consider $f_b(X)=X+(X^p-X+b)^{-1}\in \Bbb F_p(X)$, where $b\in\Bbb F_{p^n}$ is such that $\text{Tr}_{p^n/p}(b)\ne 0$. It is known that (i) $f_b$ permutes $\Bbb F_{p^n}$ for $p=2,3$ and all $n\ge 1$; (ii) for $p>3$ and $n=2$, $f_b$ permutes $\Bbb F_{p^2}$ if and only if $\text{Tr}_{p^2/p}(b)=\pm 1$; and (iii) for $p>3$ and $n\ge 5$, $f_b$ does not permute $\Bbb F_{p^n}$. It has been conjectured that for $p>3$ and $n=3,4$, $f_b$ does not permute $\Bbb F_{p^n}$. We prove this conjecture for sufficiently large $p$., 13 pages

Riemann's hypothesis on function fields over a finite field implies the Hasse–Weil bound for the number of zeros of an absolutely irreducible bi-variate polynomial over a finite field. The Hasse–Weil bound has extensive applications in the arithmetic of finite fields. In this paper, we use the Hasse–Weil bound to prove two results on permutation polynomials over F q where q is sufficiently large. To facilitate these applications, the absolute irreducibility of certain polynomials in F q [ X , Y ] is established.

In 2007, Dmytrenko, Lazebnik and Williford posed two related conjectures about polynomials over finite fields. Conjecture 1 is a claim about the uniqueness of certain monomial graphs. Conjecture 2 , which implies Conjecture 1 , deals with certain permutation polynomials of finite fields. Two natural strengthenings of Conjecture 2 , referred to as Conjecture A , Conjecture B in the present paper, were also insinuated. In a recent development, Conjecture 2 and hence Conjecture 1 have been confirmed. The present paper gives a proof of Conjecture A .

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.

Problems and their solutions of the Fifth International Students? Olympiad in cryptography NSUCRYPTO?2018 are presented. We consider problems related to attacks on ciphers and hash functions, Boolean functions, quantum circuits, Enigma, etc. We discuss several open problems on orthogonal arrays, Sylvester matrices, and disjunct matrices. The problem of existing an invertible Sylvester matrix whose inverse is again a Sylvester matrix was completely solved during the Olympiad.

Let q be a power of 2. Recently, Tu and Zeng considered trinomials of the form f ( X ) = X + a X ( 1 ∕ 4 ) q 2 ( q − 1 ) + b X ( 3 ∕ 4 ) q 2 ( q − 1 ) , where a , b ∈ F q 2 ∗ . They proved that f is a permutation polynomial of F q 2 if b = a 2 − q and X 3 + X + a − 1 − q has no root in F q . In this paper, we show that the above sufficient condition is also necessary.

Let AGL ( 1 , F q ) denote the affine linear group of dimension one over the finite field F q . We determine the Mobius function of the lattice of subgroups of AGL ( 1 , F q ) .

Let $p$ be a prime and $n$ be a positive integer. Let $f_b(X)=X+(X^p-X+b)^{-1}$, where $b\in\Bbb F_{p^n}$ is such that $\text{Tr}_{p^n/p}(b)\ne 0$. In 2008, Yuan et al. \cite{Yuan-Ding-Wang-Pieprzyk-FFA-2008} showed that for $p=2,3$, $f_b$ permutes $\Bbb F_{p^n}$ for all $n\ge 1$. Using the Hasse-Weil bound, we show that when $p>3$ and $n\ge 5$, $f$ does not permute $\Bbb F_{p^n}$. For $p>3$ and $n=2$, we prove that $f_b$ permutes $\Bbb F_{p^2}$ if and only if $\text{Tr}_{p^2/p}(b)=\pm 1$. We conjecture that for $p>3$ and $n=3,4$, $f_b$ does not permute $\Bbb F_{p^n}$., 7 pages

Let F q be a finite field with char F q = p and n > 0 an integer with gcd ( n , log p ⁡ q ) = 1 . Let ( ) ⁎ : F q ( x 0 , … , x n − 1 ) → F q ( x 0 , … , x n − 1 ) be the F q -monomorphism defined by x i ⁎ = x i + 1 for 0 ≤ i n − 1 and x n − 1 ⁎ = x 0 q . For f , g ∈ F q ( x 0 , … , x n − 1 ) ∖ F q , define f ∘ g = f ( g , g ⁎ , … , g ( n − 1 ) ⁎ ) . Then ( F q ( x 0 , … , x n − 1 ) ∖ F q , ∘ ) is a monoid whose invertible elements are called global P -forms. Global P -forms were first introduced by H. Dobbertin in 2001 with q = 2 to study a certain type of permutation polynomials of F 2 m with gcd ( m , n ) = 1 ; global P -forms with q = p for an arbitrary prime p were considered by W. More in 2005. In this paper, we discuss some fundamental questions about global P -forms, some of which are answered and others remain open.

Let r be a prime power and q = r m . For 0 ≤ i ≤ m − 1 , let f i ∈ F r [ X ] be q-linearized and a i ∈ F q . Assume that z ∈ F ‾ r satisfies the equation ∑ i = 0 m − 1 a i f i ( z ) r i = 0 , where ∑ i = 0 m − 1 a i f i r i ∈ F q [ X ] is an r-linearized polynomial. It is shown that z satisfies a q-linearized polynomial equation with coefficients in F r . This result provides an explanation for numerous permutation polynomials previously obtained through computer search.

Constructions of permutation polynomials over finite fields have attracted much interests in recent years, especially those with few terms, such as trinomials, due to their simple form and additional properties. In this paper, we construct several classes of permutation trinomials over F p 2 k with Niho exponents of the form f ( x ) = x + λ 1 x s ( p k − 1 ) + 1 + λ 2 x t ( p k − 1 ) + 1 ; some necessary and sufficient conditions for the polynomial f ( x ) to permute F p 2 k are provided. Specifically, for p = 5 , new permutation trinomials are presented. We also give recursive constructions of permutation polynomials using self-reciprocal polynomials.

Let $f(X)=X(1+aX^{q(q-1)}+bX^{2(q-1)})\in\Bbb F_{q^2}[X]$, where $a,b\in\Bbb F_{q^2}^*$. In a series of recent papers by several authors, sufficient conditions on $a$ and $b$ were found for $f$ to be a permutation polynomial (PP) of $\Bbb F_{q^2}$ and, in characteristic $2$, the sufficient conditions were shown to be necessary. In the present paper, we confirm that in characteristic 3, the sufficient conditions are also necessary. More precisely, we show that when $\text{char}\,\Bbb F_q=3$, $f$ is a PP of $\Bbb F_{q^2}$ if and only if $(ab)^q=a(b^{q+1}-a^{q+1})$ and $1-(b/a)^{q+1}$ is a square in $\Bbb F_q^*$., 31 pages

Let n be a positive integer, q = 2 n , and let F q be the finite field with q elements. For each positive integer m, let D m ( X ) be the Dickson polynomial of the first kind of degree m with parameter 1. Assume that m > 1 is a divisor of q + 1 . We study the existence of α ∈ F q ⁎ such that D m ( α ) = D m ( α − 1 ) = 0 . We also explore the connections of this question to an open question by Wiedemann and a game called “Button Madness”.

Recently, Tu, Zeng, Li, and Helleseth considered trinomials of the form $f(X)=X+aX^{q(q-1)+ 1}+bX^{2(q-1)+ 1}\in \mathbb {F}_{q^{2}}[X]$, where q is even and $a,b\in \mathbb {F}_{q^{2}}^{*}$. They found sufficient conditions on a, b for f to be a permutation polynomial (PP) of $\mathbb {F}_{q^{2}}$ and they conjectured that the sufficient conditions are also necessary. The conjecture has been confirmed by Bartoli using the Hasse-Weil bound. In this paper, we give an alternative solution to the question. We also use the Hasse-Weil bound, but in a different way. Moreover, the necessity and sufficiency of the conditions are proved by the same approach.

Permutation polynomials over finite fields constitute an active research area in which advances are being made constantly. We survey the contributions made to this area in recent years. Emphasis is placed on significant results and novel methods.

Let f = a x + x 3 q − 2 ∈ F q 2 [ x ] , where a ∈ F q 2 ⁎ . We prove that f is a permutation polynomial of F q 2 if and only if one of the following occurs: (i) q = 2 e , e odd, and a q + 1 3 is a primitive 3rd root of unity. (ii) ( q , a ) belongs to a finite set which is determined in the paper.

Let $\text{AGL}(1,\Bbb F_q)$ be the affine linear group of dimension $1$ over a finite field $\Bbb F_q$. $\text{AGL}(1,\Bbb F_q)$ acts sharply 2-transitively on $\Bbb F_q$. Given $S, Comment: 19 pages plus a very long table

Let p be a prime and q=p^s. For integer a>=0, let S"a=x+x^q+...+x^q^^^a^^^-^^^[email protected]?F"p[x]. We present three constructions of permutation polynomials of F"q"^"e involving S"a which generalize several recent results. When q is even, the third construction produces a large class of Dembowski-Ostrom permutation polynomials. We also discuss an interesting linear algebraic problem arising from the third construction.

Let $f=a{\tt x} +b{\tt x}^q+{\tt x}^{2q-1}\in\Bbb F_q[{\tt x}]$. We find explicit conditions on $a$ and $b$ that are necessary and sufficient for $f$ to be a permutation polynomial of $\Bbb F_{q^2}$. This result allows us to solve a related problem. Let $g_{n,q}\in\Bbb F_p[{\tt x}]$ ($n\ge 0$, $p=\text{char}\,\Bbb F_q$) be the polynomial defined by the functional equation $\sum_{c\in\Bbb F_q}({\tt x}+c)^n=g_{n,q}({\tt x}^q-{\tt x})$. We determine all $n$ of the form $n=q^\alpha-q^\beta-1$, $\alpha>\beta\ge 0$, for which $g_{n,q}$ is a permutation polynomial of $\Bbb F_{q^2}$., Comment: 28 pages

Let p be an odd prime. We classify all self dual quadratic bent functions from F p n to F p under the action of the orthogonal group O ( n , F p ) . The sizes of the O ( n , F p ) -orbits of such self dual bent functions are explicitly determined. These results are obtained through the following steps: 1. n × n symmetric matrices A over F p satisfying A 2 = c I ( c ∈ F p ⁎ ) are classified under the conjugation by O ( n , F p ) . 2. For each representative A in step 1, the orbits of ker ( A − I ) under the action of cent O ( n , F p ) ( A ) are determined. 3. The sizes of the orbits in steps 1 and 2 are computed.

Let $f\in\Bbb F_q[X_1,\dots,X_n]$ with $°f=d>0$ and let $Z(f)=\{(x_1,\dots,x_n)\in \Bbb F_q^n: f(x_1,\dots,x_n)=0\}$. Ax's theorem states that $|Z(f)|\equiv 0\pmod {q^{\lceil n/d\rceil-1}}$, that is, $\nu_p(|Z(f)|)\ge m(\lceil n/d\rceil-1)$, where $p=\text{char}\,\Bbb F_q$, $q=p^m$, and $\nu_p$ is the $p$-adic valuation. In this paper, we determine a condition on the coefficients of $f$ that is necessary and sufficient for $f$ to meet Ax's bound, that is, $\nu_p(|Z(f)|)=m(\lceil n/d\rceil-1)$. Let $R_q(d,n)$ denote the $q$-ary Reed-Muller code $\{f\in\Bbb F_q[X_1,\dots,X_n]: °f\le d,\ °_{X_j}f\le q-1,\ 1\le j\le n\}$, and let $N_q(d,n;t)$ be the number of codewords of $R_q(d,n)$ with weight divisible by $p^t$. As applications of the aforementioned result, we find explicit formulas for $N_q(d,n;t)$ in the following cases: (i) $q=2^m$, $n$ even, $d=n/2$, $t=m+1$; (ii) $q=2$, $n/2\le d\le n-2$, $t=2$; (iii) $q=3^m$, $d=n$, $t=1$; (iv) $q=3$, $n\le d\le 2n$, $t=1$.

We describe a piecewise construction of permutation polynomials over a finite field F q which uses a subgroup of F q ⁎ , a “selection” function, and several “case” functions. Permutation polynomials obtained by this construction unify and generalize several recently discovered families of permutation polynomials.

Let p be a prime and q=pκ. We study the permutation properties of the polynomial gn,q∈Fp[x] defined by the functional equation ∑a∈Fq(x+a)n=gn,q(xq−x). The polynomial gn,q is a q-ary version of the reversed Dickson polynomial in characteristic 2. We are interested in the parameters (n,e;q) for which gn,q is a permutation polynomial (PP) of Fqe. We find several families of such parameters and obtain various necessary conditions on such parameters. Initial results, both theoretical and numerical, indicate that the class gn,q contains an abundance of PPs over finite fields, many of which are yet to be explained and understood.

We classify all self dual and anti self dual quadratic bent functions in 2n variables under the action of the orthogonal group $${{O}(2n,\mathbb F_2)}$$ . This is done through a classification of all 2n × 2n involutory alternating matrices over $${\mathbb F_2}$$ under the action of the orthogonal group. The sizes of the $${{O}(2n,\mathbb F_2)}$$ -orbits of self dual and anti self dual quadratic bent functions are determined explicitly.

Let @a,@b@?F"q"^"t^* and let N"t(@a,@b) denote the number of solutions (x,y)@?F"q"^"t^*xF"q"^"t^* of the equation x^q^-^1+@ay^q^-^1=@b. Recently, Moisio determined N"2(@a,@b) and evaluated N"3(@a,@b) in terms of the number of rational points on a projective cubic curve over F"q. We show that N"t(@a,@b) can be expressed in terms of the number of monic irreducible polynomials f@?F"q[x] of degree r such that f(0)=a and f(1)=b, where r|t and a,b@?F"q^* are related to @a,@b. Let I"r(a,b) denote the number of such polynomials. We prove that I"r(a,b)>0 when r>=3. We also show that N"3(@a,@b) can be expressed in terms of the number of monic irreducible cubic polynomials over F"q with certain prescribed trace and norm.

We discuss several enumerative results for irreducible polynomials of a given degree and pairs of relatively prime polynomials of given degrees in several variables over finite fields. Two notions of degree, the {\em total degree} and the {\em vector degree}, are considered. We show that the number of irreducibles can be computed recursively by degree and that the number of relatively prime pairs can be expressed in terms of the number of irreducibles. We also obtain asymptotic formulas for the number of irreducibles and the number of relatively prime pairs. The asymptotic formulas for the number of irreducibles generalize and improve several previous results by Carlitz, Cohen and Bodin., Comment: 33 pages

Let be the set of all subspaces of . The following three groups act on : (i) the symmetric group on the coordinate positions of ; (ii) the group of monomial transformations of ; (iii) the group of semi-linear monomial transformations of . The orbits of under these actions are the equivalence classes of linear codes in under three notions of equivalence: permutation equivalence, monomial equivalence and equivalence. Let , , N n,q Γ denote the numbers of the orbits under the three actions on respectively. It was recently proved that as n → ∞, and . In this article, we show that , where q = pr and p is a prime.

Derivatives of a solution of an ODE Cauchy problem can be computed inductively using the Faa di Bruno formula. In this paper, we exhibit a noninductive formula for these derivatives. At the heart of this formula is a combinatorial problem, which is solved in this paper. We also give a more tractable form of the Magnus expansion for the solution of a homogeneous linear ODE.

Coulter-Matthews (CM) bent functions are from F"3"^"n to F"3 defined by Tr(ax^1^2^(^3^^^@a^+^1^)), where a@?F"3"^"n^* and (@a,2n)=1. It is not known if these bent functions are weakly regular in general. In this paper, we show that when n is even and @a=n+1 (or n-1), the CM bent function is weakly regular. Moreover, we explicitly determine the dual of the CM bent function in this case. The dual is a bent function not reported previously.

Let @J"n be the number of inequivalent self-dual codes in F"2^2^n. We prove that lim"n"->"~(2n)[email protected]^-^1^2^n^(^n^-^1^)@J"n=1, where @[email protected]?"j"="1^~(1+2^-^j)~2.38423. Let @D"n be the number of inequivalent doubly even self-dual codes in F"2^8^n. We also prove that lim"n"->"~(8n)[email protected]^-^2^n^(^4^n^-^3^)@D"n=1.

For a permutation f of an n-dimensional vector space V over a finite field of order q we let k-affinity(f) denote the number of k-flats X of V such that f(X) is also a k-flat. By k-spectrum(n,q) we mean the set of integers k-affinity(f) where f runs through all permutations of V. The problem of the complete determination of k-spectrum(n,q) seems very difficult except for small or special values of the parameters. However, we are able to establish that k-spectrum(n,q) contains 0 in the following cases: (i) q>2 and 02. The maximum of k-affinity(f) is, of course, obtained when f is any semi-affine mapping. We conjecture that the next to largest value of k-affinity(f) is when f is a transposition and we are able to prove this when q=2, k=2, n>2 and when q>2, k=1, n>1., Comment: 25 pages

Let Mn,q⊂GL(n,Fq) be the group of monomial matrices, i.e., the group generated by all permutation matrices and diagonal matrices in GL(n,Fq). The group Mn,q acts on the set V(Fqn) of all subspaces of Fqn. The number of orbits of this action, denoted by Nn,q, is the number of non-equivalent linear codes in Fqn. It was conjectured by Lax that Nn,q∼|V(Fqn)|n!(q-1)n-1 as n→∞. We confirm this conjecture in this paper.

Let $$S={\rm GR}(2^3, n)$$ be the Galois ring of characteristic 23 and rank n and let $$R=S[X]/(X^2,\,2X-4)$$ . We give an explicit construction of Hadamard difference sets in $$(R,+)\cong{\Bbb Z}_8^n\times{\Bbb Z}_2^n$$ .}

Let p be a prime and let r, e, m be positive integers such that r|e and e|m. Extended cyclic codes of length pm over Fpr which are invariant under AGL(m/e, Fpe) are characterized by a well-known relation le on the set {0, 1,...,pm - 1}. From the relation le, we derive a partial order ≺ in u = {0, 1,...,m/e(p - 1)}e defined by an e-dimensional simplicial cone. We show that the aforementioned extended cyclic codes can be enumerated by the ideals of (u, ≺) which are invariant under the rth power of a circulant permutation matrix. When e = 2, we enumerate all such invariant ideals by describing their boundaries. Explicit formulas are obtained for the total number of AGL(m/2, Fp2)- invariant extended cyclic codes of length pm over Fpr and for the dimensions of such codes. We also enumerate all self-dual AGL(m/2, F22)-invariant extended cyclic codes of length 2m over F22 where m/2 is odd; the restrictions on the parameters are necessary conditions for the existence of self-dual affine invariant extended cyclic codes with e = 2.

Let f"[email protected]?F"q[X"1,...,X"n] be polynomials of degree d"i, 1==...>=d"r>=1. Denote the set of zeros of f"i in F"q^n by Z(f"i). Katz proved that q^@?^n^-^d^"^1^-^...^-^d^"^r^d^"^1^@? divides |Z(f"1)@[email protected]?Z(f"r)|. A more elementary proof of this result was given by Wan. We found a new and much simpler proof of this result.

Using the Teichmüller character and Gauss sums, we obtain the following results concerning p-ary bent functions and q-ary resilient functions: (1) a characterization of certain q-ary resilient functions in terms of their coefficients; (2) stronger upper bounds for the degree of p-ary bent functions; (3) determination of all bent functions on Fp; (4) a characterization of ternary weakly regular bent functions in terms of their coefficients.

A longstanding conjecture by Niho on the maximally nonlinearity of certain power functions was proved recently by Hollmann and Xiang using a result of Dobbertin on the almost perfect nonlinearity of the Niho power functions. A key ingredient of the proof, a bound for certain binary weights, was obtained using a computer. In this note, we provide a noncomputer proof for the bound of the binary weights.

A problem posed by S. Payne calls for determination of all linearized polynomials f(x) ∈ F 2 n [x] such that f(x) and f(x)/x are permutations of F 2 n and F* 2 n respectively. We show that such polynomials are exactly of the form f(x) = ax 2k with a ∈ F* 2 n and (k, n) = 1. In fact, we solve a q-ary version of Payne's problem.

Let Gn,t be the subgroup of GL(n,ℤ2) that stabilizes {xℤ2n:|x|≤t}. We determine Gn,t explicitly: For 1≤t≤n−2, Gn,t=Sn when t is odd and Gn,t=〈Sn,Δ〉 when t is even, where Sn