Divisibility of polynomials over finite fields and combinatorial applications

Consider a maximum-length shift-register sequence generated by a primitive polynomial f over a finite field. The set of its subintervals is a linear code whose dual code is formed by all polynomials divisible by f. Since the minimum weight of dual codes is directly related to the strength of the corresponding orthogonal arrays, we can produce orthogonal arrays by studying divisibility of polynomials. Munemasa (Finite Fields Appl 4(3):252–260, 1998) uses trinomials over \mathbbF₂{\mathbb{F}_2} to construct orthogonal arrays of guaranteed strength 2 (and almost strength 3). That result was extended by Dewar et al. (Des Codes Cryptogr 45:1–17, 2007) to construct orthogonal arrays of guaranteed strength 3 by considering divisibility of trinomials by pentanomials over \mathbbF₂{\mathbb{F}_2} . Here we first simplify the requirement in Munemasa’s approach that the characteristic polynomial of the sequence must be primitive: we show that the method applies even to the much broader class of polynomials with no repeated roots. Then we give characterizations of divisibility for binomials and trinomials over \mathbbF₃{\mathbb{F}_3} . Some of our results apply to any finite field \mathbbF_q{\mathbb{F}_q} with q elements.     

Implementing the 4-dimensional GLV method on GLS elliptic curves with <Emphasis Type="Italic">j</Emphasis>-invariant 0

The Gallant–Lambert–Vanstone (GLV) method is a very efficient technique for accelerating point multiplication on elliptic curves with efficiently computable endomorphisms. Galbraith et al. (J Cryptol 24(3):446–469, 2011) showed that point multiplication exploiting the 2-dimensional GLV method on a large class of curves over \mathbbF_p²{\mathbb{F}_{p^2}} was faster than the standard method on general elliptic curves over \mathbbF_p{\mathbb{F}_{p}} , and left as an open problem to study the case of 4-dimensional GLV on special curves (e.g., j (E) = 0) over \mathbbF_p²{\mathbb{F}_{p^2}} . We study the above problem in this paper. We show how to get the 4-dimensional GLV decomposition with proper decomposed coefficients, and thus reduce the number of doublings for point multiplication on these curves to only a quarter. The resulting implementation shows that the 4-dimensional GLV method on a GLS curve runs in about 0.78 the time of the 2-dimensional GLV method on the same curve and in between 0.78 − 0.87 the time of the 2-dimensional GLV method using the standard method over \mathbbF_p{\mathbb{F}_{p}} . In particular, our implementation reduces by up to 27% the time of the previously fastest implementation of point multiplication on x86-64 processors due to Longa and Gebotys (CHES2010).     

Periodicity of Non-Central Integral Arrangements Modulo Positive Integers

An integral coefficient matrix determines an integral arrangement of hyperplanes in \mathbbR^m{\mathbb{R}^m} . After modulo q reduction ${(q \in {\mathbb{Z}_{ >0 }})}${(q \in {\mathbb{Z}_{ >0 }})} , the same matrix determines an arrangement A_q{\mathcal{A}_q} of “hyperplanes” in \mathbbZ^m_q{\mathbb{Z}^m_q} . In the special case of central arrangements, Kamiya, Takemura, and Terao [J. Algebraic Combin. 27(3), 317–330 (2008)] showed that the cardinality of the complement of A_q{\mathcal{A}_q} in \mathbbZ^m_q{\mathbb{Z}^m_q} is a quasi-polynomial in ${q \in {\mathbb{Z}_{ >0 }}}${q \in {\mathbb{Z}_{ >0 }}} . Moreover, they proved in the central case that the intersection lattice of A_q{\mathcal{A}_q} is periodic from some q on. The present paper generalizes these results to the case of non-central arrangements. The paper also studies the arrangement [^(B)]_m^[0,a]{\hat{\mathcal{B}}_m^{[0,a]}} of Athanasiadis [J. Algebraic Combin. 10(3), 207–225 (1999)] to illustrate our results.     

Voronovskaja-Type Results in Compact Disks for Quaternion q-Bernstein Operators, q ≥ 1

Attaching to a compact disk [`(\mathbbD<sub>r</sub>)]{\overline{\mathbb{D}_{r}}} in the quaternion field \mathbbH{\mathbb{H}} and to some analytic function in Weierstrass sense on [`(\mathbbD_r)]{\overline{\mathbb{D}_{r}}} the so-called q-Bernstein operators with q ≥ 1, Voronovskaja-type results with quantitative upper estimates are proved. As applications, the exact orders of approximation in [`(\mathbbD_r)]{\overline{\mathbb{D}_{r}}} for these operators, namely \frac1n{\frac{1}{n}} if q = 1 and \frac1qⁿ{\frac{1}{q^{n}}} if q > 1, are obtained. The results extend those in the case of approximation of analytic functions of a complex variable in disks by q-Bernstein operators of complex variable in Gal (Mediterr J Math 5(3):253–272, 2008) and complete the upper estimates obtained for q-Bernstein operators of quaternionic variable in Gal (Approximation by Complex Bernstein and Convolution-Type Operators, 2009; Adv Appl Clifford Alg, doi:, 2011).     

The affine preservers of non-singular matrices

When \mathbbK{\mathbb{K}} is an arbitrary field, we study the affine automorphisms of M_n(\mathbbK){{\rm M}_n(\mathbb{K})} that stabilize GL_n(\mathbbK){{\rm GL}_n(\mathbb{K})}. Using a theorem of Dieudonné on maximal affine subspaces of singular matrices, this is easily reduced to the known case of linear preservers when n > 2 or # ${\mathbb{K} > 2}${\mathbb{K} > 2}. We include a short new proof of the more general Flanders theorem for affine subspaces of M_p,q(\mathbbK){{\rm M}_{p,q}(\mathbb{K})} with bounded rank. We also find that the group of affine transformations of M₂(\mathbbF₂){{\rm M}_2(\mathbb{F}_2)} that stabilize GL₂(\mathbbF₂){{\rm GL}_2(\mathbb{F}_2)} does not consist solely of linear maps. Using the theory of quadratic forms over \mathbbF₂{\mathbb{F}_2}, we construct explicit isomorphisms between it, the symplectic group Sp₄(\mathbbF₂){{\rm Sp}_4(\mathbb{F}_2)} and the symmetric group \mathfrakS₆{\mathfrak{S}_6}.     

Lifting of convex functions on Carnot groups and lack of convexity for a gauge function

Let ${\mathbb{G}}Let \mathbbG{\mathbb{G}} be a Carnot group of step r and m generators and homogeneous dimension Q. Let \mathbbF_m,r{\mathbb{F}_{m,r}} denote the free Lie group of step r and m generators. Let also p:\mathbbF_m,r?\mathbbG{\pi:\mathbb{F}_{m,r}\to\mathbb{G}} be a lifting map. We show that any horizontally convex function u on \mathbbG{\mathbb{G}} lifts to a horizontally convex function u°p{u\circ \pi} on \mathbbF_m,r{\mathbb{F}_{m,r}} (with respect to a suitable horizontal frame on \mathbbF_m,r{\mathbb{F}_{m,r}}). One of the main aims of the paper is to exhibit an example of a sub-Laplacian L=?_j=1^m X_j²{\mathcal{L}=\sum_{j=1}^m X_j^2} on a Carnot group of step two such that the relevant L{\mathcal{L}}-gauge function d (i.e., d ^2-Q is the fundamental solution for L{\mathcal{L}}) is not h-convex with respect to the horizontal frame {X ₁, . . . , X _m }. This gives a negative answer to a question posed in Danielli et al. (Commun. Anal. Geom. 11 (2003), 263–341).     

Small resolutions and non-liftable Calabi-Yau threefolds

We use properties of small resolutions of the ordinary double point in dimension three to construct smooth non-liftable Calabi-Yau threefolds. In particular, we construct a smooth projective Calabi-Yau threefold over \mathbbF₃{\mathbb{F}_3} that does not lift to characteristic zero and a smooth projective Calabi-Yau threefold over \mathbbF₅{\mathbb{F}_5} having an obstructed deformation. We also construct many examples of smooth Calabi-Yau algebraic spaces over \mathbbF_p{\mathbb{F}_p} that do not lift to algebraic spaces in characteristic zero.     

Extension theorems for paraboloids in the finite field setting

In this paper we study the L ^p ? L ^r boundedness of the extension operators associated with paraboloids in ${{\mathbb F}_{q}^{d}}In this paper we study the L ^p − L ^r boundedness of the extension operators associated with paraboloids in \mathbb F_q^d{{\mathbb F}_{q}^{d}} , where \mathbbF_q{\mathbb{F}_{q}} is a finite field of q elements. In even dimensions d ≥ 4, we estimate the number of additive quadruples in the subset E of the paraboloids, that is the number of quadruples (x,y,z,w) ? E⁴{(x,y,z,w) \in E^4} with x + y = z+w. As a result, in higher even dimensions, we obtain the sharp range of exponents p for which the extension operator is bounded, independently of q, from L ^p to L ⁴ in the case when −1 is a square number in \mathbbF_q{\mathbb{F}_{q}} . Using the sharp L ^p −L ⁴ result, we improve upon the range of exponents r, for which the L ² − L ^r estimate holds, obtained by Mockenhaupt and Tao (Duke Math 121:35–74, 2004) in even dimensions d ≥ 4. In addition, assuming that −1 is not a square number in \mathbbF_q{\mathbb{F}_{q}}, we extend their work done in three dimension to specific odd dimensions d ≥ 7. The discrete Fourier analytic machinery and Gauss sum estimates make an important role in the proof.     

Dilation of Newton Polytope and <Emphasis Type="Italic">p</Emphasis>-adic Estimate

Let f(X) be a polynomial in n variables over the finite field  \mathbbF_q\mathbb{F}_{q}. Its Newton polytope Δ(f) is the convex closure in ℝ ⁿ of the origin and the exponent vectors (viewed as points in ℝ ⁿ ) of monomials in f(X). The minimal dilation of Δ(f) such that it contains at least one lattice point of $\mathbb{Z}_{>0}^{n}$\mathbb{Z}_{>0}^{n} plays a vital pole in the p-adic estimate of the number of zeros of f(X) in  \mathbbF_q\mathbb{F}_{q}. Using this fact, we obtain several tight and computational bounds for the dilation which unify and improve a number of previous results in this direction.     

From Chaos to Global Convergence

The main purpose of this paper is to investigate dynamical systems F : \mathbbR² ? \mathbbR²{F : \mathbb{R}^2 \rightarrow \mathbb{R}^2} of the form F(x, y) = (f(x, y), x). We assume that f : \mathbbR² ? \mathbbR{f : \mathbb{R}^2 \rightarrow \mathbb{R}} is continuous and satisfies a condition that holds when f is non decreasing with respect to the second variable. We show that for every initial condition x₀ = (x ₀, y ₀), such that the orbit

All 4-Edge-Connected HHD-Free Graphs are {\mathbb{Z}_3}-Connected

An undirected graph G = (V, E) is called \mathbbZ₃{\mathbb{Z}_3}-connected if for all b: V ? \mathbbZ₃{b: V \rightarrow \mathbb{Z}_3} with ?_{v ? V}b(v)=0{\sum_{v \in V}b(v)=0}, an orientation D = (V, A) of G has a \mathbbZ₃{\mathbb{Z}_3}-valued nowhere-zero flow f: A? \mathbbZ₃-{0}{f: A\rightarrow \mathbb{Z}_3-\{0\}} such that ?_{e ? d⁺(v)}f(e)-?_{e ? d^-(v)}f(e)=b(v){\sum_{e \in \delta^+(v)}f(e)-\sum_{e \in \delta^-(v)}f(e)=b(v)} for all v ? V{v \in V}. We show that all 4-edge-connected HHD-free graphs are \mathbbZ₃{\mathbb{Z}_3}-connected. This extends the result due to Lai (Graphs Comb 16:165–176, 2000), which proves the \mathbbZ₃{\mathbb{Z}_3}-connectivity for 4-edge-connected chordal graphs.     

Cyclic codes over $${{\mathbb{F}}_2+u{\mathbb{F}}_2+v{\mathbb{F}}_2+uv{\mathbb{F}}_2}$$

In this work, we focus on cyclic codes over the ring \mathbbF₂+u\mathbbF₂+v\mathbbF₂+uv\mathbbF₂{{{\mathbb{F}}_2+u{\mathbb{F}}_2+v{\mathbb{F}}_2+uv{\mathbb{F}}_2}} , which is not a finite chain ring. We use ideas from group rings and works of AbuAlrub et.al. in (Des Codes Crypt 42:273–287, 2007) to characterize the ring (\mathbbF₂+u\mathbbF₂+v\mathbbF₂+uv\mathbbF₂)/(xⁿ-1){({{\mathbb{F}}_2+u{\mathbb{F}}_2+v{\mathbb{F}}_2+uv{\mathbb{F}}_2})/(x^n-1)} and cyclic codes of odd length. Some good binary codes are obtained as the images of cyclic codes over \mathbbF₂+u\mathbbF₂+v\mathbbF₂+uv\mathbbF₂{{{\mathbb{F}}_2+u{\mathbb{F}}_2+v{\mathbb{F}}_2+uv{\mathbb{F}}_2}} under two Gray maps that are defined. We also characterize the binary images of cyclic codes over \mathbbF₂+u\mathbbF₂+v\mathbbF₂+uv\mathbbF₂{{{\mathbb{F}}_2+u{\mathbb{F}}_2+v{\mathbb{F}}_2+uv{\mathbb{F}}_2}} in general.     

Counting Ω-ideals

Let ${\mathbb{A}}Let \mathbbA{\mathbb{A}} be a universal algebra of signature Ω, and let I{\mathcal{I}} be an ideal in the Boolean algebra P_\mathbbA{\mathcal{P}_{\mathbb{A}}} of all subsets of \mathbbA{\mathbb{A}} . We say that I{\mathcal{I}} is an Ω-ideal if I{\mathcal{I}} contains all finite subsets of \mathbbA{\mathbb{A}} and f(Aⁿ) ? I{f(A^{n}) \in \mathcal{I}} for every n-ary operation f ? W{f \in \Omega} and every A ? I{A \in \mathcal{I}} . We prove that there are 2^2à₀{2^{2^{\aleph_0}}} Ω-ideals in P_\mathbbA{\mathcal{P}_{\mathbb{A}}} provided that \mathbbA{\mathbb{A}} is countably infinite and Ω is countable.     

The Inverse Conjecture for the Gowers Norm over Finite Fields in Low Characteristic

We establish the inverse conjecture for the Gowers norm over finite fields, which asserts (roughly speaking) that if a bounded function f : V ? \mathbbC{f : V \rightarrow \mathbb{C}} on a finite-dimensional vector space V over a finite field \mathbbF{\mathbb{F}} has large Gowers uniformity norm ||f||_U^s+1(V){{\parallel{f}\parallel_{U^{s+1}(V)}}} , then there exists a (non-classical) polynomial P: V ? \mathbbT{P: V \rightarrow \mathbb{T}} of degree at most s such that f correlates with the phase e(P) = e ^2πiP . This conjecture had already been established in the “high characteristic case”, when the characteristic of \mathbbF{\mathbb{F}} is at least as large as s. Our proof relies on the weak form of the inverse conjecture established earlier by the authors and Bergelson [3], together with new results on the structure and equidistribution of non-classical polynomials, in the spirit of the work of Green and the first author [22] and of Kaufman and Lovett [28].     

Modular Lie algebras and the Gelfand–Kirillov conjecture

Let ${\mathfrak{g}}Let \mathfrakg{\mathfrak{g}} be a finite dimensional simple Lie algebra over an algebraically closed field \mathbbK\mathbb{K} of characteristic 0. Let \mathfrakg_\mathbbZ{\mathfrak{g}}_{{\mathbb{Z}}} be a Chevalley ℤ-form of \mathfrakg{\mathfrak{g}} and \mathfrakg_\Bbbk=\mathfrakg_\mathbbZ?_\mathbbZ\Bbbk{\mathfrak{g}}_{\Bbbk}={\mathfrak{g}}_{{\mathbb{Z}}}\otimes _{{\mathbb{Z}}}\Bbbk, where \Bbbk\Bbbk is the algebraic closure of  \mathbbF_p{\mathbb{F}}_{p}. Let G_\BbbkG_{\Bbbk} be a simple, simply connected algebraic \Bbbk\Bbbk-group with \operatornameLie(G_\Bbbk)=\mathfrakg_\Bbbk\operatorname{Lie}(G_{\Bbbk})={\mathfrak{g}}_{\Bbbk}. In this paper, we apply recent results of Rudolf Tange on the fraction field of the centre of the universal enveloping algebra U(\mathfrakg_\Bbbk)U({\mathfrak{g}}_{\Bbbk}) to show that if the Gelfand–Kirillov conjecture (from 1966) holds for \mathfrakg{\mathfrak{g}}, then for all p≫0 the field of rational functions \Bbbk (\mathfrakg_\Bbbk)\Bbbk ({\mathfrak{g}}_{\Bbbk}) is purely transcendental over its subfield \Bbbk(\mathfrakg_\Bbbk)^G_\Bbbk\Bbbk({\mathfrak{g}}_{\Bbbk})^{G_{\Bbbk}}. Very recently, it was proved by Colliot-Thélène, Kunyavskiĭ, Popov, and Reichstein that the field of rational functions \mathbbK(\mathfrakg){\mathbb{K}}({\mathfrak{g}}) is not purely transcendental over its subfield \mathbbK(\mathfrakg)^\mathfrakg{\mathbb{K}}({\mathfrak{g}})^{\mathfrak{g}} if \mathfrakg{\mathfrak{g}} is of type B _n , n≥3, D _n , n≥4, E₆, E₇, E₈ or F₄. We prove a modular version of this result (valid for p≫0) and use it to show that, in characteristic 0, the Gelfand–Kirillov conjecture fails for the simple Lie algebras of the above types. In other words, if \mathfrakg{\mathfrak{g}} is of type B _n , n≥3, D _n , n≥4, E₆, E₇, E₈ or F₄, then the Lie field of \mathfrakg{\mathfrak{g}} is more complicated than expected.     

Affine extractors over prime fields

An affine extractor is a map that is balanced on every affine subspace of large enough dimension. We construct an explicit affine extractor AE from \mathbbFⁿ \mathbb{F}^n to \mathbbF\mathbb{F}, \mathbbF\mathbb{F} a prime field, so that AE(x) is exponentially close to uniform when x is chosen uniformly at random from an arbitrary affine subspace of \mathbbFⁿ \mathbb{F}^n of dimension at least δn, 0<δ≤1 a constant. Previously, Bourgain constructed such affine extractors when the size of \mathbbF\mathbb{F} is two. Our construction is in the spirit of but different than Bourgain’s construction. This allows for simpler analysis and better quantitative results.     

The Nonexistence of Pseudoquaternions in {\mathbb{C}^{2\times 2}}

The field of quaternions, denoted by \mathbbH{\mathbb{H}} can be represented as an isomorphic four dimensional subspace of \mathbbR^4×4{\mathbb{R}^{4\times 4}}, the space of real matrices with four rows and columns. In addition to the quaternions there is another four dimensional subspace in \mathbbR^4×4{\mathbb{R}^{4\times 4}} which is also a field and which has – in connection with the quaternions – many pleasant properties. This field is called field of pseudoquaternions. It exists in \mathbbR^4×4{\mathbb{R}^{4\times 4}} but not in \mathbbH{\mathbb{H}}. It allows to write the quaternionic linear term axb in matrix form as Mx where x is the same as the quaternion x only written as a column vector in \mathbbR⁴{\mathbb{R}^4}. And M is the product of the matrix associated with the quaternion a with the matrix associated with the pseudoquaternion b.     

New Besov-type spaces and Triebel–Lizorkin-type spaces including Q spaces

Let ${s,\,\tau\in\mathbb{R}}Let s, t ? \mathbbR{s,\,\tau\in\mathbb{R}} and q ? (0,￥]{q\in(0,\infty]} . We introduce Besov-type spaces [(B)\dot]^s, t_p, q(\mathbbRⁿ){{{{\dot B}^{s,\,\tau}_{p,\,q}(\mathbb{R}^{n})}}} for p ? (0, ￥]{p\in(0,\,\infty]} and Triebel–Lizorkin-type spaces [(F)\dot]^s, t_p, q(\mathbbRⁿ) for p ? (0, ￥){{{{\dot F}^{s,\,\tau}_{p,\,q}(\mathbb{R}^{n})}}\,{\rm for}\, p\in(0,\,\infty)} , which unify and generalize the Besov spaces, Triebel–Lizorkin spaces and Q spaces. We then establish the j{\varphi} -transform characterization of these new spaces in the sense of Frazier and Jawerth. Using the j{\varphi} -transform characterization of [(B)\dot]^s, t_p, q(\mathbbRⁿ) and [(F)\dot]^s, t_p, q(\mathbbRⁿ){{{{\dot B}^{s,\,\tau}_{p,\,q}(\mathbb{R}^{n})}\, {\rm and}\, {{\dot F}^{s,\,\tau}_{p,\,q}(\mathbb{R}^{n})}}} , we obtain their embedding and lifting properties; moreover, for appropriate τ, we also establish the smooth atomic and molecular decomposition characterizations of [(B)\dot]^s, t_p, q(\mathbbRⁿ) and [(F)\dot]^s, t_p, q(\mathbbRⁿ){{{{\dot B}^{s,\,\tau}_{p,\,q}(\mathbb{R}^{n})}\,{\rm and}\, {{\dot F}^{s,\,\tau}_{p,\,q}(\mathbb{R}^{n})}}} . For s ? \mathbbR{s\in\mathbb{R}} , p ? (1, ￥), q ? [1, ￥){p\in(1,\,\infty), q\in[1,\,\infty)} and t ? [0, \frac1(max{p, q})￠]{\tau\in[0,\,\frac{1}{(\max\{p,\,q\})'}]} , via the Hausdorff capacity, we introduce certain Hardy–Hausdorff spaces B[(H)\dot]^s, t_p, q(\mathbbRⁿ){{{{B\dot{H}^{s,\,\tau}_{p,\,q}(\mathbb{R}^{n})}}}} and prove that the dual space of B[(H)\dot]^s, t_p, q(\mathbbRⁿ){{{{B\dot{H}^{s,\,\tau}_{p,\,q}(\mathbb{R}^{n})}}}} is just [(B)\dot]^-s, t_p￠, q￠(\mathbbRⁿ){\dot{B}^{-s,\,\tau}_{p',\,q'}(\mathbb{R}^{n})} , where t′ denotes the conjugate index of t ? (1,￥){t\in (1,\infty)} .     

Global existence of weak solutions for the Navier�CStokes equations with capillarity on the half-line

In this paper, we construct the global weak solutions to the initial-boundary problem for the Navier–Stokes system with capillarity in the half space \mathbbR₊¹{\mathbb{R}_+^1}. The result extends Eugene Tsyganov’s existence theorem which considered the problem in the finite region published in J. Differential Equaions 245:3936–3955, 2008.