Fast decoding of Gabidulin codes

Gabidulin codes are the analogues of Reed–Solomon codes in rank metric and play an important role in various applications. In this contribution, a method for efficient decoding of Gabidulin codes up to their error correcting capability is shown. The new decoding algorithm for Gabidulin codes (defined over ${\mathbb{F}_{q^m}}$ ) directly provides the evaluation polynomial of the transmitted codeword. This approach can be seen as a Gao-like algorithm and uses an equivalent of the Euclidean Algorithm. In order to achieve low complexity, a fast symbolic product and a fast symbolic division are presented. The complexity of the whole decoding algorithm for Gabidulin codes is ${\mathcal{O} (m^3 \, \log \, m)}$ operations over the ground field ${\mathbb{F}_q}$ .     

A characterisation of multiplicity

LetR be a ring with non-zero identity and unitary leftR-modules, while \(\mathcal{N}_R \) is the subcategory of NoetherianR-modules. Given a length functionL on \(\mathcal{N}_R \) and central elements α₁,...,α _n ofR we can define the multiplicity length functione _R (L|α₁,...α _n |) on \(\mathcal{N}_R \) with the same properties as the classical multiplicity. Here, we characterise multiplicity as the greatest length function which can be defined inductively in terms of a certain type of function on \(\mathcal{N}_R \) .     

First moment of Rankin–Selberg central L-values and subconvexity in the level aspect

Let 1≤N<M with N and M coprime and square-free. Through classical analytic methods we estimate the first moment of central L-values $L(\frac{1}{2},f\times g)$ where $f\in\mathcal{S}^{*}_{k}(N)$ runs over primitive holomorphic forms of level N and trivial nebentypus and g is a given form of level M. As a result, we recover the bound $L(\frac{1}{2},f\times g) \ll_{\varepsilon}(N + \sqrt{M}) N^{\varepsilon}M^{\varepsilon}$ when g is dihedral. The first moment method also applies to the special derivative $L'(\frac{1}{2},f\times g)$ under the assumption that it is non-negative for all $f\in\mathcal{S}^{*}_{k}(N)$ .     

Mixed Invariant Subspaces over the Bidisk

It is known that the structure of invariant subspaces I of the Hardy space H ² over the bidisk is extremely complicated. One reason is that it is difficult to describe infinite dimensional wandering spaces ${I\ominus zI}$ completely. In this paper, we study the structure of nontrivial closed subspaces N of H ² with ${T_zN\subset N}$ and ${T^*_wN\subset N}$ , which are called mixed invariant subspaces under T _z and ${T^*_w}$ . We know that the dimension of ${N\ominus zN}$ ranges from 1 to ??. If ${T^*_w(N\ominus zN)\subset N\ominus zN}$ , we may describe N completely. If ${T^*_w(N\ominus zN)\not\subset N\ominus zN}$ , it seems difficult to describe N generally. So we study N under the condition ${dim\,(N\ominus zN)=1}$ . Write ${M=H^2\ominus N}$ . We describe ${M\ominus wM}$ precisely. We give a characterization of N for which there is a nonzero function ${\varphi}$ in ${M\ominus wM}$ satisfying ${z^k\varphi\in M\ominus wM}$ for every k ?? 0. We also see that the space ${M\ominus wM}$ has a deep connection with the de Branges?CRovnyak spaces studied by Sarason.     

A concentration inequality and a local law for the sum of two random matrices

Let ${H_{N}=A_{N}+U_{N}B_{N}U_{N}^{\ast}}$ where A _N and B _N are two N-by-N Hermitian matrices and U _N is a Haar-distributed random unitary matrix, and let ${\mu _{H_{N}},}$ ${\mu_{A_{N}}, \mu _{B_{N}}}$ be empirical measures of eigenvalues of matrices H _N , A _N , and B _N , respectively. Then, it is known (see Pastur and Vasilchuk in Commun Math Phys 214:249?C286, 2000) that for large N, the measure ${\mu _{H_{N}}}$ is close to the free convolution of measures ${\mu _{A_{N}}}$ and ${\mu _{B_{N}}}$ , where the free convolution is a non-linear operation on probability measures. The large deviations of the cumulative distribution function of ${\mu _{H_{N}}}$ from its expectation have been studied by Chatterjee (J Funct Anal 245:379?C389, 2007). In this paper we improve Chatterjee??s concentration inequality and show that it holds with the rate which is quadratic in N. In addition, we prove a local law for eigenvalues of ${H_{N_{N}},}$ by showing that the normalized number of eigenvalues in an interval approaches the density of the free convolution of??? _A and??? _B provided that the interval has width (log N)^?1/2.     

Quasi–Monte Carlo rules for numerical integration over the unit sphere {\mathbb{S}^2}

We study numerical integration on the unit sphere ${\mathbb{S}^2 \subseteq\mathbb{R}^3}$ using equal weight quadrature rules, where the weights are such that constant functions are integrated exactly. The quadrature points are constructed by lifting a (0, m, 2)-net given in the unit square [0, 1]² to the sphere ${\mathbb{S}^2}$ by means of an area preserving map. A similar approach has previously been suggested by Cui and Freeden [SIAM J Sci Comput 18(2):595–609, 1997]. We prove three results. The first one is that the construction is (almost) optimal with respect to discrepancies based on spherical rectangles. Further we prove that the point set is asymptotically uniformly distributed on ${\mathbb{S}^2}$ . And finally, we prove an upper bound on the spherical cap L ₂-discrepancy of order N ^?1/2(log N)^1/2 (where N denotes the number of points). This improves upon the bound on the spherical cap L ₂-discrepancy of the construction by Lubotzky, Phillips and Sarnak [Commun Pure Appl Math 39(S, suppl):S149–S186, 1986] by a factor of ${\sqrt{\log N}}$ . Numerical results suggest that the (0, m, 2)-nets lifted to the sphere ${\mathbb{S}^2}$ have spherical cap L ₂-discrepancy converging with the optimal order of N ^?3/4.     

On the functional codes defined by quadrics and Hermitian varieties

In recent years, functional codes have received much attention. In his PhD thesis, F.A.B. Edoukou investigated various functional codes linked to quadrics and Hermitian varieties defined in finite projective spaces (Edoukou, PhD Thesis, 2007). This work was continued in (Edoukou et al., Des Codes Cryptogr 56:219–233, 2010; Edoukou et al., J Pure Appl Algebr 214:1729–1739, 2010; Hallez and Storme, Finite Fields Appl 16:27–35, 2010), where the results of the thesis were improved and extended. In particular, Hallez and Storme investigated the functional codes ${C_2(\mathcal{H})}$ , with ${\mathcal{H}}$ a non-singular Hermitian variety in PG(N, q ²). The codewords of this code are defined by evaluating the points of ${\mathcal{H}}$ in the quadratic polynomials defined over ${\mathbb{F}_{q^2}}$ . We now present the similar results for the functional code ${C_{Herm}(\mathcal{Q})}$ . The codewords of this code are defined by evaluating the points of a non-singular quadric ${\mathcal{Q}}$ in PG(N, q ²) in the polynomials defining the Hermitian varieties of PG(N, q ²).     

Improved bounds for separating hash families

An ${(N;n,m,\{w_1,\ldots, w_t\})}$ -separating hash family is a set ${\mathcal{H}}$ of N functions ${h: \; X \longrightarrow Y}$ with ${|X|=n, |Y|=m, t \geq 2}$ having the following property. For any pairwise disjoint subsets ${C_1, \ldots, C_t \subseteq X}$ with ${|C_i|=w_i, i=1, \ldots, t}$ , there exists at least one function ${h \in \mathcal{H}}$ such that ${h(C_1), h(C_2), \ldots, h(C_t)}$ are pairwise disjoint. Separating hash families generalize many known combinatorial structures such as perfect hash families, frameproof codes, secure frameproof codes, identifiable parent property codes. In this paper we present new upper bounds on n which improve many previously known bounds. Further we include constructions showing that some of these bounds are tight.     

Unitary SK1 of semiramified graded and valued division algebras

We prove formulas for SK₁(E, τ), which is the unitary SK₁ for a graded division algebra E finite-dimensional and semiramified over its center T with respect to a unitary involution τ on E. Every such formula yields a corresponding formula for SK₁(D, ρ) where D is a division algebra tame and semiramified over a Henselian valued field and ρ is a unitary involution on D. For example, it is shown that if ${\sf{E} \sim \sf{I}_0 \otimes_{\sf{T}_0}\sf{N}}$ where I ₀ is a central simple T ₀-algebra split by N ₀ and N is decomposably semiramified with ${\sf{N}_0 \cong L_1\otimes_{\sf{T}_0} L_2}$ with L ₁, L ₂ fields each cyclic Galois over T ₀, then $${\rm SK}_1(\sf{E}, \tau) \,\cong\ {\rm Br}(({L_1}\otimes_{\sf{T}_0} {L_2})/\sf{T}_0;\sf{T}_0^\tau)\big/ \left[{\rm Br}({L_1}/\sf{T}_0;\sf{T}_0^\tau)\cdot {\rm Br}({L_2}/\sf{T}_0;\sf{T}_0^\tau) \cdot \langle[\sf{I}_0]\rangle\right].$$      

Optimal Reconstruction Might be Hard

Given as input a point set $\mathcal S $ that samples a shape $\mathcal A $ , the condition required for inferring Betti numbers of $\mathcal A $ from $\mathcal S $ in polynomial time is much weaker than the conditions required by any known polynomial time algorithm for producing a topologically correct approximation of $\mathcal A $ from $\mathcal S $ . Under the former condition which we call the weak precondition, we investigate the question whether a polynomial time algorithm for reconstruction exists. As a first step, we provide an algorithm which outputs an approximation of the shape with the correct Betti numbers under a slightly stronger condition than the weak precondition. Unfortunately, even though our algorithm terminates, its time complexity is unbounded. We then identify at the heart of our algorithm a test which requires answering the following question: given 2 two-dimensional simplicial complexes $L \subset K$ , does there exist a simplicial complex containing $L$ and contained in $K$ which realizes the persistent homology of $L$ into $K$ ? We call this problem the homological simplification of the pair $(K,L)$ and prove that this problem is NP-complete, using a reduction from 3SAT.     

Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function

This paper presents extensions and further analytical properties of algorithms for linear programming based only on primal scaling and projected gradients of a potential function. The paper contains extensions and analysis of two polynomial-time algorithms for linear programming. We first present an extension of Gonzaga's O(nL) iteration algorithm, that computes dual variables and does not assume a known optimal objective function value. This algorithm uses only affine scaling, and is based on computing the projected gradient of the potential function $$q\ln (x^T s) - \sum\limits_{j = 1}^n {\ln (x_j )} $$ wherex is the vector of primal variables ands is the vector of dual slack variables, and q = n + \(\sqrt n \) . The algorithm takes either a primal step or recomputes dual variables at each iteration. We next present an alternate form of Ye's O( \(\sqrt n \) L) iteration algorithm, that is an extension of the first algorithm of the paper, but uses the potential function $$q\ln (x^T s) - \sum\limits_{j = 1}^n {\ln (x_j ) - \sum\limits_{j - 1}^n {\ln (s_j )} } $$ where q = n + \(\sqrt n \) . We use this alternate form of Ye's algorithm to show that Ye's algorithm is optimal with respect to the choice of the parameterq in the following sense. Suppose thatq = n + n ^t wheret?0. Then the algorithm will solve the linear program in O(n ^r L) iterations, wherer = max{t, 1 ? t}. Thus the value oft that minimizes the complexity bound ist = 1/2, yielding Ye's O( \(\sqrt n \) L) iteration bound.     

L 2 existence theorems for the\bar \partial _b - Neumann problem on strongly pseudoconvex CR manifoldsproblem on strongly pseudoconvex CR manifolds

LetM be the boundary of a strongly pseudoconvex domain in \(\mathbb{C}^n \) ,n≥4 and ω be an open subset inM such that ?ω is the intersection ofM with a flat hypersurface. We establish theL ² existence theorems of the \(\bar \partial _b - Neumann\) problem on ω. In particular, we prove that the \(\bar \partial _b - Laplacian\) \(\square _b = \bar \partial _b \bar \partial _b^* + \bar \partial _b^* \bar \partial _b \) equipped with a pair of natural boundary conditions, the so-called \(\bar \partial _b - Neumann\) boundary conditions, has closed range when it acts on (0,q) forms, 1≤q≤n?3. Thus there exists a bounded inverse operator for \(\square _b \) , the \(\bar \partial _b - Neumann\) operatorN _b, and we have the following Hodge decomposition theorem on ω for \(\bar \partial _b \bar \partial _b^* N_b \alpha + \bar \partial _b^* \bar \partial _b N_b \alpha \) , for any (0,q) form α withL ²(ω) coefficients. The proof depends on theL ^p regularity of the tangential Cauchy-Riemann operators \(\bar \partial _b u = \alpha \) on ω?M under the compatibility condition \(\bar \partial _b \alpha = 0\) , where α is a (p, q) form on ω, where 1≤q≤n?2. The interior regularity ofN _b follows from the fact that \(\square _b \) is subelliptic in the interior of ω. The operatorN _b induces natural questions on the regularity up to the boundary ?ω. Near the characteristic point of the boundary, certain compatibility conditions will be present. In fact, one can show thatN _b is not a compact operator onL ²(ω).     

Limiting Behavior of High Order Correlations for Simple Random Sampling

For ${N = 1, 2,\ldots,}$ let S _N be a simple random sample of size n = n _N from a population A _N of size N, where ${0 \leq n \leq N}$ . Then with f _N =  n/N, the sampling fraction, and 1 _A the inclusion indicator that ${A \in S_N}$ , for any ${H \subset A_N}$ of size ${k \geq 0}$ , the high order correlations $${\rm Corr}(k) = E \big(\mathop{\Pi}\limits_{A \in H} ({\bf 1}_A - f_N )\big)$$ depend only on k, and if the sampling fraction ${f_N \rightarrow f}$ as ${N \rightarrow \infty}$ , then $$N^{k/2}{\rm Corr}(k) \rightarrow [f (f - 1)]^{k/2}EZ^{k}, k \,{\rm even}$$ and $$N^{(k+1)/2}{\rm Corr}(k) \rightarrow [f (f - 1)]^{(k-1)/2}(2f - 1)\frac{1}{3}(k - 1)EZ^{k+1}, k \,{\rm odd}$$ where Z is a standard normal random variable. This proves a conjecture given in [2].     

Mutually disjoint t-designs and t-SEEDs from extremal doubly-even self-dual codes

It is known that extremal doubly-even self-dual codes of length \(n\equiv 8\) or \(0\ (\mathrm {mod}\ 24)\) yield 3- or 5-designs respectively. In this paper, by using the generator matrices of bordered double circulant doubly-even self-dual codes, we give 3-(n, k; m)-SEEDs with (n, k, m) \(\in \{(32,8,5), (56,12,9), (56,16,9), (56,24,9), (80,16,52)\}\) . With the aid of computer, we obtain 22 generator matrices of bordered double circulant doubly-even self-dual codes of length 48, which enable us to get 506 mutually disjoint 5-(48, k, \(\lambda \) ) designs for (k, \(\lambda \) )=(12, 8),(16, 1356),(20, 36176). Moreover, this implies 5-(48, k; 506)-SEEDs for \(k=12, 16, 20, 24\) .     

Converting homotopies to isotopies and dividing homotopies in half in an effective way

We prove two theorems about homotopies of curves on two-dimensional Riemannian manifolds. We show that, for any \({\epsilon > 0}\) , if two simple closed curves are homotopic through curves of bounded length L, then they are also isotopic through curves of length bounded by \({L + \epsilon}\) . If the manifold is orientable, then for any \({\epsilon > 0}\) we show that, if we can contract a curve \({\gamma}\) traversed twice through curves of length bounded by L, then we can also contract \({\gamma}\) through curves bounded in length by \({L + \epsilon}\) . Our method involves cutting curves at their self-intersection points and reconnecting them in a prescribed way. We consider the space of all curves obtained in this way from the original homotopy, and use a novel approach to show that this space contains a path which yields the desired homotopy.     

Random and algebraic permutations’ statistics

An algebraic permutation $\hat{A}\in S(N=n^{m})$ is the permutation of the N points of the finite torus ? _n ^m , realized by a linear operator A∈SL(m,? _n ). The statistical properties of algebraic permutations are quite different from those of random permutations of N points. For instance, the period length T(A) grows superexponentially with N for some (random) permutations A of N elements, whereas $T(\hat{A})$ is bounded by a power of N for algebraic permutations  $\hat{A}$ . The paper also contains a strange mean asymptotics formula for the number of points of the finite projective line P¹(? _n ) in terms of the zeta function.     

On the greatest prime factor of ab + 1

We prove that whenever $ \mathcal{A} $ and $ \mathcal{B} $ are dense enough subsets of {1, ..., N}, there exist a ∈ $ \mathcal{A} $ and b ∈ $ \mathcal{B} $ such that the greatest prime factor of ab + 1 is at least $ N^{1 + |\mathcal{A}|/(9N)} $ .     

Flat orbits, minimal ideals and spectral synthesis

Let G = exp ${\mathfrak{g}}$ be a connected, simply connected, nilpotent Lie group and let ω be a continuous symmetric weight on G with polynomial growth. In the weighted group algebra ${L^{1}_{\omega}(G)}$ we determine the minimal ideal of given hull ${\{\pi_{l'} \in \hat{G} | l' \in l + \mathfrak{n}^{\perp}\}}$ , where ${\mathfrak{n}}$ is an ideal contained in ${\mathfrak{g}(l)}$ , and we characterize all the L ^∞(G/N)-invariant ideals (where ${N = {\rm exp}\, \mathfrak{n}}$ ) of the same hull. They are parameterized by a set of G-invariant, translation invariant spaces of complex polynomials on N dominated by ω and are realized as kernels of specially built induced representations. The result is particularly simple if the co-adjoint orbit of l is flat.     

Isometric embeddings of \mathbb{Z}_{p^k} in the Hamming space \mathbb{F}_{p}^{N} and \mathbb{Z}_{p^k}-linear codes

Isometric embeddings of $\mathbb{Z}_{p^n+1}$ into the Hamming space ( $\mathbb{F}_{p}^{p^n},w$ ) have played a fundamental role in recent constructions of non-linear codes. The codes thus obtained are very good codes, but their rate is limited by the rate of the first-order generalized Reed–Muller code—hence, when n is not very small, these embeddings lead to the construction of low-rate codes. A natural question is whether there are embeddings with higher rates than the known ones. In this paper, we provide a partial answer to this question by establishing a lower bound on the order of a symmetry of ( $\mathbb{F}_{p}^{N},w$ ).