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.     

Nef line bundles on flag bundles on a curve over {\overline{{\mathbb F}}_p}

Let E be a vector bundle of rank r over an irreducible smooth projective curve X defined over the field ${\overline{{\mathbb F}}_p}$ F ¯ p . For fixed integers ${r_1\, , \ldots\, , r_\nu}$ r 1 , ... , r ν with ${1\, \leq\, r_1\, <\, \cdots\, <\, r_\nu\, <\, r}$ 1 ≤ r 1 < ? < r ν < r , let ${\text{Fl}(E)}$ Fl ( E ) be the corresponding flag bundle over X associated to E. Let ${\xi\, \longrightarrow \, {\rm Fl}(E)}$ ξ ? Fl ( E ) be a line bundle such that for every pair of the form ${(C\, ,\phi)}$ ( C , ? ) , where C is an irreducible smooth projective curve defined over ${\overline{\mathbb F}_p}$ F ¯ p and ${\phi\, :\, C\, \longrightarrow\, {\rm Fl}(E)}$ ? : C ? Fl ( E ) is a nonconstant morphism, the inequality ${{\rm degree}(\phi^* \xi)\, > \, 0}$ degree ( ? ? ξ ) > 0 holds. We prove that the line bundle ${\xi}$ ξ is ample.     

Discrepancy, separation and Riesz energy of finite point sets on the unit sphere

For $d \geqslant 2,$ we consider asymptotically equidistributed sequences of $\mathbb S^d$ codes, with an upper bound $\operatorname{\boldsymbol{\delta}}$ on spherical cap discrepancy, and a lower bound Δ on separation. For such sequences, if 0?<?s?<?d, then the difference between the normalized Riesz s energy of each code, and the normalized s-energy double integral on the sphere is bounded above by $\operatorname{O}\big(\operatorname{\boldsymbol{\delta}}^{1-s/d}\,\Delta^{-s}\,N^{-s/d}\big),$ where N is the number of code points. For well separated sequences of spherical codes, this bound becomes $\operatorname{O}\big(\operatorname{\boldsymbol{\delta}}^{1-s/d}\big).$ We apply these bounds to minimum energy sequences, sequences of well separated spherical designs, sequences of extremal fundamental systems, and sequences of equal area points.     

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\) .     

Computational results of duadic double circulant codes

Quadratic residue codes have been one of the most important classes of algebraic codes. They have been generalized into duadic codes and quadratic double circulant codes. In this paper we introduce a new subclass of double circulant codes, called duadic double circulant codes, which is a generalization of quadratic double circulant codes for prime lengths. This class generates optimal self-dual codes, optimal linear codes, and linear codes with the best known parameters in a systematic way. We describe a method to construct duadic double circulant codes using 4-cyclotomic cosets and give certain duadic double circulant codes over $\mathbb{F}_{2}$ , $\mathbb{F}_{3}$ , $\mathbb{F}_{4}$ , $\mathbb{F}_{5}$ , and $\mathbb{F}_{7}$ . In particular, we find a new ternary self-dual [76,38,18] code and easily rediscover optimal binary self-dual codes with parameters [66,33,12], [68,34,12], [86,43,16], and [88,44,16] as well as a formally self-dual binary [82,41,14] code.     

Approximating Tverberg Points in Linear Time for Any Fixed Dimension

Let $P \subseteq \mathbb{R }^d$ P ? R d be a $d$ d -dimensional $n$ n -point set. A Tverberg partition is a partition of $P$ P into $r$ r sets $P_1, \dots , P_r$ P 1 , ? , P r such that the convex hulls $\hbox {conv}(P_1), \dots , \hbox {conv}(P_r)$ conv ( P 1 ) , ? , conv ( P r ) have non-empty intersection. A point in $\bigcap _{i=1}^{r} \hbox {conv}(P_i)$ ? i = 1 r conv ( P i ) is called a Tverberg point of depth $r$ r for $P$ P . A classic result by Tverberg shows that there always exists a Tverberg partition of size $\lceil n/(d+1) \rceil $ ? n / ( d + 1 ) ? , but it is not known how to find such a partition in polynomial time. Therefore, approximate solutions are of interest. We describe a deterministic algorithm that finds a Tverberg partition of size $\lceil n/4(d+1)^3 \rceil $ ? n / 4 ( d + 1 ) 3 ? in time $d^{O(\log d)} n$ d O ( log d ) n . This means that for every fixed dimension we can compute an approximate Tverberg point (and hence also an approximate centerpoint) in linear time. Our algorithm is obtained by combining a novel lifting approach with a recent result by Miller and Sheehy (Comput Geom Theory Appl 43(8):647–654, 2010).     

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 ²).     

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 .     

A Clifford Bundle Approach to the Differential Geometry of Branes

We first recall using the Clifford bundle formalism (CBF) of differential forms and the theory of extensors acting on \({\mathcal{C}\ell}\) (M, g) (the Clifford bundle of differential forms) the formulation of the intrinsic geometry of a differential manifold M equipped with a metric field g of signature (p, q) and an arbitrary metric compatible connection \({\nabla}\) introducing the torsion (2?1)-extensor field \({\tau}\) , the curvature (2 ? 2) extensor field \({\Re}\) and (once fixing a gauge) the connection (1?2)-extensor \({\omega}\) and the Ricci operator \({\partial \bigwedge \partial}\) (where \({\partial}\) is the Dirac operator acting on sections of \({\mathcal{C}\ell(M, g)}\) ) which plays an important role in this paper. Next, using the CBF we give a thoughtful presentation the Riemann or the Lorentzian geometry of an orientable submanifold M (dim M =  m) living in a manifold M? (such that M? \({\simeq \mathbb{R}^n}\) is equipped with a semi- Riemannian metric g? with signature (p?, q?) and p?+q? = n and its Levi- Civita connection D?) and where there is defined a metric g =  i*g?, where \({i : M \rightarrow}\) M? is the inclusion map. We prove several equivalent forms for the curvature operator \({\Re}\) of M. Moreover we show a very important result, namely that the Ricci operator of M is the (negative) square of the shape operator S of M (object obtained by applying the restriction on M of the Dirac operator ?? of \({\mathcal{C}\ell}\) (M?, g?) to the projection operator P). Also we disclose the relationship between the (1?2)-extensor \({\omega}\) and the shape biform \({\mathcal{S}}\) (an object related to S). The results obtained are used to give a mathematical formulation to Clifford’s theory of matter. It is hoped that our presentation will be useful for differential geometers and theoretical physicists interested, e.g., in string and brane theories and relativity theory by divulging, improving and expanding very important and so far unfortunately largely ignored results appearing in reference [13].     

On permutations of central quadrics which preserve an inner distance

Letq be a regular quadratic form on a vector space (V, $\mathbb{F}$ ) and assume dimV ≥ 4 and ¦ $\mathbb{F}$ ¦ ≥ 4. We consider a permutation ? of the central affine quadric $\mathcal{F}$ := {x εV ¦q(x) = 1} such that $$(*)x \cdot y = \mu \Leftrightarrow x^\varphi \cdot y^\varphi = \mu \forall x,y\varepsilon \mathcal{F}$$ holds true, where μ is a fixed element of $\mathbb{F}$ and where “·” is the scalar product associated withq. We prove that ? is induced (in a certain sense) by a semi-linear bijection (σ,?): (V, $\mathbb{F}$ ) → (V, $\mathbb{F}$ ) such thatq o ?o q, provided $\mathcal{F}$ contains lines and the pair (μ, $\mathbb{F}$ ) has additional properties if there ar no planes in $\mathcal{F}$ . The cases μ,≠ 0 and μ = 0 require different techniques.     

On Some Noteworthy Pairs of Ideals in Mod-R

An additive functor $F \colon {\mathcal A}\to{\mathcal B}$ between preadditive categories $\mathcal A$ and $\mathcal B$ is said to be a local functor if, for every morphism $f\colon A\to A'$ in $\mathcal A$ , F(f) isomorphism in $\mathcal B$ implies f isomorphism in $\mathcal A$ . We show that there exist several pairs $(\mathcal I_1,\mathcal I_2)$ of ideals of $\mathcal A$ for which the canonical functor $\mathcal A\to\mathcal A/\mathcal I_1\times \mathcal A/\mathcal I_2$ is a local functor. In most of our examples, the category $\mathcal A$ is a full subcategory of the category Mod?-R of all right modules over a ring R. These pairs of ideals arise in a surprisingly natural way and enjoy several properties. Ideals are kernels of functors, and most of our examples of ideals are kernels of important and well studied functors. E.g., (1) the kernel Δ of the canonical functor P of Mod?-R into its spectral category Spec(Mod?-R), so that Δ is the ideal of all morphisms with an essential kernel; (2) the kernel Σ of the dual functor F of P, so that Σ is the ideal of all morphisms with a superfluous image; (3) the kernels Δ⁽¹⁾ and Σ₍₁₎ of the first derived functors P ⁽¹⁾ and F ₍₁₎ of P and F, respectively; (4) the kernels of suitable functors Hom and ? and their first derived functors ${\rm Ext}^1_R$ and ${\rm Tor}^R_1$ .     

Bounds for codes and designs in complex subspaces

We introduce the concepts of complex Grassmannian codes and designs. Let $\mathcal{G}_{m,n}$ denote the set of m-dimensional subspaces of ? ⁿ : then a code is a finite subset of $\mathcal{G}_{m,n}$ in which few distances occur, while a design is a finite subset of $\mathcal{G}_{m,n}$ that polynomially approximates the entire set. Using Delsarte’s linear programming techniques, we find upper bounds for the size of a code and lower bounds for the size of a design, and we show that association schemes can occur when the bounds are tight. These results are motivated by the bounds for real subspaces recently found by Bachoc, Bannai, Coulangeon and Nebe, and the bounds generalize those of Delsarte, Goethals and Seidel for codes and designs on the complex unit sphere.     

Classification and nonexistence results for linear codes with prescribed minimum distances

Starting from a linear [n, k, d] _q code with dual distance ${d^{\bot}}$ , we may construct an ${[n - d^\bot, k - d^\bot +1,\geq d]_q}$ code with dual distance at least ${\left\lceil\frac{d^\bot}{q}\right\rceil}$ using construction Y ₁. The inverse construction gives a rule for the classification of all [n, k, d] _q codes with dual distance ${d^{\bot}}$ by adding ${d^\bot}$ further columns to the parity check matrices of the smaller codes. Isomorph rejection is applied to guarantee a small search space for this iterative approach. Performing a complete search based on this observation, we are able to prove the nonexistence of linear codes for 16 open parameter sets [n, k, d] _q , q =  2, 3, 4, 5, 7, 8. These results imply 217 new upper bounds in the known tables for the minimum distance of linear codes and establish the exact value in 109 cases.     

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$ ).     

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}$ .     

Classification of hypersurfaces with constant M?bius curvature in {\mathbb{S}^{m+1}}

Let ${x: M^{m} \rightarrow \mathbb{S}^{m+1}}$ be an m-dimensional umbilic-free hypersurface in an (m?+?1)-dimensional unit sphere ${\mathbb{S}^{m+1}}$ , with standard metric I?= dx · dx. Let II be the second fundamental form of isometric immersion x. Define the positive function ${\rho=\sqrt{\frac{m}{m-1}}\|II-\frac{1}{m}tr(II)I\|}$ . Then positive definite (0,2) tensor ${\mathbf{g}=\rho^{2}I}$ is invariant under conformal transformations of ${\mathbb{S}^{m+1}}$ and is called M?bius metric. The curvature induced by the metric g is called M?bius curvature. The purpose of this paper is to classify the hypersurfaces with constant M?bius curvature.     

Sporadic neighbour-transitive codes in Johnson graphs

We classify the neighbour-transitive codes in Johnson graphs $J(v,k)$ of minimum distance at least three which admit a neighbour-transitive group of automorphisms that is an almost simple two-transitive group of degree $v$ and does not occur in an infinite family of two-transitive groups. The result of this classification is a table of 22 codes with these properties. Many have relatively large minimum distance in comparison to their length $v$ and number of code words. We construct an additional five neighbour-transitive codes with minimum distance two admitting such a group. All 27 codes are $t$ -designs with $t$ at least two.     

Duality of weighted anisotropic Besov and Triebel–Lizorkin spaces

Let A be an expansive dilation on ${{\mathbb R}^n}$ and w a Muckenhoupt ${\mathcal A_\infty(A)}$ weight. In this paper, for all parameters ${\alpha\in{\mathbb R} }$ and ${p,q\in(0,\infty)}$ , the authors identify the dual spaces of weighted anisotropic Besov spaces ${\dot B^\alpha_{p,q}(A;w)}$ and Triebel?CLizorkin spaces ${\dot F^\alpha_{p,q}(A;w)}$ with some new weighted Besov-type and Triebel?CLizorkin-type spaces. The corresponding results on anisotropic Besov spaces ${\dot B^\alpha_{p,q}(A; \mu)}$ and Triebel?CLizorkin spaces ${\dot F^\alpha_{p,q}(A; \mu)}$ associated with ${\rho_A}$ -doubling measure??? are also established. All results are new even for the classical weighted Besov and Triebel?CLizorkin spaces in the isotropic setting. In particular, the authors also obtain the ${\varphi}$ -transform characterization of the dual spaces of the classical weighted Hardy spaces on ${{\mathbb R}^n}$ .     

Changing-sign bubble solutions for an anisotropic sinh-Poisson equation

We consider the following anisotropic sinh-Poisson equation $${\rm div} (a(x) \nabla u)+ 2\varepsilon^2 a(x) {\rm sinh}\,u=0\ \ {\rm in}\ \Omega, \quad u=0 \ \ {\rm on}\ \partial \Omega,$$ where ${\Omega \subset \mathbb{R}^2}$ is a bounded smooth domain and a(x) is a positive smooth function. We investigate the effect of anisotropic coefficient ${a(x)}$ on the existence of bubbling solutions. We show that there exists a family of solutions u _?? concentrating positively and negatively at ${\bar{x}}$ , a given local critical point of a(x), for ?? sufficiently small, for which with the property $$2\varepsilon^2a(x){\rm sinh} u_\varepsilon \rightharpoonup 8\pi\sum\limits_{j=1}^{m}b_j\delta_{\bar{x}},$$ where ${b_j=\pm 1}$ . This result shows a striking difference with the isotropic case (a(x) ?? Constant) in Bartolucci and Pistoia (IMA J Appl Math 72(6):706?C729, 2007), Jost et?al. (Calc Var Partial Differ Equ 31:263?C276, 2008) and Esposito and Wei (Calc Var Partial Differ Equ 34:341?C375, 2009).