skip to main content


This content will become publicly available on June 1, 2025

Title: On the generalized Hamming weights of hyperbolic codes

[Formula: see text]A hyperbolic code is an evaluation code that improves a Reed–Muller code because the dimension increases while the minimum distance is not penalized. We give necessary and sufficient conditions, based on the basic parameters of the Reed–Muller code, to determine whether a Reed–Muller code coincides with a hyperbolic code. Given a hyperbolic code [Formula: see text], we find the largest Reed–Muller code contained in [Formula: see text] and the smallest Reed–Muller code containing [Formula: see text]. We then prove that similar to Reed–Muller and affine Cartesian codes, the [Formula: see text]th generalized Hamming weight and the [Formula: see text]th footprint of the hyperbolic code coincide. Unlike for Reed–Muller and affine Cartesian codes, determining the [Formula: see text]th footprint of a hyperbolic code is still an open problem. We give upper and lower bounds for the [Formula: see text]th footprint of a hyperbolic code that, sometimes, are sharp.

 
more » « less
Award ID(s):
2201094
PAR ID:
10523653
Author(s) / Creator(s):
; ; ; ; ;
Publisher / Repository:
World Scientific
Date Published:
Journal Name:
Journal of Algebra and Its Applications
Volume:
23
Issue:
07
ISSN:
0219-4988
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. A collection of sets displays aproximity gapwith respect to some property if for every set in the collection, either (i) all members areδ-close to the property in relative Hamming distance or (ii) only a tiny fraction of members areδ-close to the property. In particular, no set in the collection has roughly half of its membersδ-close to the property and the othersδ-far from it.

    We show that the collection of affine spaces displays a proximity gap with respect to Reed–Solomon (RS) codes, even over small fields, of size polynomial in the dimension of the code, and the gap applies to anyδsmaller than the Johnson/Guruswami–Sudan list-decoding bound of the RS code. We also show near-optimal gap results, over fields of (at least)linearsize in the RS code dimension, forδsmaller than the unique decoding radius. Concretely, ifδis smaller than half the minimal distance of an RS code\(V\subset {\mathbb {F}}_q^n \), every affine space is either entirelyδ-close to the code, or alternatively at most an (n/q)-fraction of it isδ-close to the code. Finally, we discuss several applications of our proximity gap results to distributed storage, multi-party cryptographic protocols, and concretely efficient proof systems.

    We prove the proximity gap results by analyzing the execution of classical algebraic decoding algorithms for Reed–Solomon codes (due to Berlekamp–Welch and Guruswami–Sudan) on aformal elementof an affine space. This involves working with Reed–Solomon codes whose base field is an (infinite) rational function field. Our proofs are obtained by developing an extension (to function fields) of a strategy of Arora and Sudan for analyzing low-degree tests.

     
    more » « less
  2. In this paper, we use the [Formula: see text]-spin theorem to show that the Davis hyperbolic 4-manifold admits harmonic spinors. This is the first example of a closed hyperbolic [Formula: see text]-manifold that admits harmonic spinors. We also explicitly describe the spinor bundle of a spin hyperbolic 2- or 4-manifold and show how to calculated the subtle sign terms in the [Formula: see text]-spin theorem for an isometry, with isolated fixed points, of a closed spin hyperbolic 2- or 4-manifold. 
    more » « less
  3. Abstract

    CSS-T codes were recently introduced as quantum error-correcting codes that respect a transversal gate. A CSS-T code depends on a CSS-T pair, which is a pair of binary codes$$(C_1, C_2)$$(C1,C2)such that$$C_1$$C1contains$$C_2$$C2,$$C_2$$C2is even, and the shortening of the dual of$$C_1$$C1with respect to the support of each codeword of$$C_2$$C2is self-dual. In this paper, we give new conditions to guarantee that a pair of binary codes$$(C_1, C_2)$$(C1,C2)is a CSS-T pair. We define the poset of CSS-T pairs and determine the minimal and maximal elements of the poset. We provide a propagation rule for nondegenerate CSS-T codes. We apply some main results to Reed–Muller, cyclic and extended cyclic codes. We characterize CSS-T pairs of cyclic codes in terms of the defining cyclotomic cosets. We find cyclic and extended cyclic codes to obtain quantum codes with better parameters than those in the literature.

     
    more » « less
  4. null (Ed.)
    A collection of sets displays a proximity gap with respect to some property if for every set in the collection, either (i) all members are δ-close to the property in relative Hamming distance or (ii) only a tiny fraction of members are δ-close to the property. In particular, no set in the collection has roughly half of its members δ-close to the property and the others δ-far from it. We show that the collection of affine spaces displays a proximity gap with respect to Reed-Solomon (RS) codes, even over small fields, of size polynomial in the dimension of the code, and the gap applies to any δ smaller than the Johnson/Guruswami-Sudan list-decoding bound of the RS code. We also show near-optimal gap results, over fields of (at least) linear size in the RS code dimension, for δ smaller than the unique decoding radius. Concretely, if δ is smaller than half the minimal distance of an RS code V ⊂ Fq n , every affine space is either entirely δ-close to the code, or alternatively at most an ( n/q)-fraction of it is δ-close to the code. Finally, we discuss several applications of our proximity gap results to distributed storage, multi-party cryptographic protocols, and concretely efficient proof systems. We prove the proximity gap results by analyzing the execution of classical algebraic decoding algorithms for Reed-Solomon codes (due to Berlekamp-Welch and Guruswami-Sudan) on a formal element of an affine space. This involves working with Reed-Solomon codes whose base field is an (infinite) rational function field. Our proofs are obtained by developing an extension (to function fields) of a strategy of Arora and Sudan for analyzing low-degree tests. 
    more » « less
  5. World Scientific (Ed.)
    In general, it is difficult to measure distances in the Weil–Petersson metric on Teichmüller space. Here we consider the distance between strata in the Weil–Petersson completion of Teichmüller space of a surface of finite type. Wolpert showed that for strata whose closures do not intersect, there is a definite separation independent of the topology of the surface. We prove that the optimal value for this minimal separation is a constant [Formula: see text] and show that it is realized exactly by strata whose nodes intersect once. We also give a nearly sharp estimate for [Formula: see text] and give a lower bound on the size of the gap between [Formula: see text] and the other distances. A major component of the paper is an effective version of Wolpert’s upper bound on [Formula: see text], the inner product of the Weil–Petersson gradient of length functions. We further bound the distance to the boundary of Teichmüller space of a hyperbolic surface in terms of the length of the systole of the surface. We also obtain new lower bounds on the systole for the Weil–Petersson metric on the moduli space of a punctured torus. 
    more » « less