arXiv:1606.01592v5 [] 12 Jun 2017

Proof of Tightness of Varshamov - Gilbert
Bound for Linear Binary Codes
Vladimir Blinovsky
Institute for Information Transmission Problems,
B. Karetnyi 19, Moscow, Russia,
vblinovs@yandex.ru

Abstract We find the asymptotically tight coding bound for linear codes.
We prove that asymptotic Varshamov - Gilbert [1], [2] bound for linear
binary codes is tight
In the linear space of q−ary vectors (q = pm , pprime) of length n as Fqn ,
where alphabet is the set of elements from finite field Fq=pm . Linear code Mn
is linear subspace of Fqn , k = logq Mn , RMn = k/n, dMn = {min d(x, y), x 6=
P
y ⊂}, d(x, y) = ni=1 δxi , yi , δMn = dMn /n,
(Asymptotic) Varshamov -Gilbert bound [3], [4] says that there exist sequence of linear codes Fqn such that
RMn > 1 − Hq (δMn ) + o(1).

(1)

as n → ∞, where Hq (x) = −x logq x − (1 − x) logq (1 − x) + (q − 1) logq (x) is
q−ary entropy.
Main hypothesis in Information theory says that this bound is tight for
binary alphabet. In present paper we prove this hypothesis and moreover
find the tight asymptotic bound in general case of q−ary alphabet.
We need the following Lemma [4].
Lemma 1. (Stefanescus, 2005). Let p(x) ∈ R[x] be such that the number of
variations of signs of its coefficients is even. If
p(x) = c1 xd1 − b1 xm1 + c2 xd2 − b2 xm2 + . . . + ck xdk − bk xmk + g(x),
1

g(x) ∈ R+ [x], ci > 0, bi > 0, Di > mi > di+1 for all i, the number



B3 (p) = max 

b1
c1

!1/(d1 −m1 )

bk
ck

,...,

!1/(dk −mk ) 



is upper bound bound for the positive roots of the polynomial p for any choice
c1 , . . . , ck .
Define redundancy r = n − kMn and HMn = {hi,j , i ∈ [n], j ∈ [r]} is
checking matrix of the code Mn .
Let h(i) be the rows of HMn . Consider polynome
Pq (r, d) =

X

h(i)∈Fqn



qr − q

Y

[n]
σ∈∪d−1
i=1 k q

( )

Pr

j=1

Pm

s=1

cos( 2π
2π(h(j),σ)s )
p



.

(2)

It is clear that this polynome is equal to zero iff dMn < d. Hence if we find
the proper lower bound for the root 1/q r of this polynome, it would be the
bound for the rate of the code Mn .
Expansion of Pq (r, d) is as follows
Pq (r, d) = q

r(V −1)

VX
−1

(−1)j

j=0

X

[n]
{am,λ },{σw }=∪d−1
i=1 ( k )

q
q

Pj

m=1

1
q rj

π(j),

P km P s
λ=1

X
P

t=1

s

ks ≤r

1
2 ks
s=1 ks ! s!

Qj

cos( 2π
(am,λ σwt ))
p

where {am,λ } runs over the set of rows of parity checking matrix. Using
Lemma we find upper bound for the root 1/q r of this polynome:
(

)

X Pm cos 2π (a,σ)
1
2
2
s)
≤
max
(2s
+
2)(k
)
/((2s
+
1)(k
)
))
q s=1 ( p
. (3)
2s+2
2s+1
qr
σ

Here (a, σ)s define s−th coordinate in the representation of the element
(a, σ) ∈ Fpm .
Because max is taken over the set of numbers which are in logarithmic
asymptotic equal, we have that bound (3) is tight. In binary case it gives
(asymptotically) Varshamov- Gilbert bound.
Method using here -constructing of function which (positive) minimal root
gives the upper bound for parameter of combinatorial problem and consequently finding the bound for this root is original and we call it Blinovskys (:))
2

averaging method. We expect that this method allows to solve many combinatorial problems such as Hadwiger conjecture [5], Borsuk conjecture [6],
codes with fixed distance d and codes in Euclidean space. We hope we return
to this scheme of proof in the subsequent manuscripts.

References
[1] E. N. Gilbert, A comparison of signaling alphabets, Bell System Tech.
J. 31 (1952), 504522.
[2] R. R. Varshamov, Estimate of the number of signals in error correcting
codes, Dokl. Akad. Nauk SSSR 117 (1957), 739741.

[3] http://ac.els-cdn.com/0012365X82900589/1-s2.0-0012365X82900589-main.pdf?-tid=27cab464-2e60
and —x-0&acdnat=1493637797-5e3b27c210e946c0cf7f0c48d6f0b33f
[4] http://inf-server.inf.uth.gr/∼akritas/phd-thesis-vigklas.pdf
[5] https://en.wikipedia.org/wiki/Hadwiger-onjecture-(graph-theory)
[6] https://en.wikipedia.org/wiki/Borsuk%27s-conjecture

3

