Computing Explicit Isomorphisms with Full Matrix Algebras over $$\mathbb {F}_q(x)$$

We propose a polynomial time f-algorithm (a deterministic algorithm which uses an oracle for factoring univariate polynomials over \(\mathbb {F}_q\)) for computing an isomorphism (if there is any) of a finite-dimensional \(\mathbb {F}_q(x)\)-algebra \(\mathcal{A}\) given by structure constants with the algebra of n by n matrices with entries from \(\mathbb {F}_q(x)\). The method is based on computing a finite \(\mathbb {F}_q\)-subalgebra of \(\mathcal{A}\) which is the intersection of a maximal \(\mathbb {F}_q[x]\)-order and a maximal R-order, where R is the subring of \(\mathbb {F}_q(x)\) consisting of fractions of polynomials with denominator having degree not less than that of the numerator.     

The primitive idempotents and weight distributions of irreducible constacyclic codes

Let \({\mathbb {F}}_q\) be a finite field with q elements such that \(l^v||(q^t-1)\) and \(\gcd (l,q(q-1))=1\), where l, t are primes and v is a positive integer. In this paper, we give all primitive idempotents in a ring \(\mathbb F_q[x]/\langle x^{l^m}-a\rangle \) for \(a\in {\mathbb {F}}_q^*\). Specially for \(t=2\), we give the weight distributions of all irreducible constacyclic codes and their dual codes of length \(l^m\) over \({\mathbb {F}}_q\).     

On kernels and nuclei of rank metric codes

For each rank metric code \(\mathcal {C}\subseteq \mathbb {K}^{m\times n}\), we associate a translation structure, the kernel of which is shown to be invariant with respect to the equivalence on rank metric codes. When \(\mathcal {C}\) is \(\mathbb {K}\)-linear, we also propose and investigate other two invariants called its middle nucleus and right nucleus. When \(\mathbb {K}\) is a finite field \(\mathbb {F}_q\) and \(\mathcal {C}\) is a maximum rank distance code with minimum distance \(d<\min \{m,n\}\) or \(\gcd (m,n)=1\), the kernel of the associated translation structure is proved to be \(\mathbb {F}_q\). Furthermore, we also show that the middle nucleus of a linear maximum rank distance code over \(\mathbb {F}_q\) must be a finite field; its right nucleus also has to be a finite field under the condition \(\max \{d,m-d+2\} \geqslant \left\lfloor \frac{n}{2} \right\rfloor +1\). Let \(\mathcal {D}\) be the DHO-set associated with a bilinear dimensional dual hyperoval over \(\mathbb {F}_2\). The set \(\mathcal {D}\) gives rise to a linear rank metric code, and we show that its kernel and right nucleus are isomorphic to \(\mathbb {F}_2\). Also, its middle nucleus must be a finite field containing \(\mathbb {F}_q\). Moreover, we also consider the kernel and the nuclei of \(\mathcal {D}^k\) where k is a Knuth operation.     

Categorical crepant resolutions for quotient singularities

Let \(\mathbb {F}_q\) be a finite field and \(\beta \) a Pisot or Salem unit series in \( \mathbb {F}_q((X^{-1}))\). The aim of this paper is to prove that the \(\beta \)-expansion of any rational element in the unit disk D(0, 1) is purely periodic. No similar result exist in the real case.     

Lattices from codes over $$\mathbb {Z}_q$$: generalization of constructions D, $$ D'$$ D′ and $$\overline{ D}$$ D¯

In this paper, we extend the lattice Constructions D, \(D'\) and \(\overline{D}\) (this latter is also known as Forney’s code formula) from codes over \(\mathbb {F}_p\) to linear codes over \(\mathbb {Z}_q\), where \(q \in \mathbb {N}\). We define an operation in \(\mathbb {Z}_q^n\) called zero-one addition, which coincides with the Schur product when restricted to \(\mathbb {Z}_2^n\) and show that the extended Construction \(\overline{D}\) produces a lattice if and only if the nested codes are closed under this addition. A generalization to the real case of the recently developed Construction \(A'\) is also derived and we show that this construction produces a lattice if and only if the corresponding code over \(\mathbb {Z}_q[X]/X^a\) is closed under a shifted zero-one addition. One of the motivations for this work is the recent use of q-ary lattices in cryptography.     

The cohomology of orbit spaces of certain free circle group actions

Suppose that \(G =\mathbb{S}^1\) acts freely on a finitistic space X whose (mod p) cohomology ring is isomorphic to that of a lens space \(L^{2m-1}(p;q_1,\ldots,q_m)\) or \(\mathbb{S}^1\times \mathbb{C}P^{m-1}\). The mod p index of the action is defined to be the largest integer n such that α ⁿ ?≠?0, where \(\alpha \,\epsilon\, H^2(X/G;\mathbb{Z}_p)\) is the nonzero characteristic class of the \(\mathbb{S}^1\)-bundle \(\mathbb{S}^1\hookrightarrow X\rightarrow X/G\). We show that the mod p index of a free action of G on \(\mathbb{S}^1\times \mathbb{C}P^{m-1}\) is p???1, when it is defined. Using this, we obtain a Borsuk–Ulam type theorem for a free G-action on \(\mathbb{S}^1\times \mathbb{C}P^{m-1}\). It is note worthy that the mod p index for free G-actions on the cohomology lens space is not defined.     

Complete mappings and Carlitz rank

The well-known Chowla and Zassenhaus conjecture, proven by Cohen in 1990, states that for any \(d\ge 2\) and any prime \(p>(d^2-3d+4)^2\) there is no complete mapping polynomial in \(\mathbb {F}_p[x]\) of degree d. For arbitrary finite fields \(\mathbb {F}_q\), we give a similar result in terms of the Carlitz rank of a permutation polynomial rather than its degree. We prove that if \(n<\lfloor q/2\rfloor \), then there is no complete mapping in \(\mathbb {F}_q[x]\) of Carlitz rank n of small linearity. We also determine how far permutation polynomials f of Carlitz rank \(n<\lfloor q/2\rfloor \) are from being complete, by studying value sets of \(f+x.\) We provide examples of complete mappings if \(n=\lfloor q/2\rfloor \), which shows that the above bound cannot be improved in general.     

Explicit factorizations of cyclotomic polynomials over finite fields

Let q be a prime power and let \({\mathbb {F}}_q\) be a finite field with q elements. This paper discusses the explicit factorizations of cyclotomic polynomials over \(\mathbb {F}_q\). Previously, it has been shown that to obtain the factorizations of the \(2^{n}r\)th cyclotomic polynomials, one only need to solve the factorizations of a finite number of cyclotomic polynomials. This paper shows that with an additional condition that \(q\equiv 1 \pmod p\), the result can be generalized to the \(p^{n}r\)th cyclotomic polynomials, where p is an arbitrary odd prime. Applying this result we discuss the factorization of cyclotomic polynomials over finite fields. As examples we give the explicit factorizations of the \(3^{n}\)th, \(3^{n}5\)th and \(3^{n}7\)th cyclotomic polynomials.     

Sets with even partition functions and 2-adic integers

For P ? \(\mathbb{F}_2 \)[z] with _P(0) = 1 and deg(_P) ≥ 1, let \(\mathcal{A}\) = \(\mathcal{A}\)(P) (cf. [4], [5], [13]) be the unique subset of ? such that Σ _n≥0 p(\(\mathcal{A}\), n)z ⁿ ≡ P(z) (mod 2), where p(\(\mathcal{A}\), n) is the number of partitions of n with parts in \(\mathcal{A}\). Let p be an odd prime and P ? \(\mathbb{F}_2 \)[z] be some irreducible polynomial of order p, i.e., p is the smallest positive integer such that P(z) divides 1 + z ^p in \(\mathbb{F}_2 \)[z]. In this paper, we prove that if m is an odd positive integer, the elements of \(\mathcal{A}\) = \(\mathcal{A}\)(P) of the form 2 ^k m are determined by the 2-adic expansion of some root of a polynomial with integer coefficients. This extends a result of F. Ben Saïd and J.-L. Nicolas [6] to all primes p.     

On the 2-adic valuation of the cardinality of elliptic curves over finite extensions of $$\mathbb {F}_{\varvec{q}} $$

In this paper we study the difference between the 2-adic valuations of the cardinalities \( \# E( \mathbb {F}_{q^k} ) \) and \( \# E( \mathbb {F}_q ) \) of an elliptic curve E over \( \mathbb {F}_q \). We also deduce information about the structure of the 2-Sylow subgroup \( E[ 2^\infty ]( \mathbb {F}_{q^k} ) \) from the exponents of \( E[ 2^\infty ]( \mathbb {F}_q ) \).     

On codes over $$\mathbb {F}_{q}+v\mathbb {F}_{q}+v^{2}\mathbb {F}_{q}$$

In this paper we investigate linear codes with complementary dual (LCD) codes and formally self-dual codes over the ring \(R=\mathbb {F}_{q}+v\mathbb {F}_{q}+v^{2}\mathbb {F}_{q}\), where \(v^{3}=v\), for q odd. We give conditions on the existence of LCD codes and present construction of formally self-dual codes over R. Further, we give bounds on the minimum distance of LCD codes over \(\mathbb {F}_q\) and extend these to codes over R.     

Idempotent and <Emphasis Type="Italic">p</Emphasis>-potent quadratic functions: distribution of nonlinearity and co-dimension

The Walsh transform \(\widehat{Q}\) of a quadratic function \(Q:{\mathbb F}_{p^n}\rightarrow {\mathbb F}_p\) satisfies \(|\widehat{Q}(b)| \in \{0,p^{\frac{n+s}{2}}\}\) for all \(b\in {\mathbb F}_{p^n}\), where \(0\le s\le n-1\) is an integer depending on Q. In this article, we study the following three classes of quadratic functions of wide interest. The class \(\mathcal {C}_1\) is defined for arbitrary n as \(\mathcal {C}_1 = \{Q(x) = \mathrm{Tr_n}(\sum _{i=1}^{\lfloor (n-1)/2\rfloor }a_ix^{2^i+1})\;:\; a_i \in {\mathbb F}_2\}\), and the larger class \(\mathcal {C}_2\) is defined for even n as \(\mathcal {C}_2 = \{Q(x) = \mathrm{Tr_n}(\sum _{i=1}^{(n/2)-1}a_ix^{2^i+1}) + \mathrm{Tr_{n/2}}(a_{n/2}x^{2^{n/2}+1}) \;:\; a_i \in {\mathbb F}_2\}\). For an odd prime p, the subclass \(\mathcal {D}\) of all p-ary quadratic functions is defined as \(\mathcal {D} = \{Q(x) = \mathrm{Tr_n}(\sum _{i=0}^{\lfloor n/2\rfloor }a_ix^{p^i+1})\;:\; a_i \in {\mathbb F}_p\}\). We determine the generating function for the distribution of the parameter s for \(\mathcal {C}_1, \mathcal {C}_2\) and \(\mathcal {D}\). As a consequence we completely describe the distribution of the nonlinearity for the rotation symmetric quadratic Boolean functions, and in the case \(p > 2\), the distribution of the co-dimension for the rotation symmetric quadratic p-ary functions, which have been attracting considerable attention recently. Our results also facilitate obtaining closed formulas for the number of such quadratic functions with prescribed s for small values of s, and hence extend earlier results on this topic. We also present the complete weight distribution of the subcodes of the second order Reed–Muller codes corresponding to \(\mathcal {C}_1\) and \(\mathcal {C}_2\) in terms of a generating function.     

Maximum scattered linear sets and MRD-codes

The rank of a scattered \({\mathbb F}_q\)-linear set of \({{\mathrm{{PG}}}}(r-1,q^n)\), rn even, is at most rn / 2 as it was proved by Blokhuis and Lavrauw. Existence results and explicit constructions were given for infinitely many values of r, n, q (rn even) for scattered \({\mathbb F}_q\)-linear sets of rank rn / 2. In this paper, we prove that the bound rn / 2 is sharp also in the remaining open cases. Recently Sheekey proved that scattered \({\mathbb F}_q\)-linear sets of \({{\mathrm{{PG}}}}(1,q^n)\) of maximum rank n yield \({\mathbb F}_q\)-linear MRD-codes with dimension 2n and minimum distance \(n-1\). We generalize this result and show that scattered \({\mathbb F}_q\)-linear sets of \({{\mathrm{{PG}}}}(r-1,q^n)\) of maximum rank rn / 2 yield \({\mathbb F}_q\)-linear MRD-codes with dimension rn and minimum distance \(n-1\).     

Improved elliptic curve hashing and point representation

For a large class of functions \(f:\mathbb {F}_q\rightarrow E(\mathbb {F}_q)\) to the group of points of an elliptic curve \(E/\mathbb {F}_q\) (typically obtained from certain algebraic correspondences between E and \(\mathbb {P}^1\)), Farashahi et al. (Math Comput 82(281):491–512, 2013) established that the map \((u,v)\mapsto f(u)+f(v)\) is regular, in the sense that for a uniformly random choice of \((u,v)\in \mathbb {F}_q^2\), the elliptic curve point \(f(u)+f(v)\) is close to uniformly distributed in \(E(\mathbb {F}_q)\). This result has several applications in cryptography, mainly to the construction of elliptic curve-valued hash functions and to the “Elligator Squared” technique by Tibouchi (in: Christin and Safavi-Naini (eds) Financial cryptography. LNCS, vol 8437, pp 139–156. Springer, Heidelberg, 2014) for representating uniform points on elliptic curves as close to uniform bitstrings. In this paper, we improve upon Farashahi et al.’s character sum estimates in two ways: we show that regularity can also be obtained for a function of the form \((u,v)\mapsto f(u)+g(v)\) where g has a much smaller domain than \(\mathbb {F}_q\), and we prove that the functions f considered by Farashahi et al. also satisfy requisite bounds when restricted to large intervals inside \(\mathbb {F}_q\). These improved estimates can be used to obtain more efficient hash function constructions, as well as much shorter “Elligator Squared” bitstring representations.     

On some constacyclic codes over $$\mathbb {Z}_{4}\left[ u\right] /\left\langle u^{2}-1\right\rangle $$, their $$\mathbb {Z}_4$$Z4 images,and new codes

In this paper, we study \(\lambda \)-constacyclic codes over the ring \(R=\mathbb {Z}_4+u\mathbb {Z}_4\) where \(u^{2}=1\), for \(\lambda =3+2u\) and \(2+3u\). Two new Gray maps from R to \(\mathbb {Z}_4^{3}\) are defined with the goal of obtaining new linear codes over \(\mathbb {Z}_4\). The Gray images of \(\lambda \)-constacyclic codes over R are determined. We then conducted a computer search and obtained many \(\lambda \)-constacyclic codes over R whose \(\mathbb {Z}_4\)-images have better parameters than currently best-known linear codes over \(\mathbb {Z}_4\).     

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.     

New optical orthogonal signature pattern codes with maximum collision parameter 2 and weight 4

Optical orthogonal signature pattern codes (OOSPCs) play an important role in a novel type of optical code-division multiple-access network for 2-dimensional image transmission. There is a one-to-one correspondence between an \((m, n, w, \lambda )\)-OOSPC and a \((\lambda +1)\)-(mn, w, 1) packing design admitting an automorphism group isomorphic to \(\mathbb {Z}_m\times \mathbb {Z}_n\). In 2010, Sawa gave a construction of an (m, n, 4, 2)-OOSPC from a one-factor of Köhler graph of \(\mathbb {Z}_m\times \mathbb {Z}_n\) which contains a unique element of order 2. In this paper, we study the existence of one-factor of Köhler graph of \(\mathbb {Z}_m\times \mathbb {Z}_n\) having three elements of order 2. It is proved that there is a one-factor in the Köhler graph of \(\mathbb {Z}_{2^{\epsilon }p}\times \mathbb {Z}_{2^{\epsilon '}}\) relative to the Sylow 2-subgroup if there is an S-cyclic Steiner quadruple system of order 2p, where \(p\equiv 5\pmod {12}\) is a prime and \(1\le \epsilon ,\epsilon '\le 2\). Using this one-factor, we construct a strictly \(\mathbb {Z}_{2^{\epsilon }p}\times \mathbb {Z}_{2^{\epsilon '}}\)-invariant regular \(G^*(p,2^{\epsilon +\epsilon '},4,3)\) relative to the Sylow 2-subgroup. By using the known S-cyclic SQS(2p) and a recursive construction for strictly \(\mathbb {Z}_{m}\times \mathbb {Z}_{n}\)-invariant regular G-designs, we construct more strictly \(\mathbb {Z}_{m}\times \mathbb {Z}_{n}\)-invariant 3-(mn, 4, 1) packing designs. Consequently, there is an optimal \((2^{\epsilon }m,2^{\epsilon '}n,4,2)\)-OOSPC for any \(\epsilon ,\epsilon '\in \{0,1,2\}\) with \(\epsilon +\epsilon '>0\) and an optimal (6m, 6n, 4, 2)-OOSPC where m, n are odd integers whose all prime divisors from the set \(\{p\equiv 5\pmod {12}:p\) is a prime, \(p<\)1,500,000}.     

$$L^{p}$$-Norms a nd Mahler’s Measure of Poly nomials o n the n-Dime nsio nal Torus

We prove Nikol’skii type inequalities that, for polynomials on the n-dimensional torus \(\mathbb {T}^n\), relate the \(L^p\)-norm with the \(L^q\)-norm (with respect to the normalized Lebesgue measure and \(0 <p <q < \infty \)). Among other things, we show that \(C=\sqrt{q/p}\) is the best constant such that \(\Vert P\Vert _{L^q}\le C^{\text {deg}(P)} \Vert P\Vert _{L^p}\) for all homogeneous polynomials P on \(\mathbb {T}^n\). We also prove an exact inequality between the \(L^p\)-norm of a polynomial P on \(\mathbb {T}^n\) and its Mahler measure M(P), which is the geometric mean of |P| with respect to the normalized Lebesgue measure on \(\mathbb {T}^n\). Using extrapolation, we transfer this estimate into a Khintchine–Kahane type inequality, which, for polynomials on \(\mathbb {T}^n\), relates a certain exponential Orlicz norm and Mahler’s measure. Applications are given, including some interpolation estimates.     

Resilience of ranks of higher inclusion matrices

Let \(n \ge r \ge s \ge 0\) be integers and \(\mathcal {F}\) a family of r-subsets of [n]. Let \(W_{r,s}^{\mathcal {F}}\) be the higher inclusion matrix of the subsets in \({{\mathcal {F}}}\) vs. the s-subsets of [n]. When \(\mathcal {F}\) consists of all r-subsets of [n], we shall simply write \(W_{r,s}\) in place of \(W_{r,s}^{\mathcal {F}}\). In this paper we prove that the rank of the higher inclusion matrix \(W_{r,s}\) over an arbitrary field K is resilient. That is, if the size of \(\mathcal {F}\) is “close” to \({n \atopwithdelims ()r}\) then \({{\mathrm{rank}}}_{K}( W_{r,s}^{\mathcal {F}}) = {{\mathrm{rank}}}_{K}(W_{r,s})\), where K is an arbitrary field. Furthermore, we prove that the rank (over a field K) of the higher inclusion matrix of r-subspaces vs. s-subspaces of an n-dimensional vector space over \({\mathbb {F}}_q\) is also resilient if \(\mathrm{char}(K)\) is coprime to q.     

Cohomogeneity one actions on Minkowski spaces

We study isometric cohomogeneity one actions on the \((n+1)\)-dimensional Minkowski space \(\mathbb {L}^{n+1}\) up to orbit-equivalence. We give examples of isometric cohomogeneity one actions on \(\mathbb {L}^{n+1}\) whose orbit spaces are non-Hausdorff. We show that there exist isometric cohomogeneity one actions on \(\mathbb {L}^{n+1}\), \(n \ge 3\), which are orbit-equivalent on the complement of an n-dimensional degenerate subspace \(\mathbb {W}^n\) of \(\mathbb {L}^{n+1}\) and not orbit-equivalent on \(\mathbb {W}^n\). We classify isometric cohomogeneity one actions on \(\mathbb {L}^2\) and \(\mathbb {L}^3\) up to orbit-equivalence.