Linear recurring sequences and subfield subcodes of cyclic codes

Linear recurring sequences over finite fields play an important role in coding theory and cryptography. It is known that subfield subcodes of linear codes yield some good codes. In this paper, we study linear recurring sequences and subfield subcodes. Let Mqm(f(x)) denote the set of all linear recurring sequences over Fqm with characteristic polynomial f(x) over Fqm . Denote the restriction of Mqm(f(x)) to sequences over Fq and the set after applying trace function to each sequence in Mqm(f(x)) by Mqm(f(x)) | Fq and Tr( Mqm(f(x))), respectively. It is shown that these two sets are both complete sets of linear recurring sequences over Fq with some characteristic polynomials over Fq. In this paper, we firstly determine the characteristic polynomials for these two sets. Then, using these results, we determine the generator polynomials of subfield subcodes and trace codes of cyclic codes over Fqm .     

Some relations on the ordering of trees by minimal energies between subclasses of trees

The energy of a graph is defined as the sum of the absolute values of all eigenvalues of the graph. A tree is said to be non-starlike if it has at least two vertices with degree more than 2. A caterpillar is a tree in which a removal of all pendent vertices makes a path. Let $\mathcal{T}_{n,d}$ , $\mathbb{T}_{n,p}$ be the set of all trees of order n with diameter d, p pendent vertices respectively. In this paper, we investigate the relations on the ordering of trees and non-starlike trees by minimal energies between $\mathcal{T}_{n,d}$ and $\mathbb{T}_{n,n-d+1}$ . We first show that the first two trees (non-starlike trees, resp.) with minimal energies in $\mathcal{T}_{n,d}$ and $\mathbb{T}_{n,n-d+1}$ are the same for 3≤d≤n?2 (3≤d≤n?3, resp.). Then we obtain that the trees with third-minimal energy in $\mathcal{T}_{n,d}$ and $\mathbb{T}_{n,n-d+1}$ are the same when n≥11, 3≤d≤n?2 and d≠8; and the tree with third-minimal energy in $\mathcal{T}_{n,8}$ is the caterpillar with third-minimal energy in $\mathbb{T}_{n,n-7}$ for n≥11.     

The Generalization of the Decomposition of Functions by Energy Operators

This work starts with the introduction of a family of differential energy operators. Energy operators $({\varPsi}_{R}^{+}, {\varPsi}_{R}^{-})$ were defined together with a method to decompose the wave equation in a previous work. Here the energy operators are defined following the order of their derivatives $(\varPsi^{-}_{k}, \varPsi^{+}_{k}, k=\{0,\pm 1,\pm 2,\ldots\})$ . The main part of the work demonstrates for any smooth real-valued function f in the Schwartz space $(\mathbf{S}^{-}(\mathbb{R}))$ , the successive derivatives of the n-th power of f ( $n \in \mathbb{Z}$ and n≠0) can be decomposed using only $\varPsi^{+}_{k}$ (Lemma); or if f in a subset of $\mathbf{S}^{-}(\mathbb{R})$ , called $\mathbf{s}^{-}(\mathbb{R})$ , $\varPsi^{+}_{k}$ and $\varPsi^{-}_{k}$ ( $k\in \mathbb{Z}$ ) decompose in a unique way the successive derivatives of the n-th power of f (Theorem). Some properties of the Kernel and the Image of the energy operators are given along with the development. Finally, the paper ends with the application to the energy function.     

On the sup-norm of Maass cusp forms of large level. III

Let $f$ be a Hecke–Maass cuspidal newform of square-free level $N$ and Laplacian eigenvalue $\lambda $ . It is shown that $\left||f \right||_\infty \ll _{\lambda ,\epsilon } N^{-\frac{1}{6}+\epsilon } \left||f \right||_2$ for any $\epsilon >0$ .     

Computing α-Invariants of Singular del Pezzo Surfaces

We prove a new local inequality for divisors on surfaces and utilize it to compute α-invariants of singular del Pezzo surfaces, which implies that del Pezzo surfaces of degree one whose singular points are of type $\mathbb{A}_{1}$ , $\mathbb{A}_{2}$ , $\mathbb{A}_{3}$ , $\mathbb{A}_{4}$ , $\mathbb{A}_{5}$ , or $\mathbb{A}_{6}$ are Kähler-Einstein.     

Towards a classification of modular compactifications of \mathcal {M}_{g,n}

The moduli space of smooth curves admits a beautiful compactification $\mathcal{M}_{g,n} \subset \overline{\mathcal{M}}_{g,n}$ by the moduli space of stable curves. In this paper, we undertake a systematic classification of alternate modular compactifications of $\mathcal{M}_{g,n}$ . Let $\mathcal{U}_{g,n}$ be the (non-separated) moduli stack of all n-pointed reduced, connected, complete, one-dimensional schemes of arithmetic genus g. When g=0, $\mathcal{U}_{0,n}$ is irreducible and we classify all open proper substacks of $\mathcal{U}_{0,n}$ . When g≥1, $\mathcal{U}_{g,n}$ may not be irreducible, but there is a unique irreducible component $\mathcal{V}_{g,n} \subset\mathcal{U}_{g,n}$ containing $\mathcal{M}_{g,n}$ . We classify open proper substacks of $\mathcal {V}_{g,n}$ satisfying a certain stability condition.     

{\boldsymbol(}\boldsymbol{\mathcal{Z}}_{\bf 1}, \boldsymbol{\mathcal{Z}}_{\bf 2}{\boldsymbol)}-Complete Partially Ordered Sets and Their Representations by \boldsymbol{\mathcal{Q}}-Spaces

The present paper proposes a general theory for $\left( \mathcal{Z}_{1}, \mathcal{Z}_{2}\right) $ -complete partially ordered sets (alias $\mathcal{Z} _{1}$ -join complete and $\mathcal{Z}_{2}$ -meet complete partially ordered sets) and their Stone-like representations. It is shown that for suitably chosen subset selections $\mathcal{Z}_{i}$ (i?=?1,...,4) and $\mathcal{Q} =\left( \mathcal{Z}_{1},\mathcal{Z}_{2},\mathcal{Z}_{3},\mathcal{Z} _{4}\right) $ , the category $\mathcal{Q}$ P of $\left( \mathcal{Z}_{1},\mathcal{Z}_{2}\right) $ -complete partially ordered sets and $\left( \mathcal{Z}_{3},\mathcal{Z}_{4}\right) $ -continuous (alias $\mathcal{ Z}_{3}$ -join preserving and $\mathcal{Z}_{4}$ -meet preserving) functions forms a useful categorical framework for various order-theoretical constructs, and has a close connection with the category $\mathcal{Q}$ S of $\mathcal{Q}$ -spaces which are generalizations of topological spaces involving subset selections. In particular, this connection turns into a dual equivalence between the full subcategory $ \mathcal{Q}$ P _s of $\mathcal{Q}$ P of all $\mathcal{Q}$ -spatial objects and the full subcategory $\mathcal{Q}$ S _s of $\mathcal{Q}$ S of all $\mathcal{Q}$ -sober objects. Here $\mathcal{Q}$ -spatiality and $\mathcal{Q}$ -sobriety extend usual notions of spatiality of locales and sobriety of topological spaces to the present approach, and their relations to $\mathcal{Z}$ -compact generation and $\mathcal{Z}$ -sobriety have also been pointed out in this paper.     

Generalised Gagliardo–Nirenberg Inequalities Using Weak Lebesgue Spaces and BMO

Using elementary arguments based on the Fourier transform we prove that for ${1 \leq q < p < \infty}$ and ${s \geq 0}$ with s > n(1/2 ? 1/p), if ${f \in L^{q,\infty} (\mathbb{R}^n) \cap \dot{H}^s (\mathbb{R}^n)}$ , then ${f \in L^p(\mathbb{R}^n)}$ and there exists a constant c _p,q,s such that $$\| f \|_{L^{p}} \leq c_{p,q,s} \| f \|^\theta _{L^{q,\infty}} \| f \|^{1-\theta}_{\dot{H}^s},$$ where 1/p = θ/q + (1?θ)(1/2?s/n). In particular, in ${\mathbb{R}^2}$ we obtain the generalised Ladyzhenskaya inequality ${\| f \| _{L^4} \leq c \| f \|^{1/2}_{L^{2,\infty}} \| f \|^{1/2}_{\dot{H}^1}}$ .We also show that for s = n/2 and q > 1 the norm in ${\| f \|_{\dot{H}^{n/2}}}$ can be replaced by the norm in BMO. As well as giving relatively simple proofs of these inequalities, this paper provides a brief primer of some basic concepts in harmonic analysis, including weak spaces, the Fourier transform, the Lebesgue Differentiation Theorem, and Calderon–Zygmund decompositions.     

Fixed point homomorphisms for parameterized maps

Let X be an ANR (absolute neighborhood retract), ${\Lambda}$ a k-dimensional topological manifold with topological orientation ${\eta}$ , and ${f : D \rightarrow X}$ a locally compact map, where D is an open subset of ${X \times \Lambda}$ . We define Fix(f) as the set of points ${{(x, \lambda) \in D}}$ such that ${x = f(x, \lambda)}$ . For an open pair (U, V) in ${X \times \Lambda}$ such that ${{\rm Fix}(f) \cap U \backslash V}$ is compact we construct a homomorphism ${\Sigma_{(f,U,V)} : H^{k}(U, V ) \rightarrow R}$ in the singular cohomologies H* over a ring-with-unit R, in such a way that the properties of Solvability, Excision and Naturality, Homotopy Invariance, Additivity, Multiplicativity, Normalization, Orientation Invariance, Commutativity, Contraction, Topological Invariance, and Ring Naturality hold. In the case of a ${C^{\infty}}$ -manifold ${\Lambda}$ , these properties uniquely determine ${\Sigma}$ . By passing to the direct limit of ${\Sigma_{(f,U,V)}}$ with respect to the pairs (U, V) such that ${K = {\rm Fix}(f) \cap U \backslash V}$ , we define a homomorphism ${\sigma_{(f,K)} : {H}_{k}({\rm Fix}(f), Fix(f) \backslash K) \rightarrow R}$ in the ?ech cohomologies. Properties of ${\Sigma}$ and ${\sigma}$ are equivalent each to the other. We indicate how the homomorphisms generalize the fixed point index.     

Conservative fragments of {{S}^{1}_{2}} and {{R}^{1}_{2}}

Conservative subtheories of ${{R}^{1}_{2}}$ and ${{S}^{1}_{2}}$ are presented. For ${{S}^{1}_{2}}$ , a slight tightening of Je?ábek??s result (Math Logic Q 52(6):613?C624, 2006) that ${T^{0}_{2} \preceq_{\forall \Sigma^{b}_{1}}S^{1}_{2}}$ is presented: It is shown that ${T^{0}_{2}}$ can be axiomatised as BASIC together with induction on sharply bounded formulas of one alternation. Within this ${\forall\Sigma^{b}_{1}}$ -theory, we define a ${\forall\Sigma^{b}_{0}}$ -theory, ${T^{-1}_{2}}$ , for the ${\forall\Sigma^{b}_{0}}$ -consequences of ${S^{1}_{2}}$ . We show ${T^{-1}_{2}}$ is weak by showing it cannot ${\Sigma^{b}_{0}}$ -define division by 3. We then consider what would be the analogous ${\forall\hat\Sigma^{b}_{1}}$ -conservative subtheory of ${R^{1}_{2}}$ based on Pollett (Ann Pure Appl Logic 100:189?C245, 1999. It is shown that this theory, ${{T}^{0,\left\{2^{(||\dot{id}||)}\right\}}_{2}}$ , also cannot ${\Sigma^{b}_{0}}$ -define division by 3. On the other hand, we show that ${{S}^{0}_{2}+open_{\{||id||\}}}$ -COMP is a ${\forall\hat\Sigma^{b}_{1}}$ -conservative subtheory of ${R^{1}_{2}}$ . Finally, we give a refinement of Johannsen and Pollett (Logic Colloquium?? 98, 262?C279, 2000) and show that ${\hat{C}^{0}_{2}}$ is ${\forall\hat\Sigma^{b}_{1}}$ -conservative over a theory based on open _cl-comprehension.     

Donsker-type theorems for nonparametric maximum likelihood estimators

Let ${\mathcal{P}}$ be a nonparametric probability model consisting of smooth probability densities and let ${\hat{p}_{n}}$ be the corresponding maximum likelihood estimator based on n independent observations each distributed according to the law ${\mathbb{P}}$ . With $\hat{\mathbb{P}}_{n}$ denoting the measure induced by the density ${\hat{p}_{n}}$ , define the stochastic process ${\hat{\nu}}_{n}: f\longmapsto \sqrt{n} \int fd({\hat{\mathbb{P}}}_{n} -\mathbb{P})$ where f ranges over some function class ${\mathcal{F}}$ . We give a general condition for Donsker classes ${\mathcal{F}}$ implying that the stochastic process $\hat{\nu}_{n}$ is asymptotically equivalent to the empirical process in the space ${\ell ^{\infty }(\mathcal{F})}$ of bounded functions on ${ \mathcal{F}}$ . This implies in particular that $\hat{\nu}_{n}$ converges in law in ${\ell ^{\infty }(\mathcal{F})}$ to a mean zero Gaussian process. We verify the general condition for a large family of Donsker classes ${\mathcal{ F}}$ . We give a number of applications: convergence of the probability measure ${\hat{\mathbb{P}}_{n}}$ to ${\mathbb{P}}$ at rate ${\sqrt{n}}$ in certain metrics metrizing the topology of weak(-star) convergence; a unified treatment of convergence rates of the MLE in a continuous scale of Sobolev-norms; ${\sqrt{n}}$ -efficient estimation of nonlinear functionals defined on ${\mathcal{P}}$ ; limit theorems at rate ${\sqrt{n}}$ for the maximum likelihood estimator of the convolution product ${\mathbb{P\ast P}}$ .     

On the cohomology of the orthosymplectic superalgebra

Let $\mathfrak{F}_{\lambda}^{n}$ be the $\mathop {\mathfrak {osp}}\nolimits \,(n|2)$ -module of weighted densities on ?^1|n of weight ??. We compute the cohomology spaces $\mathrm{H}^{k}_{\mathrm{diff}}\left(\mathop {\mathfrak {osp}}\nolimits \,(n|2),\mathfrak{F}_{\lambda}^{n}\right)$ , where k=1 and n=0,1,2 or k=2 and n=0,1. We explicitly give cocycles spanning these cohomology spaces.     

Composition Operators on Spaces of Fractional Cauchy Transforms

For ?? > 0, the Banach space ${\mathcal{F}_{\alpha}}$ is defined as the collection of functions f which can be represented as integral transforms of an appropriate kernel against a Borel measure defined on the unit circle T. Let ?? be an analytic self-map of the unit disc D. The map ?? induces a composition operator on ${\mathcal{F}_{\alpha}}$ if ${C_{\Phi}(f) = f \circ \Phi \in \mathcal{F}_{\alpha}}$ for any function ${f \in \mathcal{F}_{\alpha}}$ . Various conditions on ?? are given, sufficient to imply that C _?? is bounded on ${\mathcal{F}_{\alpha}}$ , in the case 0 < ?? < 1. Several of the conditions involve ???? and the theory of multipliers of the space ${\mathcal{F}_{\alpha}}$ . Relations are found between the behavior of C _?? and the membership of ?? in the Dirichlet spaces. Conditions given in terms of the generalized Nevanlinna counting function are shown to imply that ?? induces a bounded composition operator on ${\mathcal{F}_{\alpha}}$ , in the case 1/2 ?? ?? < 1. For such ??, examples are constructed such that ${\| \Phi \|_{\infty} = 1}$ and ${C_{\Phi}: \mathcal{F}_{\alpha} \rightarrow \mathcal{F}_{\alpha}}$ is bounded.     

Representation of Polynomials by Linear Combinations of Radial Basis Functions

Let ${\mathcal {P}_{n}^{d}}$ denote the space of polynomials on ? ^d of total degree n. In this work, we introduce the space of polynomials ${\mathcal {Q}_{2 n}^{d}}$ such that ${\mathcal {P}_{n}^{d}}\subset {\mathcal {Q}_{2 n}^{d}}\subset\mathcal{P}_{2n}^{d}$ and which satisfy the following statement: Let h be any fixed univariate even polynomial of degree n and $\mathcal{A}$ be a finite set in ? ^d . Then every polynomial P from the space  ${\mathcal {Q}_{2 n}^{d}}$ may be represented by a linear combination of radial basis functions of the form h(∥x+a∥), $a\in \mathcal{A}$ , if and only if the set $\mathcal{A}$ is a uniqueness set for the space  ${\mathcal {Q}_{2 n}^{d}}$ .     

A unified approach for minimizing composite norms

We propose a first-order augmented Lagrangian algorithm (FALC) to solve the composite norm minimization problem $$\begin{aligned} \begin{array}{ll} \min \limits _{X\in \mathbb{R }^{m\times n}}&\mu _1\Vert \sigma (\mathcal{F }(X)-G)\Vert _\alpha +\mu _2\Vert \mathcal{C }(X)-d\Vert _\beta ,\\ \text{ subject} \text{ to}&\mathcal{A }(X)-b\in \mathcal{Q }, \end{array} \end{aligned}$$ where $\sigma (X)$ denotes the vector of singular values of $X \in \mathbb{R }^{m\times n}$ , the matrix norm $\Vert \sigma (X)\Vert _{\alpha }$ denotes either the Frobenius, the nuclear, or the $\ell _2$ -operator norm of $X$ , the vector norm $\Vert .\Vert _{\beta }$ denotes either the $\ell _1$ -norm, $\ell _2$ -norm or the $\ell _{\infty }$ -norm; $\mathcal{Q }$ is a closed convex set and $\mathcal{A }(.)$ , $\mathcal{C }(.)$ , $\mathcal{F }(.)$ are linear operators from $\mathbb{R }^{m\times n}$ to vector spaces of appropriate dimensions. Basis pursuit, matrix completion, robust principal component pursuit (PCP), and stable PCP problems are all special cases of the composite norm minimization problem. Thus, FALC is able to solve all these problems in a unified manner. We show that any limit point of FALC iterate sequence is an optimal solution of the composite norm minimization problem. We also show that for all $\epsilon >0$ , the FALC iterates are $\epsilon $ -feasible and $\epsilon $ -optimal after $\mathcal{O }(\log (\epsilon ^{-1}))$ iterations, which require $\mathcal{O }(\epsilon ^{-1})$ constrained shrinkage operations and Euclidean projection onto the set $\mathcal{Q }$ . Surprisingly, on the problem sets we tested, FALC required only $\mathcal{O }(\log (\epsilon ^{-1}))$ constrained shrinkage, instead of the $\mathcal{O }(\epsilon ^{-1})$ worst case bound, to compute an $\epsilon $ -feasible and $\epsilon $ -optimal solution. To best of our knowledge, FALC is the first algorithm with a known complexity bound that solves the stable PCP problem.     

Program extraction for 2-random reals

Let ${2-\textsf{RAN}}$ be the statement that for each real X a real 2-random relative to X exists. We apply program extraction techniques we developed in Kreuzer and Kohlenbach (J. Symb. Log. 77(3):853–895, 2012. doi:10.2178/jsl/1344862165), Kreuzer (Notre Dame J. Formal Log. 53(2):245–265, 2012. doi:10.1215/00294527-1715716) to this principle. Let ${{\textsf{WKL}_0^\omega}}$ be the finite type extension of ${\textsf{WKL}_0}$ . We obtain that one can extract primitive recursive realizers from proofs in ${{\textsf{WKL}_0^\omega} + \Pi^0_1-{\textsf{CP}} + 2-\textsf{RAN}}$ , i.e., if ${{\textsf{WKL}_0^\omega} + \Pi^0_1-{\textsf{CP}} + 2-\textsf{RAN} \, {\vdash} \, \forall{f}\, {\exists}{x} A_{qf}(f,x)}$ then one can extract from the proof a primitive recursive term t(f) such that ${A_{qf}(f,t(f))}$ . As a consequence, we obtain that ${{\textsf{WKL}_0}+ \Pi^0_1 - {\textsf{CP}} + 2-\textsf{RAN}}$ is ${\Pi^0_3}$ -conservative over ${\textsf{RCA}_0}$ .     

Scaling relationship between the copositive cone and Parrilo’s first level approximation

We investigate the relation between the cone ${\mathcal{C}^{n}}$ of n × n copositive matrices and the approximating cone ${\mathcal{K}_{n}^{1}}$ introduced by Parrilo. While these cones are known to be equal for n ≤ 4, we show that for n ≥ 5 they are not equal. This result is based on the fact that ${\mathcal{K}_{n}^{1}}$ is not invariant under diagonal scaling. We show that for any copositive matrix which is not the sum of a nonnegative and a positive semidefinite matrix we can find a scaling which is not in ${\mathcal{K}_{n}^{1}}$ . In fact, we show that if all scaled versions of a matrix are contained in ${\mathcal{K}_{n}^{r}}$ for some fixed r, then the matrix must be in ${\mathcal{K}_{n}^{0}}$ . For the 5 × 5 case, we show the more surprising result that we can scale any copositive matrix X into ${\mathcal{K}_{5}^{1}}$ and in fact that any scaling D such that ${(DXD)_{ii} \in \{0,1\}}$ for all i yields ${DXD \in \mathcal{K}_{5}^{1}}$ . From this we are able to use the cone ${\mathcal{K}_{5}^{1}}$ to check if any order 5 matrix is copositive. Another consequence of this is a complete characterisation of ${\mathcal{C}^{5}}$ in terms of ${\mathcal{K}_{5}^{1}}$ . We end the paper by formulating several conjectures.