ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.617235 J. Algebra Comb. Discrete Appl. 6(3) • 135–145 Received: 15 January 2018 Accepted: 23 July 2019 0 Journal of Algebra Combinatorics Discrete Structures and Applications Asymptotically good homological error correcting codes Research Article Jason McCullough∗, Heather Newman Abstract: Let ∆ be an abstract simplicial complex. We study classical homological error correcting codes associated to ∆, which generalize the cycle codes of simple graphs. It is well-known that cycle codes of graphs do not yield asymptotically good families of codes. We show that asymptotically good families of codes do exist for homological codes associated to simplicial complexes of dimension at least 2. We also prove general bounds and formulas for (co-)cycle and (co-)boundary codes for arbitrary simplicial complexes over arbitrary fields. 2010 MSC: 94B25, 05E45 Keywords: Error correcting codes, Simplicial complexes, Simplicial homology 1. Introduction Fix a field (usually finite) K. Given an abstract simplicial complex ∆, one can define the reduced chain complex of ∆ with coefficients in K, which naturally defines the cycles, boundaries and homology of ∆. These are the classical homological codes, seemingly first studied by Salzer [10]. In the case when ∆ is a one-dimensional simplicial complex, ∆ may be viewed as a simple graph. Since the Moore bound gives a logarithmic bound on the girth of a graph in terms of the number of edges and vertices, it follows that one cannot define asymptotically good families of codes from cycle codes of graphs. By applying recent work in [4] and [2], we show in Theorem 4.2 that one can define asymptotically good families of codes from cycle codes of simplicial complexes of dimension two or higher. The paper is organized as follows: Section 2 gathers preliminary results, definitions and related work. Section 3 contains our results about arbitrary homological codes over arbitrary fields. In it we recover the parameters for the ith cycle and boundary codes (and their duals) of a simplex of arbitrary dimension. This was previously done in [10] and [13] over F2. Section 4 contains our main results on the existence of asymptotically good homological codes. ∗ This author was supported by a grant from the Simons Foundation (576107, JGM). Jason McCullough(Corresponding Author); Department of Mathematics, Iowa State University,Ames, Iowa 50011, United States (email: jmccullo@iastate.edu). Heather Newman; Department of Mathematics, Drexel University, Philadelphia, PA 19104, United States (email: hn385@drexel.edu). 135 J. McCullough, H. Newman / J. Algebra Comb. Discrete Appl. 6(3) (2019) 135–145 2. Preliminaries 2.1. Simplicial complexes Let ∆ be an abstract simplicial complex on vertex set [m] := {1, . . . ,m}; that is, ∆ is a collection of subsets of [m], closed under taking subsets. Elements σ ∈ ∆ are called faces or simplices. Maximal faces are called facets. We note that ∆ is determined by its facets. For σ ∈ ∆, we define the dimension of σ by setting dim(σ) = |σ|−1. Thus dim(∅) = −1. Then the dimension of ∆ is dim(∆) = max{dim(σ) |σ ∈ ∆}. We denote by ∆i the set of i-dimensional faces of ∆, called the i-skeleton of ∆, and call an element of ∆i an i-face. An m-simplex is then a simplicial complex on [m + 1] consisting of all possible facets with one m-dimensional facet. Set fi(∆) to be the number of i-faces, that is, fi(∆) = |∆i|. The vector (f−1(∆),f0(∆),f1(∆), . . . ,fdim(∆)(∆)) is called the f-vector of ∆. We sometimes refer to 0-faces as vertices and 1-faces as edges. We say that an i-face σ ∈ ∆i has degree r if σ is contained in exactly r many (i+ 1)-faces of ∆; that is, deg(σ) = ∣∣{τ ∈ ∆i+1 : σ ⊂ τ}∣∣ . Finally we define the i-degree of ∆ to be deg(i, ∆) = min{deg(σ) |σ ∈ ∆i}. Thus deg(1, ∆) is just the minimal degree of a vertex of the 1-skeleton of ∆ viewed as a simple graph. Over any field K, we may define a chain complex (C•(∆,K),∂•) by setting Ci(∆,K) to be the K- vector space whose basis is identified with ∆i and such that given σ ∈ ∆i, write σ = {j0,j1, . . . ,ji}⊆ [m], where j0 < · · · < ji, then ∂i(σ) = i∑ k=0 (−1)k{j0, . . . , ĵk, . . . ,ji}, where ĵk denotes that jk has been removed. Thus C−1(∆,K) ∼= K as ∅ is the only −1-dimensional face. We extend this linearly to define a map ∂i : Ci(∆,K) → Ci−1(∆,K). Since ∂i−1 ◦∂i = 0 ∀i, the resulting sequence is a chain complex of K-vector spaces. Let Zi(∆,K) = Ker(∂i) and Bi(∆,K) = Im(∂i+1). Note that Bi(∆,K) ⊆ Zi(∆,K) ⊆ Ci(∆,K) ∀i. Then we define the ith reduced simplicial homology of ∆ with coefficients in K as Hi(C•(∆,K)) = H̃i(∆,K) = Zi(∆,K) Bi(∆,K) . We define the co-chain complex of ∆ over K to be the vector space dual C•(∆,K) = (C•(∆,K)) ∗ of the chain complex, with coboundary maps ∂i = ∂∗i . We set Z i(∆,K) = Ker(∂i+1) and Bi(∆,K) = Im(∂i). Then the ith reduced simplicial cohomology of ∆ over K is Hi(C•(∆,K)) = H̃i(∆,K) = Zi(∆,K) Bi(∆,K) . Since HomK( ,K) is exact, there is a canonical isomorphism H̃i(∆,K) ∼= H̃i(∆,K). When the simplicial complex ∆ and the field K are clear from context, we omit them from the notation, e.g. writing H̃i for H̃i(∆,K). Let S(∆) denote the suspension of the simplicial complex ∆; that is, S(∆) is the simplicial complex on vertex set ∆0 ∪{a,b}, where a,b are two new vertices. For any facet σ ∈ ∆, we assert that σ ∪{a} and σ ∪{b} are facets of S(∆). This uniquely determines S(∆). The suspension can be viewed as the union of two cones of ∆ glued along their bases. 2.2. Linear codes A linear code C of length n over a (usually finite) field K is a K-vector subspace of Kn. Elements x = (x1, . . . ,xn) ∈ C are called codewords. We say that C is an [n,k,d]-linear code if C has length n, the dimension dimK(C) is k, and the minimum Hamming distance of C is d. The minimum Hamming 136 J. McCullough, H. Newman / J. Algebra Comb. Discrete Appl. 6(3) (2019) 135–145 distance is the minimum over all pairs x,y ∈ C of distinct codewords of the number of positions i such that xi 6= yi. The weight w(x) of a codeword x ∈ C is the number of positions i such that xi 6= 0. The minimum distance of a linear code C is equal to the minimum weight of a nonzero codeword of C. A generator matrix G of a linear code C over K is a matrix whose rowspace is C. A parity check matrix H of C is a matrix whose null space is C. In other words x ∈ C if and only if HxT = 0. The dual code C⊥ of C is the code whose generator matrix is H. Thus G is a parity check matrix for C⊥. We do not require the rows of G or H to be linearly independent. We make use of the following well-known fact relating minimum distance of a code to its parity check matrix. Proposition 2.1 ([8, Lemma 1.2.3]). Let H be a parity-check matrix for a linear code C over a field K. Then every set of d−1 columns of H are linearly independent if and only if C has minimum distance at least d. One of the main challenges in classical error correcting code theory is to find codes with large mini- mum distance and dimension relative to their length. More precisely, we seek a family of asymptotically good codes. A family of codes Ci with parameters [ni,ki,di] with limi→∞ni →∞ is asymptotically good if there exists α,β > 0 such that lim i→∞ ki ni > α and lim i→∞ di ni > β, where ki ni and di ni define the information rate and relative minimum distance of Ci, respectively. Of particular interest are Low Density Parity Check (LDPC) codes. A linear code C (usually defined over F2) is an LDPC code if C has a parity check matrix H with relatively few nonzero entries. If the Hamming weight (number of nonzero entries) in each row and column of H is constant, C is called a regular LDPC code. If we relax one of these conditions, C is called an irregular LDPC code. The cycle codes in this paper have parity check matrices with fixed column weight (since the image of the boundary of any i-face has weight i + 1), but only certain ones will have fixed row weight as well. 2.3. Homological error correcting codes Let ∆ be an m-dimensional simplicial complex and let K be a field. For each 0 ≤ i ≤ m, we define four potentially distinct linear codes. These codes will be the main object of study in this paper. The definitions parallel those in [10] and [13]. We define the ith cycle code (respectively boundary code) as Zi(∆,K) (resp. Bi(∆,K)). Similarly, we define the ith cocycle code (respectively coboundary code) as Zi(∆,K) (resp. Bi(∆,K)). Note that all four codes have length fi as they are subvector spaces of Ci or C∗i . Moreover, by their definitions it is clear that Z i(∆,K) = Bi(∆,K)⊥ and Bi(∆,K) = Zi(∆,K)⊥. In particular for all i we have, dimK Z i(∆,K) + dimK Bi(∆,K) = dimK Zi(∆,K) + dimK Bi(∆,K) = fi(∆). 2.4. Relation to previous work The definition of LDPC codes originates in the thesis of Gallager [6], [5]. Such codes have recently attracted more attention because of the good iterative decoding algorithms associated to them which approach the Shannon limit. Asympotically good codes can be shown to exist by pseudorandom methods and constructed algorithmically. (See e.g. [7]). Our Theorem 4.2 shows that they can be constructed as cycle codes of two-dimensional simplicial complexes. The earliest references we can find to the definition of homological error-correcting codes of a simpli- cial complex are the papers by Salzer [10] and Thomeier [13], where the authors use the terms “topological codes” and “polyhedral codes,” respectively. Both describe the general construction of cycle and boundary 137 J. McCullough, H. Newman / J. Algebra Comb. Discrete Appl. 6(3) (2019) 135–145 codes of a simplicial complex. Both authors then compute the parameters of the ith cycle codes for an m-dimensional simplex. We recover this as a special case of our more general formulas for the dimension and minimum distance. See Theorem 3.7. In [9], Rytíř showed that any linear code over Q or Fp can be realized as a truncated homological code of some two dimensional simplicial complex. Without truncation, there are linear codes which cannot be realized. Our results give both restrictions on the parameters of homological codes and existence results for asymptotically good homological codes. When ∆ is a one-dimensional simplicial complex, we may view ∆ as a simple graph G = (V,E) with vertex set V = ∆0 and edge set E = ∆1. In this case Z1(∆,F2) is called the cycle code of the graph G and has been well-studied. See [14] for a concise survey. It is easy to see that if G = (V,E) is a graph, then its cycle code has parameters [n,k,d], where n = |E|, k = |E|−|V |+ 1 and d is the girth of G, that is, the minimum length of a cycle in G. The well-known Moore bound states that for an r-regular graph G, that is a graph which has r edges incident to each vertex, the girth of G is bounded above by a term logarithmic in r and |V |. A similar bound for non-regular graphs was given in [1]. Thus if we have a family of graphs Gi = (Vi,Ei) with linear growth for |Vi| and |Ei|, the girth of Gi is at most logarithmic in |Vi| and |Ei|. Therefore, it is impossible to construct a family of asymptotically good error correcting codes from graphs or one-dimensional simplicial complexes. Our Theorem 4.2 shows that it is possible to do so with two-dimensional simplicial complexes. Finally we comment that a there is great interest in finding quantum error correcting codes, in- troduced in [11], with similar properties. A well-studied family are the CSS codes [3], [12]. Some constructions of CSS codes, also called homological codes, are defined from graphs, simplicial or poly- hedral complexes. In the quantum setting, the existence of asymptotically good codes is still an open question. We do not discuss quantum codes further in this paper and refer the interested reader to the survey [14] and the references therein. 3. Results on arbitrary homological codes In this section we collect general results which hold for each of the four types of homological codes for an arbitrary simplicial complex ∆ and an arbitrary field K. When clear from context, we suppress ∆ and K from the notation. Theorem 3.1. Let ∆ be an m-dimensional simplicial complex, K a field and 0 ≤ i ≤ m. Then Zi = Zi(∆,K) is an [n,k,d]-code with n = fi, k = i∑ j=−1 (−1)i+jfj + i−1∑ j=0 (−1)i+j+1 dimK H̃j, d ≥ i + 2. Proof. Zi is a sub-vector space of Ci and dimK Ci = fi. So n = fi. By definition, the matrix H associated to ∂i is a parity check matrix for Zi. Since two i-faces of ∆ can only share at most one (i− 1)-face, any two columns of H can share at most one index where that entry is nonzero. Thus each set of i + 1 columns of ∂i are linearly independent. By Proposition 2.1, d ≥ i + 2. For the computation of k, we proceed by induction on i. For i = 0, we have the short exact sequence 0 → Z0 → C0 → C−1 → 0. Thus, dimK Z0 = dimK C0 − dimK C−1 = f0 −f−1 138 J. McCullough, H. Newman / J. Algebra Comb. Discrete Appl. 6(3) (2019) 135–145 as desired. Now suppose dimK Zp = p∑ j=−1 (−1)j+pfj + p−1∑ j=0 (−1)j+p+1 dimK H̃j for some p ∈ N. For i ≥ 0, we have the short exact sequences 0 → Bi → Zi → H̃i → 0 and 0 → Zi → Ci → Bi−1 → 0. Therefore, dimK Bi = dimK Zi − dimK H̃i and dimK Zi = dimK Ci − dimK Bi−1. Then by induction we have dimK Zp+1 = dimK Cp+1 − dimK Bp = fp+1 − (dimK Zp − dimK H̃p) = fp+1 −     p∑ j=−1 (−1)j+pfj + p−1∑ j=0 (−1)j+p+1 dimK H̃j  − dimK H̃p   = p+1∑ j=−1 (−1)j+p+1fj + p∑ j=0 (−1)j+p dimK H̃j. Corollary 3.2. Let ∆ be a contractible simplicial complex and let K be a field. Then, dimK Zi(∆,K) = i∑ j=−1 (−1)i+jfj. Proof. If ∆ is contractible then H̃i(∆,K) = 0 ∀i. The following corollary provides an explicit formula for computing the dimension of cycle codes of graphs discussed in Section 2.3. Corollary 3.3. Let ∆ be a connected simplicial complex. Then, dimK Z1(∆,K) = f1(∆) −f0(∆) + 1. Proof. By Theorem 3.1, we have dimK Z1 = f1 −f0 + f−1 + dimK H̃0. Since ∆ is connected, H̃0 = 0. Moreover, f−1 = 1 for any simplicial complex. The result follows. 139 J. McCullough, H. Newman / J. Algebra Comb. Discrete Appl. 6(3) (2019) 135–145 In general, as the following example shows, the minimum distance of Zi(∆,K) can be strictly bigger than i + 2. When i = 1, d represents the girth of the 1-skeleton of ∆. Example 3.4. Consider the Petersen Graph P viewed as a simplicial complex of dimension 1. It has 10 vertices (0-faces) and 15 edges (1-faces). The graph P is 3-regular with girth 5. It follows from Theorem 3.1 and the discussion in Section 2.4 that Z1(P,K) is a [15, 6, 5]-code for any field K. Note that the minimum distance here is 5 > 3 = 1 + 2. 1 2 34 5 6 7 89 10 If K = F2, then the parity check matrix of Z1(P,F2) is the incidence matrix of P, which is also the matrix associated to ∂1(P,F2). We index the rows by the vertices and the columns by the edges of P.   1,3 1,4 1,6 2,4 2,5 2,7 3,5 3,8 4,9 5,10 6,7 6,10 7,8 8,9 9,10 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 3 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 4 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 5 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 6 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 7 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 8 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 9 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 10 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1   Since the dimensions of the homologies of a simplicial complex can depend on the field K, the parameters for a given cycle code can also depend on K. Example 3.5. Let ∆ be the standard triangulation of the real projective plane on vertex set {1, 2, 3, 4, 5, 6} with the following 2-faces: ∆2 = {123, 124, 126, 134, 135, 156, 235, 236, 346, 456}. If K = F2, then H̃1(∆,K) = K, whereas if K = Fp with p 6= 2, then H̃1(∆,K) = 0. So by Theorem 3.1, when K = F2, Z2(∆,K) has dimension k = f2 −f1 + f0 −f−1 + H̃1(∆,F2) − H̃0(∆,F2) = 10 − 15 + 6 − 1 + 1 − 0 = 1, whereas when K = Fp for p 6= 2, Z2(∆,K) has dimension k = 0. 140 J. McCullough, H. Newman / J. Algebra Comb. Discrete Appl. 6(3) (2019) 135–145 Theorem 3.6. Let ∆ be an m-dimensional simplicial complex, K a field and 0 ≤ i < m. Then Bi(∆,K) is an [n,k,d]-code with n = fi, k = i∑ j=−1 (−1)i+jfj + i∑ j=0 (−1)i+j+1 dimK H̃j, d = i + 2. Proof. Bi is a sub-vector space of Ci and dimK Ci = fi. So n = fi. Since dimK Bi = dimK Zi−dimK H̃i, the formula for k follows from Theorem 3.1. Since dim(∆) ≥ i + 1, the image of ∂i+1 is nonempty. Each (i + 1)-face has boundary with i + 2 distinct faces. Hence there is at least one vector in Bi of weight exactly i + 2. So d ≤ i + 2. But Bi ⊆ Zi and the minimum distance of Zi was at least i + 2. Thus d = i + 2. Corollary 3.7. Let ∆ be an m-dimensional simplex, K a field and 0 ≤ i < m. Then Zi(∆,K) = Bi(∆,K) is an [n,k,d]-code with n = ( m + 1 i + 1 ) , k = ( m i + 1 ) , d = i + 2. Proof. By Theorem 3.1, n = fi = ( m+1 i+1 ) . Since ∆ is contractible, H̃i(∆) = 0 ∀i. Hence, Zi = Bi ∀i and d = i + 2 by Theorem 3.6. Finally, we have k = i∑ j=−1 (−1)i+jfj = i∑ j=−1 (−1)i+j ( m + 1 j + 1 ) = ( m i + 1 ) , by Pascal’s Identity. Note that the parameters do not depend on the field K. Remark 3.8. The family of m-simplex codes described here are not asymptotically good according to the definition given in Section 2.2. If i = m− 1, then k = ( m m ) = 1; that is, a one-dimensional code. In the most interesting scenario, we set i = m− 2 and obtain the following: n = (m2 + m) 2 , k = m, d = m. Note that there is quadratic growth in n, but linear growth in k and d. Thus, lim i→∞ ki ni = 0 and lim i→∞ di ni = 0. Other choices of i < m− 2 produce codes with similar asymptotics. A similar analysis can be carried out on the dual codes Zi(∆,K) and Bi(∆,K). In general, the minimum distance depends on the minimum degree of an i-face in ∆. 141 J. McCullough, H. Newman / J. Algebra Comb. Discrete Appl. 6(3) (2019) 135–145 Theorem 3.9. Let ∆ be an m-dimensional simplicial complex, K a field and 0 ≤ i < m. Then Zi = Zi(∆,K) is an [n,k,d]-code with n = fi, k = i−1∑ j=−1 (−1)i+j+1fj + i∑ j=0 (−1)i+j dimK H̃j, d ≥ deg(i, ∆) + 1. Proof. Since Zi ⊆ Ci, n = fi. Since Zi = B⊥i , dimK Z i + dimK Bi = fi and the value of k follows from Theorem 3.6. Each column of the matrix associated to ∂∗i+1 has at least deg(i, ∆) nonzero entries. Since any two distinct i-faces are contained in at most one (i + 1)-face, every set of deg(i, ∆) columns of ∂∗i+1 is linearly independent. Indeed suppose r columns of ∂∗i+1 are linearly dependent. The first such column has at least deg(i, ∆) nonzero entries and each other column can cancel at most one of these entries, meaning r > deg(i, ∆). Applying Proposition 2.1 yields that d ≥ deg(i, ∆) + 1. A similar argument gives the parameters for the coboundary codes. Theorem 3.10. Let ∆ be an m-dimensional simplicial complex, K a field and 0 ≤ i ≤ m. Then Bi = Bi(∆,K) is an [n,k,d]-code with n = fi, k = i−1∑ j=−1 (−1)i+j+1fj + i−1∑ j=0 (−1)i+j dimK H̃j, deg(i, ∆) + 1 ≤ d ≤ min{deg(σ) |σ ∈ ∆i−1 and deg(σ) > 0}. Proof. The formulas for n and k follow from Theorem 3.1. That deg(i, ∆) + 1 ≤ d follows from Theorem 3.9 since Bi ⊆ Zi. On the other hand, by definition there is a nonzero element in Bi of weight min{deg(σ) |σ ∈ ∆i−1 and deg(σ) > 0}. When ∆ is the m-dimensional simplex, each i-face is contained in exactly m−i many (i + 1)-dimensional faces. Applying the previous two theorems yields the following calculation, which together with Theo- rem 3.7, recovers calculations in [10] and [13]. Corollary 3.11. Let ∆ be an m-simplex, K a field and 0 ≤ i ≤ m. Then Zi(∆,K) = Bi(∆,K) is an [n,k,d]-code with n = ( m + 1 i + 1 ) , k = ( m i ) , d = m− i + 1. It is easy to check that none of these codes form a regular LDPC family of codes that are asymptotically good. 4. Asymptotically good homological codes The goal of this section is to prove the existence of asymptotically good cycle codes for specially chosen simplicial complexes ∆ with dim(∆) ≥ 2. We rely on the following result of Dotterer, Guth, and Kahle derived from work of Aronshtam, Linial, Łuczak and Meshulam [2]. Since a proof is omitted from [4] we sketch a proof here. For notation and details, we refer the reader to [2]. 142 J. McCullough, H. Newman / J. Algebra Comb. Discrete Appl. 6(3) (2019) 135–145 Theorem 4.1 ([4, Theorem 6.2(1)]). For any α > 0, and for all n sufficiently large, there exist 2- dimensional simplicial complexes ∆ with n vertices and with at least αn2 faces, such that every cycle in in H2(∆,F2) is supported on at least Cαn2 faces (where Cα > 0 is a constant depending only on α). Proof. Let Y2(n,p) denote the probability space of simplicial complexes of that contain every (d− 1)- dimensional face and also each d-dimensional face with independent probability p. Fix α > 0 and let c > 6α. By [2, Theorem 4.1], there exists a constant δ (depending only on c) such that asymptotically almost surely, every every minimal core subcomplex (and thus every minimal cycle) K of Y ∈ Y2(n, cm) with f2(K) ≤ δn2 is the boundary of a 3-dimensional simplex. Let Xm denote the number of 2-cycles in Y with exactly m faces so that Xm = 0 for m ≤ 3 and X4 counts the number of boundaries of 3-dimensional simplices in Y . The expected number of such subcomplexes is EX4 = ( n 4 ) p4 = n(n− 1)(n− 2)(n− 3) 3! c4 n4 ≤ c4 6 . Thus for sufficiently large n, we can find a d-dimensional simplicial complex Y with n vertices and no cycles of size ≤ δn2 except for the at most c 4 6 boundaries of 3-simplices. By removing one face from each cycle, we get a simplicial complex Y ′ with no 2-cycles of size ≤ δn2. The expected number of 2-faces in Y ′ is Ef2(Y ′) ≥ ( n 3 ) p− c4 6 = n(n− 1)(n− 2) 6 c n − c4 6 = c(n− 1)(n− 2) − c4 6 , and for n sufficiently large c(n−1)(n−2)−c 4 6 > αn2. Thus we may take Cα = δ. With this result and Theorem 3.1 in hand, we can now prove our main result about the existence of asymptotically good cycle codes. Theorem 4.2. There is a positive constant c ∈ R such that, for all m ∈ N sufficiently large, there exists a 2-dimensional simplicial complex ∆m on m vertices such that Z2(∆m,F2) is an [n,k,d]-code with n = m2, k ≥ m2 2 , d ≥ cm2. In particular, Z2(∆m,F2) give a family of asymptotically good codes over F2. Proof. Let α = 1 and apply Theorem 4.1. We get an infinite family of 2-dimensional simplicial complexes ∆m for m � 0 such that ∆m has m vertices and at least m2 2-faces and such that every cycle of H2(∆m,F2) = Z2(∆m,F2) is supported on at least cm2 faces where c = C1 above. First note that we may assume that f2(∆m) = m2 since deleting faces can only increase the size of the support of a cycle in H2(∆m,F2). Moreover, we may assume that all ( m 2 ) edges are present since adding edges does not affect Z2(∆m,F2). Thus by Theorem 3.1, Z2(∆m,F2) is an [n,k,d]-code with n = f2(∆m) = m2. Since every cycle is supported on at least cm2 faces, d ≥ cm2. Finally we have k = f2 −f1 + f0 −f−1 + H̃1 − H̃0 = m2 − ( m 2 ) + m− 1 + H̃1 − H̃0 ≥ m2 2 where the last inequality uses that H̃0 = 0, since ∆m is connected, and that m ≥ 2. 143 J. McCullough, H. Newman / J. Algebra Comb. Discrete Appl. 6(3) (2019) 135–145 The results in [2] and [4] rely on probabilistic methods to prove the existence of such simplicial complexes. It would be interesting to have explicit constructions of such simplicial complexes. Finally we remark that the previous Theorem can be extended to higher dimension by taking sus- pensions. Proposition 4.3. Let ∆ be an m-dimensional simplicial complex and let K be a field. If Zm(∆,K) had parameters [n,k,d], then Zm+1(S(∆),K) has parameters [2n,k, 2d]. Proof. For all i ≥ −1, there is a canonical isomorphism φ : H̃i(∆,K) ∼= H̃i+1(S(∆),K), coming from the Mayer-Vietoris sequence induced by sending an i-face σ to the sum σ∪{a} + σ∪{b}, where a,b are the two additional vertices. In particular, Zm(∆,K) = H̃m(∆,K) ∼= H̃m+1(S(∆),K) = Zm+1(S(∆),K) and the dimensions of the 2 codes agree. If n is the length of Zm(∆,K), then by construction the length of S(∆) is fm+1(S(∆)) = 2fm(∆) = 2n. Finally, it is clear that φ doubles the support of any cycle in Zm(∆,K) and hence doubles the minimum weight of the associated code. Note that since the dimension is preserved, we do not get asymptotically good families by taking repeated suspensions of a given simplicial complex. However, combining with Theorem 4.2 yields the following consequence. Corollary 4.4. For any integer r ≥ 2, there is a family of r-dimensional simplicial complexes {∆m} whose cycle codes Zr(∆m,F2) are asymptotically good. Proof. Fix r ≥ 2. Let Sr(∆) denote the r-fold suspension of ∆. Let {∆m} be the family of 2- dimensional simplicial complexes from Theorem 4.2. Then by Proposition 4.3, Zr(Sr−2(∆m),F2) has parameters [2r−2m2,m2/2,c2r−2m2], and hence forms an asymptotically good family. Finally we remark that since the parity check matrix of Zr(Sr−2(∆m),F2) is the matrix associated to ∂r(Sr−2(∆m),F2), it has exactly r + 1 ones per column. So the corresponding family of codes is a (non-regular) LDPC family of codes. Acknowledgment: We are very grateful to Tony Bahri and Lance Miller for feedback on an earlier version of this paper and Matthew Kahle for useful conversations. We also thank the referee for several helpful suggestions. References [1] N. Alon, S. Hoory, N. Linial, The Moore bound for irregular graphs, Graphs Combin. 18(1) (2002) 53–57. [2] L. Aronshtam, N. Linial, T. Łuczak, R. Meshulam, Collapsibility and vanishing of top homology in random simplicial complexes, Discrete Comput. Geom. 49(2) (2013) 317–334. [3] A. R. Calderbank, P. W. Shor, Good quantum error–correcting codes exist, Physical Review A 54(2) (1996) 1098–1105. [4] D. Dotterrer, L. Guth, M. Kahle 2–complexes with large 2–girth, Discrete Computational Geometry 59(2) (2018) 383–412. [5] R. G. Gallager, Low–density parity–check codes, IRE Trans. 8(1) (1962) 21–28. [6] R. G. Gallager, Low–Density Parity–Check Code, MIT Press, 1963. [7] X.-Y. Hu, E. Eleftheriou, D. M. Arnold, Regular and irregular progressive edge–growth Tanner graphs, IEEE Trans. Inform. Theory 51(1) (2005) 386–398. [8] Steven Roman, Coding and Information Theory, Graduate Texts in Mathematics, vol. 134, Springer– Verlag, New York, 1992. 144 https://doi.org/10.1007/s003730200002 https://doi.org/10.1007/s003730200002 https://doi.org/10.1007/s00454-012-9483-8 https://doi.org/10.1007/s00454-012-9483-8 https://doi.org/10.1103/PhysRevA.54.1098 https://doi.org/10.1103/PhysRevA.54.1098 https://doi.org/10.1007/s00454-017-9926-3 https://doi.org/10.1007/s00454-017-9926-3 https://doi.org/10.1109/TIT.1962.1057683 https://mitpress.mit.edu/books/low-density-parity-check-codes https://doi.org/10.1109/TIT.2004.839541 https://doi.org/10.1109/TIT.2004.839541 J. McCullough, H. Newman / J. Algebra Comb. Discrete Appl. 6(3) (2019) 135–145 [9] Pavel Rytíř, Geometric representations of linear codes, Adv. Math. 282(10) (2015) 1–22. [10] Charles Saltzer, Topological codes, Error Correcting Codes (Proc. Sympos. Math. Res. Center, Madi- son, Wis., 1968), Wiley, New York (1968) 111–129. [11] P. W. Shor, Scheme for reducing decoherence in quantum memory, Phys. Rev. A. 52(4) (1995) R2493–R2496. [12] A. M. Steane, Multiple–particle interference and quantum error correction, Proc. Roy. Soc. A. 452(1954) (1996) 2551–2577. [13] S. Thomeier, Error–correcting polyhedral codes, J. Comput. Inform. 1(2) (1990) 91–101. [14] G. Zémor, On Cayley graphs, surface codes, and the limits of homological coding for quantum error correction, Coding and cryptology, Lecture Notes in Comput. Sci., vol. 5557, Springer, Berlin (2009) 259–273. 145 https://doi.org/10.1016/j.aim.2015.06.011 https://mathscinet.ams.org/mathscinet-getitem?mr=237222 https://mathscinet.ams.org/mathscinet-getitem?mr=237222 https://doi.org/10.1103/PhysRevA.52.R2493 https://doi.org/10.1103/PhysRevA.52.R2493 https://www.jstor.org/stable/52827 https://www.jstor.org/stable/52827 https://mathscinet.ams.org/mathscinet-getitem?mr=1121382 https://doi.org/10.1007/978-3-642-01877-0_21 https://doi.org/10.1007/978-3-642-01877-0_21 https://doi.org/10.1007/978-3-642-01877-0_21 Introduction Preliminaries Results on arbitrary homological codes Asymptotically good homological codes References