A "binary code" is an M-element subset of the 2^n binary n-bit words, with minimum hamming distance d. A "q-ary code" is an M-element subset of the q^n words of n letters in alphabet of size q, words, with minimum hamming distance d. A "spherical code" is a set of M points on the unit sphere in n dimensions, wiht minimum angular separation d. If we let d depend on n in some monotone manner, then if d is too large, then necessarily M will stay small, e.g. growing at most polynomially as a function of n. On the other hand, if d is too small, then codes exist with enormously large M growing faster with n than any polynomial, and indeed if d is small enough exponentially. It thus is an interesting question what is the "critical" d(n) delineating the border between "too small" and "too large." I have not seen this question & answer stated before, although one might have thought it'd be well known. CLAIM: Let k>0 be a constant and consider the following choice of d as a function of n: for binary codes: d = n/2 - k*n^(1/2) for q-ary codes (q>1 is a fixed prime integer): d = (1-1/q)*n - k*n^(1/2) for spherical codes: sec(d) = k*n^(1/2) I claim with this choice of d, codes whose cardinalities M grow like a power of n exist, where the power may be made arbitrarily large by making k small enough. I conjecture that was best possible, i.e. there exists some k>0 which forces M to be upper bounded by a polynomial in n in each of the three cases. One might conjecture still more strongly that for any fixed k>0, M is upper bounded by a polynomial in n. PROOF (but not of the conjectural part): You can simply use the duals of BCH codes (where for spherical codes, use binary codes with alphabet {-1,+1} then rescale all n-vectors to have unit length) in view of (A) this paper: Daniel Augot, Francoise Levy-dit-Vehel: Bounds on the minimum distance of the duals of BCH codes, http://hal.archives-ouvertes.fr/docs/00/50/94/78/PS/i3e2newmat.ps (B) the fact that (extended narrow sense) BCH linear q-ary codes with blocklength n and "designed distance h+1" exist, for any fixed integer h>0, which when n-->infinity have duals having order n^floor(h/2) codewords. (It is possible that actual min distance exceeds the designed distance, but this possibility does not hurt us.) Finally, my conjecture that this claim is best possible would follow for binary linear codes from the conjecture that no binary linear codes exist with the same parameters as the "Kerdock codes." This conjecture is research problem 15.4 in MacWilliams & Sloane and as far as I know still remains open (although it has been verified by computer exhaustive search for small n). -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)