{'fraction_non_alphanumeric': 0.0774085762019677, 'fraction_numerical': 0.016335622795619082, 'mean_word_length': 3.3353004291845494, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An improvement of the asymptotic Elias bound for non-binary codes

For non-binary codes the Elias bound is a good upper bound for the asymptotic information rate at low relative minimum distance, where as the Plotkin bound is better at high relative minimum distance. In this work, we obtain a hybrid of these bounds which improves both. This in turn is based on the anticode bound which is a hybrid of the Hamming and Singleton bounds and improves both bounds. The question of convexity of the asymptotic rate function is an important open question. We conjecture a much weaker form of the convexity, and we show that our bounds follow immediately if we assume the conjecture.


I. INTRODUCTION
Let A q (n, d; L) denote the maximum size of a code of length n, minimum distance at least d, and contained in a subset L ⊂ F n , where F is an alphabet of finite size q. A central problem in coding theory is to obtain good upper and lower bounds for A q (n, d) = A q (n, d; F n ). The asymptotic version of this quantity is the asymptotic information rate function: α(x) = lim sup n→∞ n −1 log q A q (n, xn), x ∈ [0, 1]. (1) The quantities A q (n, d; L) and A q (n, d) are related by the inequality A q (n, d) ≤ q n A q (n, d; L)/|L|, known as the Bassalygo-Elias lemma. Taking L to be a Hamming ball of diameter w, and choosing w optimally gives, at the asymptotic level the Hamming and the Elias upper bounds.
The bound α E is better than α H for all x. Here H q (x) is the entropy function (9), and θ := 1 − q −1 . An anticode of diameter w in F n is any subset of F n with Hamming diameter w. Let A * q (n, w) denote the maximum size of an anticode of diameter at most w in F n . In contrast to the situation with A q (n, d), the quantity A * q (n, d) was explicitly determined by Ahlswede and Khachatrian in [1]. From their result, it is easy to determine the asymptotic quantity α * (x) = lim n→∞ n −1 log q A * q (n, xn). We actually do not need the results of [1], however it is the main inspiration for this work. Taking L to be an A * q (n, w) anticode in (2), and choosing w optimally, we get the following two bounds which improve α H and α E respectively.

Theorem 1. (hybrid Hamming-Singleton bound)
The bound α HS improves the Hamming and the Singleton bounds. It is ∪-convex and continuously differentiable.
, θ] The bound α EP improves the Elias and Plotkin bounds. It is ∪-convex and continuously differentiable.
As evidence for this conjecture, we will show that theorems 1 and 2 follow very easily if we admit the truth of the conjecture. The paper is organized as follows. In section II, we collect some results on size of anticodes, which we use in section III to prove Theorems 1 and 2. We discuss Conjecture 1 in section IV.

II. SIZE OF ANTICODES
We recall that A * q (n, d) is the maximum size of an anticode of diameter at most d in F n . If we take L to be an anticode of size A * q (n, d − 1) then clearly A q (n, d; L) = 1. Using this in (2), we get a bound known as Delsarte's code-anticode bound [2]. Taking d = xn where x ∈ [0, 1] we get n −1 log q A q (n, xn) ≤ 1 − n −1 log q A * q (n, xn − 1). Taking lim sup n→∞ we get: where This is the the asymptotic form of (5). We use the notation B(r; n) and V q (n, r) to denote a Hamming ball of radius r in F n and its volume respectively. The ball B(t; n) where t = (d − 1)/2 in F n is an anticode of diameter at most d − 1. Let F n = F d−1 × F n−d+1 and let v ∈ F n−d+1 be a fixed word. Sets of the form F d−1 × {v} of size q d−1 are also anticodes of diameter d − 1. It follows that: Here, we have used the well known formula: where, While the convexity of α(x) is an open question, it is quite easy to see that: Proof: If S 1 ⊂ F n 1 and S 2 ⊂ F n 2 are anticodes of diameters d 1 and d 2 respectively, then S 1 × S 2 ⊂ F n 1 × F n 2 is an anticode of diameter d 1 + d 2 . Taking S i to be A * q (n i , d i ) anticodes, we immediately get A * q (n 1 + n 2 , d 1 + d 2 ) ≥ A * q (n 1 , d 1 )A * q (n 2 , d 2 ). Let n = n 1 + n 2 go to infinity with n 1 /n = t + o(1), d 1 /n 1 = x + o(1) and d 2 /n 2 = y + o(1). Applying lim inf n→∞ n −1 log q to this inequality we get: We note that with codes we have d(C 1 ×C 2 ) = min{d(C 1 ), d(C 2 )}, which is why the above proof method does not apply to the question of convexity of α(x). From (8) and Lemma 1 we get: Let δ = tx + (1 − t)y. We can rewrite this as We note that There is a unique positive number b > 0 satisfying H q (b/2) = b (where the Hamming and Singleton bounds intersect). Therefore, H q (x/2) − x has the same sign as b − x. Using this in (10), we see that f (x, y) ≤ δ for x ≥ b. Therefore, in order to maximize f (x, y) it suffices to consider x < b. We note that ∂f ∂y (x, y) has the same sign as H(x/2) − x and hence that of b − x. Since x < b, we see that for fixed x < b, the function f (x, y) is maximized for y = 1. We are now reduced to maximizing sign(g (x)) = sign(x − 2 q ). Proof: We calculate: Therefore sign(g (x)) = sign( q 2 x(2−x) 4(q−1) − 1). Next, we note that has the same sign as x − 2/q, as was to be shown. A stronger assertion is that g(x) is in fact ∪-convex: differentiating once more, we get: ) We note that q 2 ≥ 4(q − 1), and hence the first term is non-negative. The remaining parenthetical term is non-negative using the inequality and the fact that It follows from Lemma 2 that argmin x∈[0,δ] Therefore we obtain the bound: Moreover, β(x) is continuously differentiable and ∩-convex.
We have used the relation The function β(x) is continuously differentiable because the component for x ≥ 2/q is just the tangent line at x = 2/q to the component for x ≤ 2/q, i.e. to H q (x/2). We note that β (x) equals H q (x/2)/2 for x ≤ 2/q and H q (1/q)/2 for x ≥ 2/q. Since β (x) is non-increasing, it follows that β(x) is ∩-convex.
In the next lemma, we show that there is a sequence of anticodes S n ⊂ F n of diameter at most δn such that lim n→∞ n −1 log q |S n | equals β(δ), i.e. the lower bound on α * (δ) given in theorem 3.
Proof: We note that We now have all the results we need for proving theorems 1 and 2. However, we will state a remarkable theorem due to Ahlswede and Khachatrian [1], which we will not need. We also obtain an asymptotic version of their result and record it as a corollary, as it does not seem to have appeared in literature. In brief their theorem states that A * q (n, d) equals |S(d, n)|. Moreover any A * q (n, d) anticode is Hamming isometric to the anticode S(d, n) (with some exceptions). At the asymptotic level, the result is again remarkable: The lower bound β(δ) for α * (δ) given in theorem 3 is actually the exact value of α * (δ). Moreover α * (δ) need not have been defined using lim inf n→∞ as lim n→∞ n −1 log q A * q (n, δn) already exists. Theorem. [1] Given q ≥ 2 and integers 0 ≤ d ≤ n, let r d,n and S(d, n) be as in Lemma 3. Then, Moreover, up to a Hamming isometry of F n an anticode S of size A * q (n, d) must be: Proof: It follows from the theorem of Ahlswede and Khachatrian, together with Lemma 3 that

III. PROOFS OF THEOREMS 1 AND 2 A. Proof of Theorem 1
If we use the bound . This finishes the proof of Theorem 1.
It is worth noting that (12) implies the following formula for α HS (δ): It can be shown (see subsection III-C) that α HP (δ) is an upper bound for α(δ) which improves both the Hamming and Plotkin bounds.

B. Proof of Theorem 2
It will be convenient to identify the alphabet F with the abelian group Z/qZ. Given 0 ≤ δ ≤ ω, let w n = ωn and d n = δn . We take L n ⊂ F n to be the anticode (from Lemma 3): We will take the balls B(r; m) to be centered at (0, . . . , 0) ∈ F n . As in Lemma 3, we have We also note that Lemma 3 gives Let A q (n, d n ; L n ) be the maximum possible size of a code contained in L n and having minimum distance at least d n .
Proof: Our proof is similar to the standard proof of the analogous result for the Elias bound (which corresponds to taking ρ = ω/2 instead of the prescription (18)). First let C ⊂ L be a code of size where m(i, a) = #{c ∈ C : c i = a}. We note that M = a∈F m(i, a), and that We can rewrite this as: For n − w + 2r < i ≤ n we use Cauchy-Schwarz inequality to get a∈F m(i, a) 2 ≥ M 2 /q. In particular Let π 1 be the projection of F n = F n−w+2r × F w−2r on to the factor F n−w+2r . We note that for c ∈ C, we have wt(π 1 (c)) < r because π 1 (C) ⊂ B(r; n − w + 2r). Here wt(v) is the number of nonzero entries of v. Therefore Since n−w+2r i=1 a m(i, a) = M (n − w + 2r) we get: In particular We note that a =0 m(i, a) = M n − m(i, 0). By Cauchy-Schwarz inequality: we get: This can be rewritten as: Combining this with (22) we get: Using (23) this can be written as: . Now let C n ⊂ L n be a sequence of codes of size M n = A q (n, d n ; L n ). The preceding inequality gives: (1). Using this in (21), we get: provided the denominator is a positive number. Therefore, lim n→∞ n −1 log q M n = 0 provided

This condition is the same as
Since M n = A q (n, d n ; L n ) this finishes the proof.
Taking lim sup as n → ∞ and using the result of Theorem 4 and (19) we get: where ω max (δ) is the largest value of ω for which the inequality (20) holds. In order to determine ω max (δ), we introduce functions f 1 , f 2 on [0, θ] defined by: The three assertions to be proved follow respectively from the following three relations: . The function ω max (δ) is increasing, continuously differentiable, and ∪-convex on [0, θ].
We note that the second component of ω max (δ) is the tangent line to the first component at , and constant at q−1 q−2 for x ≥ 2q−3 q(q−1) . Since the derivative is positive, the function is increasing. Since the derivative is non-decreasing, we see that the function is ∪-convex.
Proof of α EP being continuously differentiable: The function α EP (x) = α HS (ω max (x)) being a composition of continuously differentiable functions, is itself continuously differentiable.
Proof of α EP being ∪-convex: Both the functions α HS and ω max are ∪-convex, but α HS is decreasing and hence it is not obvious that α EP (x) = α HS (ω max (x)) is ∪-convex. We will show instead that the derivative α EP is non-decreasing. Since α EP is constant for x ≥ 2q−3 q(q−1) , it suffices to show that α E (x) > 0 for x ∈ (0, 2q−3 q(q−1) ]. This follows from the next lemma.
Proof that α EP improves the Plotkin bound: We have already shown that α EP (x) is ∪-convex, and hence α EP (x) lies below the secant line between x = 0 and x = θ, which is the Plotkin bound.
Proof that α EP improves the Elias bound: This does not readily follow from our results thus far, and requires more work. The characterization of α EP (x) given in the next theorem clearly implies α EP (x) ≤ α E (x).
Proof: The theorem immediately follows if we show that α E (x) θ−x is decreasing on [0, 2q−3 q(q−1) ] and increasing on [ 2q−3 q(q−1) , θ]. We will use the notation from the proof of Lemma 5. Since α E (x) is ∩-convex for x ≥ δ E , it follows that the slope α E (x)/(θ − x) of the secant between x and θ is increasing. It remains Since ϕ(t) > 0 for t ∈ (0, z E ), we see Thus we have also shown that h(z) is decreasing for z ∈ [0, 1/q] and increasing on [1/q, z E ] as required. The bounds α HS , α HP and α EP are related as Thus α EP (δ) ≤ α HP (δ). We end this section with a plot comparing α E (x) and α EP (x) for q = 16.
We now prove that the function α HP (δ) defined in (16) is an upper bound for α(δ). Taking δ 2 = θ, δ 1 = x, and µ = (y − δ 1 )/(θ − δ 1 ) in (27), we get: It is not known if the inequality (27) (the theorem of Laihonen-Litsyn) holds if we replace α H by α E . If such a result were true, then the derivation of the bound α HP (x) above with α H replaced with α E would immediately yield Theorem 5. We believe that such an inequality must be true (it would surely be true if α(x) is ∪-convex), but we believe it cannot be obtained just by a simple application of the Bassalygo-Elias lemma (2). If (29) holds, we can obtain an upper bound which improves the Laihonen-Litsyn bound [3]. We recall that the Laihonen-Litsyn bound, which we denote α HM RRW is a hybrid of the Hamming and MRRW bounds. It coincides with the Hamming bound for δ ∈ [0, a] and with the MRRW bound for [b, θ] where a < b are points such that the straight line joining (a, α H (a)) and (b, α M RRW (b)) is a common tangent to both α H at a and α M RRW at b. Since the Hamming bound is good for small δ and the MRRW bound good for large δ, the Laihonen-Litsyn bound combines the best features of both bounds in to a single bound. To obtain this bound, we note that (27) implies the inequality We fix δ = (1 − µ)δ 1 + µδ 2 and choose δ 1 and δ 2 optimally in order to minimize the right hand side. This yields the α HM RRW bound. Since the Elias bound α E (δ) is better than the Hamming bound α H (δ) for all δ, in case (29) is true, repeating this procedure with α E replacing α H , would yield a hybrid Elias-MRRW bound α EM RRW (δ) which improves the Laihonen-Litsyn bound α HM RRW . We leave the question of the truth of (29) open.

IV. ON THE CONVEXITY OF α(x)
A fundamental open question about the function α(x) is whether it is ∪-convex. In other words is it true that It is worth noting that non-convex upper bounds like the Elias bound and the MRRW bound admit corrections to the non-convex part: the bound α EP (x) for the Elias bound and the Aaltonen straightline bound (see the theorem below and the Appendix) for the MRRW bound. This may be viewed as some kind of evidence supporting the truth of (30). It is known that (30) holds for x = 0 (for example by taking δ 1 = 0 in (27)). Another way to state this is that As a consequence, if α u (x) is any upper bound for α(x) we obtain a better upper bound To see this we use: .
(1−αu(x)) x as desired. If (1 − α u (x))/x is a decreasing function then the improved boundα u (x) coincides with α u (x), but otherwiseα u (x) improves α u (x). For example let α u (x) be the first MRRW bound α M RRW (x) = It can be shown that that (1 − α M RRW (x))/x fails to be decreasing near x = 0, and similarly α M RRW (x) fails to be ∪-convex near x = 0. This is immediately rectified by passing to the improved bound α M RRW (x), resulting in the following theorem of Aaltonen.
We note that for x ≤ (1 − 2/q) 2 the boundα M RRW (x) coincides with the tangent line to α M RRW (x) at (1−2/q) 2 . In particularα M RRW (x) is continuously differentiable. The assertion thatα M RRW (x) improves α M RRW (x) follows from the fact thatα u (x) ≤ α u (x) for any upper bound α u (x) for α(x). The other assertions are proved in the appendix.
On the other hand, it is not known if the convexity condition (30) holds for y = θ, in other words if α(x)/(θ − x) is a decreasing function of x. We conjecture that this is true (see Conjecture 1). As evidence for this conjecture, we now show that the bounds α EP , α HP and α HS can be obtained without doing any work, if we assume the truth of Conjecture 1: if α u (x) is any upper bound for α(x) we obtain a better upper bound To see this we use: Thus α(δ) ≤ min x∈[0,δ] αu(x)(θ−δ) θ−x as desired. In case α(x) θ−x is a decreasing function then the improved bound α † u (x) coincides with α u (x), but otherwise α † u (x) improves α u (x). Taking α u (x) to be the Elias bound, we get α † u (x) to be the bound α EP . This is the content of Theorem 5. Taking α u (x) to be the Hamming bound, we get α † u (x) to be the bound α HP . This is the content of (28). Moreover, if α u (x)/(θ − x) is decreasing then α u (x)/(1 − x) being the product of the non-negative decreasing functions Taking α u (x) to be the Hamming bound, the bound min x∈[0,δ] . This is the content of (15).

APPENDIX A AALTONEN'S STRAIGHT-LINE BOUND
The boundα M RRW presented above was obtained by Aaltonen in [4, p.156]. The bound follows from (31) and the following result The argmax above is not straightforward to obtain, and to quote from [4], was found by a mere chance. The derivation is not presented in [4]. The purpose of this appendix is to i) record a proof of (34), and ii) to prove thatα M RRW (x) is ∪-convex. The author thanks Tero Laihonen for providing a copy of Aaltonen's work [4], which is not easily available.