Obstructions to convexity in neural codes

How does the brain encode spatial structure? One way is through hippocampal neurons called place cells, which become associated to convex regions of space known as their receptive fields: each place cell fires at a high rate precisely when the animal is in the receptive field. The firing patterns of multiple place cells form what is known as a convex neural code. How can we tell when a neural code is convex? To address this question, Giusti and Itskov identified a local obstruction, defined via the topology of a code's simplicial complex, and proved that convex neural codes have no local obstructions. Curto et al. proved the converse for all neural codes on at most four neurons. Via a counterexample on five neurons, we show that this converse is false in general. Additionally, we classify all codes on five neurons with no local obstructions. This classification is enabled by our enumeration of connected simplicial complexes on 5 vertices up to isomorphism. Finally, we examine how local obstructions are related to maximal codewords (maximal sets of neurons that co-fire). Curto et al. proved that a code has no local obstructions if and only if it contains certain “mandatory” intersections of maximal codewords. We give a new criterion for an intersection of maximal codewords to be non-mandatory, and prove that it classifies all such non-mandatory codewords for codes on up to five neurons.     

Non-invertible-element constacyclic codes over finite PIRs

In this paper we introduce the notion of λ-constacyclic codes over finite rings R for arbitrary element λ of R. We study the non-invertible-element constacyclic codes (NIE-constacyclic codes) over finite principal ideal rings (PIRs). We determine the algebraic structures of all NIE-constacyclic codes over finite chain rings, give the unique form of the sets of the defining polynomials and obtain their minimum Hamming distances. A general form of the duals of NIE-constacyclic codes over finite chain rings is also provided. In particular, we give a necessary and sufficient condition for the dual of an NIE-constacyclic code to be an NIE-constacyclic code. Using the Chinese Remainder Theorem, we study the NIE-constacyclic codes over finite PIRs. Furthermore, we construct some optimal NIE-constacyclic codes over finite PIRs in the sense that they achieve the maximum possible minimum Hamming distances for some given lengths and cardinalities.     

Completely simple codes

A code X is said to be completely simple if the kernel of the syntactic monoid of X ^? is a completely simple semigroup. This class of codes is a common generalization of two important classes of codes, that is, thin codes and group codes, and has remarkable algebraic and combinatorial properties. In this paper, we give systematic characterizations of completely simple codes and, in particular, show that many fundamental properties of thin codes are preserved in this generalization.     

Determinantal representations and Bézoutians

A major open question in convex algebraic geometry is whether all hyperbolicity cones are spectrahedral, i.e. the solution sets of linear matrix inequalities. We will use sum-of-squares decompositions of certain bilinear forms called Bézoutians to approach this problem. More precisely, we show that for every smooth hyperbolic polynomial h there is another hyperbolic polynomial q such that \(q \cdot h\) has a definite determinantal representation. Besides commutative algebra, the proof relies on results from real algebraic geometry.     

On non-antipodal binary completely regular codes

Binary non-antipodal completely regular codes are characterized. Using a result on nonexistence of nontrivial binary perfect codes, it is concluded that there are no unknown nontrivial non-antipodal completely regular binary codes with minimum distance d?3. The only such codes are halves and punctured halves of known binary perfect codes. Thus, new such codes with covering radius ρ=6 and 7 are obtained. In particular, a half of the binary Golay [23,12,7]-code is a new binary completely regular code with minimum distance d=8 and covering radius ρ=7. The punctured half of the Golay code is a new completely regular code with minimum distance d=7 and covering radius ρ=6. The new code with d=8 disproves the known conjecture of Neumaier, that the extended binary Golay [24,12,8]-code is the only binary completely regular code with d?8. Halves of binary perfect codes with Hamming parameters also provide an infinite family of binary completely regular codes with d=4 and ρ=3. Puncturing of these codes also provide an infinite family of binary completely regular codes with d=3 and ρ=2. Both these families of codes are well known, since they are uniformly packed in the narrow sense, or extended such codes. Some of these completely regular codes are new completely transitive codes.     

On the Cyclicity of Goppa Codes,Parity-Check Subcodes of Goppa Codes,and Extended Goppa Codes

Classical Goppa codes are a special case of Alternant codes. First we prove that the parity-check subcodes of Goppa codes and the extended Goppa codes are both Alternant codes. Before this paper, all known cyclic Goppa codes were some particular BCH codes. Many families of Goppa codes with a cyclic extension have been found. All these cyclic codes are in fact Alternant codes associated to a cyclic Generalized Reed–Solomon code. In (1989, J. Combin. Theory Ser. A 51, 205–220) H. Stichtenoth determined all cyclic extended Goppa codes with this property. In a recent paper (T. P. Berger, 1999, in “Finite Fields: Theory, Applications and Algorithms (R. Mullin and G. Mullen, Eds.), pp. 143–154, Amer. Math. Soc., Providence), we used some semi-linear transformations on GRS codes to construct cyclic Alternant codes that are not associated to cyclic GRS codes. In this paper, we use these results to construct cyclic Goppa codes that are not BCH codes, new families of Goppa codes with a cyclic extension, and some families of non-cyclic Goppa codes with a cyclic parity-check subcode.     

On Scattered Convex Geometries

A convex geometry is a closure space satisfying the anti-exchange axiom. For several types of algebraic convex geometries we describe when the collection of closed sets is order scattered, in terms of obstructions to the semilattice of compact elements. In particular, a semilattice Ω(η), that does not appear among minimal obstructions to order-scattered algebraic modular lattices, plays a prominent role in convex geometries case. The connection to topological scatteredness is established in convex geometries of relatively convex sets.     

Quasi-cyclic codes with cyclic constituent codes

Ling and Solé [S. Ling, P. Solé, On the algebraic structure of quasi-cyclic codes I: Finite fields, IEEE Trans. Inform. Theory 47 (2001) 2751–2760] showed that every quasi-cyclic code C is constructed from shorter linear codes which are called the constituent codes of C. Given a quasi-cyclic code C of length ℓm and index ℓ with m being pairwise coprime to ℓ and the order of the field C is over, if all its constituent codes are cyclic with their zeroes having full multiplicity, C is then shown to be equivalent to a cyclic code whose zeroes with their multiplicities are fully described in terms of the nonzeroes of the cyclic constituent codes. The general transformation to obtain the above-mentioned equivalent cyclic code is also explicitly given. The approach adopted here follows the approach used by A.M.A. Natividad [A.M.A. Natividad, PhD thesis, Department of Mathematics, University of Philippines Diliman, The Philippines, 2004] and uses the generalized discrete Fourier transform on the algebraic structure of the class of quasi-cyclic codes developed by Ling and Solé [S. Ling, P. Solé, On the algebraic structure of quasi-cyclic codes I: Finite fields, IEEE Trans. Inform. Theory 47 (2001) 2751–2760].     

Analogues of the central point theorem for families with d-intersection property in ℝ d

In this paper we consider families of compact convex sets in ? ^d such that any subfamily of size at most d has a nonempty intersection. We prove some analogues of the central point theorem and Tverberg’s theorem for such families.     

A class of uniform functions and its relationship with the class of measurable functions

Borel, Lebesgue, and Hausdorff described all uniformly closed families of real-valued functions on a set T whose algebraic properties are just like those of the set of all continuous functions with respect to some open topology on T. These families turn out to be exactly the families of all functions measurable with respect to some σ-additive and multiplicative ensembles on T. The problem of describing all uniformly closed families of bounded functions whose algebraic properties are just like those of the set of all continuous bounded functions remained unsolved. In the paper, a solution of this problem is given with the help of a new class of functions that are uniform with respect to some multiplicative families of finite coverings on T. It is proved that the class of uniform functions differs from the class of measurable functions.     

Weighted external difference families and R-optimal AMD codes

In this paper, we provide a mathematical framework for characterizing AMD codes that are R-optimal. We introduce a new combinatorial object, the reciprocally-weighted external difference family (RWEDF), which corresponds precisely to an R-optimal weak AMD code. This definition subsumes known examples of existing optimal codes, and also encompasses combinatorial objects not covered by previous definitions in the literature. By developing structural group-theoretic characterizations, we exhibit infinite families of new RWEDFs, and new construction methods for known objects such as near-complete EDFs. Examples of RWEDFs in non-abelian groups are also discussed.     

Cyclotomic construction of strong external difference families in finite fields

Strong external difference families (SEDFs) and their generalizations GSEDFs and BGSEDFs in a finite abelian group G are combinatorial designs introduced by Paterson and Stinson (Discret Math 339: 2891–2906, 2016) and have applications in communication theory to construct optimal strong algebraic manipulation detection codes. In this paper we firstly present some general constructions of these combinatorial designs by using difference sets and partial difference sets in G. Then, as applications of the general constructions, we construct series of SEDF, GSEDF and BGSEDF in finite fields by using cyclotomic classes. Particularly, we present an \((n,m,k,\lambda )=(243,11,22,20)\)-SEDF in \((\mathbb {F}_q,+)\ (q=3^5=243)\) by using the cyclotomic classes of order 11 in \(\mathbb {F}_q\) which answers an open problem raised in Paterson and Stinson (2016).     

List signature schemes

A group signature scheme allows group members to issue signatures on behalf of the group, while hiding for each signature which group member actually issued it. Such scheme also involves a group manager, who is able to open any group signature by showing which group member issued it.We introduce the concept of list signatures as a variant of group signatures which sets a limit on the number of signatures each group member may issue. These limits must be enforced without having the group manager open signatures of honest group members—which excludes the trivial solution in which the group manager opens every signature to see whether some group members exceed their limits. Furthermore, we consider the problem of publicly identifying group members who exceed their limits, also without involving the group manager.     

A q-polynomial approach to constacyclic codes

As a generalization of cyclic codes, constacyclic codes is an important and interesting class of codes due to their nice algebraic structures and various applications in engineering. This paper is devoted to the study of the q-polynomial approach to constacyclic codes. Fundamental theory of this approach will be developed, and will be employed to construct some families of optimal and almost optimal codes in this paper.     

Unconditionally τ-closed and τ-algebraic sets in groups

Families of unconditionally τ-closed and τ-algebraic sets in a group are defined, which are natural generalizations of unconditionally closed and algebraic sets defined by Markov. A sufficient condition for the coincidence of these families is found. In particular, it is proved that these families coincide in any group of cardinality at most τ. This result generalizes both Markov's theorem on the coincidence of unconditionally closed and algebraic sets in a countable group (as is known, they may be different in an uncountable group) and Podewski's theorem on the topologizability of any ungebunden group.     

On the closedness of the algebraic difference of closed convex sets

We characterize in a reflexive Banach space all the closed convex sets C₁ containing no lines for which the condition C₁^∞∩C₂^∞={0} ensures the closedness of the algebraic difference C₁−C₂ for all closed convex sets C₂. We also answer a closely related problem: determine all the pairs C₁, C₂ of closed convex sets containing no lines such that the algebraic difference of any sufficiently small uniform perturbations of C₁ and C₂ remains closed. As an application, we state the broadest setting for the strict separation theorem in a reflexive Banach space.     

Bounds for the Multicovering Radii of Reed-Muller Codes with Applications to Stream Ciphers

The multicovering radii of a code are recentgeneralizations of the covering radius of a code. For positivem, the m-covering radius of C is the leastradius t such that everym-tuple of vectors is contained in at least one ball of radiust centered at some codeword. In this paper upper bounds arefound for the multicovering radii of first order Reed-Muller codes. These bounds generalize the well-known Norse bounds for the classicalcovering radii of first order Reed-Muller codes. They are exactin some cases. These bounds are then used to prove the existence of secure families of keystreams against a general class of cryptanalytic attacks. This solves the open question that gave rise to the study ofmulticovering radii of codes.     

Feasibility in reverse convex mixed-integer programming

In this paper we address the problem of the infeasibility of systems defined by reverse convex inequality constraints, where some or all of the variables are integer. In particular, we provide a polynomial algorithm that identifies a set of all constraints critical to feasibility (CF), that is constraints that may affect a feasibility status of the system after some perturbation of the right-hand sides. Furthermore, we will investigate properties of the irreducible infeasible sets and infeasibility sets, showing in particular that every irreducible infeasible set as well as infeasibility sets in the considered system, are subsets of the set CF of constraints critical to feasibility.