extfieldsofstudy:
Mathematics
Computer Science

s2fieldsofstudy:
Computer Science
Mathematics

text:
New covering codes of radius $R$, codimension $tR$ and $tR+\frac{R}{2}$, and saturating sets in projective spaces

The length function $\ell_q(r,R)$ is the smallest length of a $ q $-ary linear code of codimension $r$ and covering radius $R$. In this work we obtain new constructive upper bounds on $\ell_q(r,R)$ for all $R\ge4$, $r=tR$, $t\ge2$, and also for all even $R\ge2$, $r=tR+\frac{R}{2}$, $t\ge1$. The new bounds are provided by infinite families of new covering codes with fixed $R$ and increasing codimension. The new bounds improve upon the known ones. We propose a general regular construction (called ``Line+Ovals'') of a minimal $\rho$-saturating $((\rho+1)q+1)$-set in the projective space $\mathrm{PG}(2\rho+1,q)$ for all $\rho\ge0$. Such a set corresponds to an $[Rq+1,Rq+1-2R,3]_qR$ locally optimal$^1$ code of covering radius $R=\rho+1$. Basing on combinatorial properties of these codes regarding to spherical capsules$^1$, we give constructions for code codimension lifting and obtain infinite families of new surface-covering$^1$ codes with codimension $r=tR$, $t\ge2$. In addition, we obtain new 1-saturating sets in the projective plane $\mathrm{PG}(2,q^2)$ and, basing on them, construct infinite code families with fixed even radius $R\ge2$ and codimension $r=tR+\frac{R}{2}$, $t\ge1$. ($^1$ see the definitions in Section 1)

Abstract. The length function ℓ q (r, R) is the smallest length of a q-ary linear code of codimension r and covering radius R. In this work we obtain new constructive upper bounds on ℓ q (r, R) for all R ≥ 4 and r = tR with integer t ≥ 2, and also for all even R ≥ 2 and r = tR + R 2 with integer t ≥ 1. The new bounds are provided by new infinite families of covering codes with fixed R and growing codimension. The new bounds improve upon the known ones.
We propose a general regular construction (called "Line-Ovals") of a minimal ρ-saturating ((ρ + 1)q + 1)-set in the projective space PG(2ρ + 1, q) for all ρ ≥ 0. Such a set corresponds to an [Rq + 1, Rq + 1 − 2R] q R locally optimal 1 code of covering radius R = ρ + 1. In these codes, we investigate combinatorial properties regarding to spherical capsules (including the property to be a surface-covering code 1 ) and give corresponding constructions for code codimension lifting. Using the new codes as starting points in these constructions we obtained the desired infinite code families with growing r = tR.
In addition, we obtain new 1-saturating sets in the projective plane PG(2, q 2 ) and, founding on them, construct infinite code families with fixed even radius R ≥ 2 and growing codimension r = tR + R 2 , t ≥ 1.

Covering codes. The length function
Let F q be the Galois field with q elements, F * q = F q \ {0}. Let F n q be the n-dimensional vector space over F q . Denote by [n, n − r] q a q-ary linear code of length n and codimension (redundancy) r, that is a subspace of F n q of dimension n − r. The sphere of radius R with center c in F n q is the set {v : v ∈ F n q , d(v, c) ≤ R} where d(v, c) is the Hamming distance between the vectors v and c. Definition 1.1. (i) The covering radius of a linear [n, n − r] q code is the least integer R such that the space F n q is covered by the spheres of radius R centered at the codewords. (ii) A linear [n, n − r] q code has covering radius R if every column of F r q is equal to a linear combination of at most R columns of a parity check matrix of the code, and R is the smallest value with this property. Definitions 1.1(i) and 1.1(ii) are equivalent. Let an [n, n − r] q R code be an [n, n − r] q code of covering radius R. An [n, n − r] q R code of minimum distance d is denoted by [n, n − r, d] q R code. For an introduction to coverings of vector Hamming spaces over finite fields, see [5,7].
The covering density µ of an [n, n − r] q R-code is defined as the ratio of the total volume of all q n−r spheres of radius R centered at the codewords to the volume q n of the space F n q . By Definition 1.1(i), we have µ ≥ 1. In the other words, The covering quality of a code is better if its covering density is smaller. For fixed q, r, R, the covering density of an [n, n − r] q R code decreases with decreasing n. Codes investigated from the point of view of the covering quality are usually called covering codes [7]; see an online bibliography [28], works [5, 9-14, 17-20, 26, 27], and the references therein. Definition 1.2. [5,7] The length function ℓ q (r, R) is the smallest length of a q-ary linear code of codimension r and covering radius R.
From (1.1), see also Definition 1.1(ii), one obtains an implicit lower bound on ℓ q (r, R): In particular, for R = 1 we have ℓ q (r, 1) ≥ q r −1 q−1 . This means that the perfect Hamming code achieves the bound and has the covering density equal to one. The same is true for the perfect Golay codes [23,12,7] 2 3 and [11, 6, 5] 3 2. In the general case, note that the main term of the sum in (1.2) is (q − 1) R ℓq(r,R) R . If n is considerable larger than R (this is the natural situation in covering codes investigations) and if q is large enough, we have and, in a more general form, where c is independent of q but it is possible that c depends on r and R. Let t, s, R * be integers. Let q ′ be a prime power. In [11,13,14,17], see also the references therein, for the situations (i) r = tR, arbitrary q, (1.4) (ii) R = sR * , r = tR + s, q = (q ′ ) R * , [n, n − r] q R covering codes are obtained with lengths of the form n = c 1 (r, R)q (r−R)/R + i≥2 c i (r, R)q (r−R)/R−µ i , c 1 (r, R) > 1, µ i > 0, (1.5) where all c i (r, R) are constants independent of q. Also, for i ≥ 2, one usually has c i (r, R) ≥ 0, but it is possible that c i (r, R) < 0, see for example Propositions 1.6 and 1.7. For growing q, code length n of (1.5) is close (by order) to the bound (1.3) since all µ i > 0.
In this work, we consider the case (i) of (1.4) for R ≥ 4 and the situation (ii) for even R with R * = 2. We briefly describe the known results and then improve upon many of them by constructing new codes.
For new codes with r = tR we note and use interesting and useful combinatorial properties connected with the locally optimality, R, ℓ-capsules and R, ℓ-objects. Definition 1.3. [12] A linear covering code is called locally optimal if one cannot remove any column from its parity check matrix without increase in covering radius. A locally optimal code can be called also non-shortening in the sense mentioned.  [14,Sect,2] Let 0 ≤ ℓ ≤ R. A linear [n, n − r] q R code of covering radius R is called an R, ℓ-object and is denoted as an [n, n − r] q R, ℓ code if any of following holds.
(i) The space F n q is covered by the R, ℓ-capsules centered at the codewords. (ii) Every column of the space F r q (including the zero column) is equal to a linear combination with nonzero coefficients of at least ℓ and at most R distinct columns of a parity-check matrix of the code.
(iii) Every coset of the code (including the code itself) contains a weight w word of the space F n q such that ℓ ≤ w ≤ R. Definitions 1.4(i), 1.4(ii), and 1.4(iii) are equivalent. In [9,10,14] widened definitions of R, ℓ-objects are considered. But for this work, Definition 1.4 is sufficient.
Note that the R, R-capsule is the surface of the sphere of radius R.
Definition 1.5. An [n, n − r] q R, R code is called surface-covering code of radius R.
The value of ℓ is important for code codimension lifting constructions, see Section 4.

The known results
Codes with radius R = 2, 3 and codimension r = tR are widely investigated for arbitrary q, see [11], [14,Sects. 4,5], [17,Ths. 9,12]. At the same time, codes with R ≥ 4 and r = tR are investigated insufficiently; moreover, the known results on these codes are obtained by use of codes with R = 2, 3 in the so-called direct sum construction [14,Sect. 4.2]. The following results on codes with R ≥ 4 and r = tR are described in the literature.

Saturating sets in projective spaces
Effective methods to obtain upper bounds on ℓ q (r, R) are connected with saturating sets in projective spaces. Let PG(N, q) be the N-dimensional projective space over the field F q ; see [21][22][23] for an introduction to the projective spaces over finite fields, see also [19,22,26,27] for connections between coding theory and Galois geometries.
is ρ-saturating if for any point A of PG(N, q) \ S there exist ρ + 1 points in S generating a subspace of PG(N, q) containing A, and ρ is the smallest value with such property.
Note that for n < (ρ + 1)q + 1 = Rq + 1, no examples of ρ-saturating n-sets in PG(2ρ + 1, q) (resp. [n, n − 2R] q R codes with R = ρ + 1) seem to be known. Moreover, in [14,Prop. 4.2], it is proved that ℓ 4 (4, 2) = s 4 (3, 1) = 2 · 4 + 1. This strengthens the interest to Problem 2 and gives rise to the following.  If the positions of a column of a parity check matrix of an [n, n − r] q R locally optimal code are considered as homogeneous coordinates of a point in PG(r −1, q) then this parity check matrix defines a minimal (R − 1)-saturating n-set in PG(r − 1, q) [12]. So, there is a a one-to-one correspondence between [n, n − r] q R locally optimal codes and minimal (R − 1)-saturating n-sets in PG(r − 1, q).
Note that the codes providing the bounds of Proposition 1.7 are based on 1-saturating sets in the projective plane of square order. Improvements of these bounds could be connected with new 1-saturating sets of relatively small sizes.
Problem 4. In PG(2, q 2 ), construct new 1-saturating sets with sizes smaller than the known ones.

The goals and the structure of the paper
The goals of this paper: • solve Problem 2 and with the help of the new [Rq + 1, Rq + 1 − 2R] q R codes solve Problem 1(i) regarding codes of covering radius R ≥ 4 and codimension tR; • solve Problem 4 and with the help of the new 1-saturating sets solve Problem 1(ii) regarding codes with even covering radius R ≥ 2 and codimension tR + R 2 . The paper is organized as follows. In Section 2 we collect the main results of the paper. In Section 3, we propose a construction "line plus ρ ovals" for ρ-saturating sets in PG(2ρ+ 1, q) and codes of codimension 2R. This solves Problem 2. In Section 4, we describe two constructions from the family of the so-called "q m -concatenating constructions" for code codimension lifting. The constructions are convenient for [n, n − r] q R, ℓ codes with ℓ ∈ {R − 1, R}. In Section 5, we prove that the codes obtained in Section 3 have ℓ = R for odd q and ℓ = R − 1 for even q. (So, for odd q we have surface-covering codes.) Then we use these codes as starting ones for the constructions of Section 4. As the result, we obtained new infinite code families with fixed radius R ≥ 4 and growing codimension tR. This solves Problem 1(i) for the most part. In Section 6, using recent results on double blocking set, we obtain new 1-saturating sets in PG(2, q 2 ) that solve in part Problem 4. Then basing on these sets, we obtain new infinite code families for all fixed even radii R ≥ 2 and growing codimension tR + R 2 . This solves in part Problem 1(ii).
• Problem 1(i) is solved for the most part, see Sections 4 and 5. We described two constructions for code codimension lifting. Using the [Rq + 1, Rq + 1 − 2R] q R codes as a start for these constructions, we obtained infinite code families with fixed radius R ≥ 4 and growing codimension tR. These families improve the known results collected in Proposition 1.6 apart from t = 3. New bounds on the length function obtained in this paper are given in Theorem 2.1 based on Theorems 3.8, 3.10, 5.3, 5.4.
Theorem 2.1. Let t be a growing integer. For the length function ℓ q (r, R) and for the smallest size s q (r −1, R −1) of a (R −1)-saturating set in the projective space PG(r −1, q) the following constructive upper bounds (provided by infinite families of codes) hold: The new bounds of Theorem 2.1 are better than the known ones of Proposition 1.6. In particular, in Proposition 1.6, the coefficient for q (r−2R)/R is R 3 , whereas in Theorem 2.1 it is equal to 1 or 2, see (i)-(iii) and (iv)-(v), respectively. Note that in the cases (iv)-(v), the coefficient is equal to 2 since the term with j = 2 of the sum in ∆ q (r, R) is q (r−2R)/R .
• Problem 4 is solved in part, see Section 6. Throughout the paper we use the following notation: In Theorem 6.3(v),(vi), using recent results on double blocking set, it is shown that in PG(2, q) there are 1-saturating sets of the following sizes: The new 1-saturating sets have smaller sizes than the known ones, see Remark 6.4.
• Problem 1(ii) is solved in part, see Section 6. Using the new 1-saturating sets in P G(2, q), we obtained infinite families of codes with covering radius R = 2, see Theorem 6.9, and, basing on them, we constructed infinite code families with fixed even radius R ≥ 2 and growing codimension tR + R 2 , see Theorem 6.11 that gives rise to Theorem 2.2. Theorem 2.2. Assume that p is prime, q = p 2η , η ≥ 2, covering radius R ≥ 2 is even, and code codimension is be as in (2.1), (2.2). The following constructive upper bounds on the length function (provided by infinite families of codes with growing codimension) hold: 3 Construction "Line-Ovals" for ρ-saturating sets in PG(2ρ + 1, q) and codes of codimension 2R Notation. Throughout the paper we denote by x i , i = 0, 1, . . . , N, the homogeneous coordinates of points of P G(N, q). In the other words, a point ( The leftmost nonzero coordinate is equal to 1. In general, by default, Also, we can write explicit values 0,1 for some coordinates or denote coordinates by letters values of which is explained later.

The construction
Let F q = {a 1 = 0, a 2 , . . . , a q } be the Galois field of order q. Let F * q = F q \ {0} = {a 2 , . . . , a q }. Denote Σ ρ = PG(2ρ + 1, q). Let Σ u be the (2u + 1)-subspace of Σ ρ such that In Σ u , let π u be the plane such that In π u , let A 0 u and A ∞ u be the points of the form In π u , let C u and C * u be the conic and the truncated one, respectively, of the form Let T u be the nucleus of C u , if q is even, or the intersection of the tangents to C u in A 0 Also, let L 0 and L * 0 be the line and the truncated one, respectively, such that Construction S. ("Line-Ovals") Let ρ ≥ 0. Let S ρ be a point ((ρ + 1)q + 1)-subset of Σ ρ . Let P j be the j-th point of S ρ , j = 1, 2, . . . , (ρ + 1)q + 1. We construct S ρ as follows: The points P j of S ρ have the form

Saturation of Construction S for
Note that by Definition 1.8, a 0-saturating set in P G(N, q) is the whole space.
The following proposition is obvious.
If q is even, every point of a plane outside of a hyperoval C u ∪ {T u } lies on (q + 2)/2 its bisecants. If q is odd, every point of a plane outside of a conic C u lies on at least (q − 1)/2 its bisecants. At most two of aforementioned bisecants will be removed if The proof is similar to the case (i) taking into account that here we remove only one point A 0 ρ from C ρ .
Proof. (i) By Proposition 3.3(iii) and Lemma 3.4, Σ 0 (points (x 0 x 1 00)) and π 1 (points (0x 1 x 2 x 3 )) are 1-covered by So, we should consider points of the form We show that B in (3.5) is a linear combination of at most 2 points of S 1 .
From (3.9)-(3.12) we see that all points of S 2 \ S 1 are 2-essential. Also, we take into account that S 1 is a minimal 1-saturating set.
(i) By Propositions 3.3, 3.6, 3.7, Lemmas 3.4, 3.5, and Assumption, we have the following: So, we should consider points of the form (3.14) We show that B in (3.14) is a linear combination of at most Γ + 1 points of . By the hypothesis and by (3.13), 2) Let (x 0 . . .
From (3.15)-(3. 19) we see that all the points of S Γ \ S Υ are Γ-essential. Also, we take into account that S Υ is a minimal Υ-saturating set.

Codes of covering radius R and codimension 2R
In the coding theory language, the results of this section give the following theorem.
Theorem 3.10. Let V ρ be the code such that the columns of its parity check matrix are the points (in the homogeneous coordinates) of the ρ-saturating ((ρ + 1)q + 1)-set S ρ of Construction S (3.1), (3.2).
Proof. We use Theorem 3.8 and Proposition 3.9. The code V ρ is locally optimal as the corresponding ρ-saturating set S ρ is minimal. Minimum distance d = 3 is due to L * 0 .

The q m -concatenating constructions for code codimension lifting
The q m -concatenating constructions are proposed in [9] and are developed in [10-12, 14, 17,18], see also [5], [7,Sec. 5.4] and the references in these works. By using a starting code as a "seed", a q m -concatenating construction yields an infinite family of new codes with a fixed covering radius, growing codimension and with almost the same covering density. We give versions of the q m -concatenating constructions convenient for our goals. Several other versions of such constructions can be found in [9][10][11][12]14,17,18] and the references therein. In Construction QM 1 below, we use a surface-covering code as a starting one, whereas for Construction QM 2 we need to start with an [n, n − r] q R, ℓ code, ℓ = R − 1. Resulting codes of both the constructions are surface-covering.
Construction QM 1 . Let columns h j belong to F r 0 q and let H 0 = [h 1 h 2 . . . h n 0 ] be a parity check matrix of an [n 0 , n 0 − r 0 ] q R, R starting surface-covering code V 0 with R ≥ 2. Let m ≥ 1 be an integer such that q m ≥ n 0 − 1. To each column h j we associate an element where B j is an (r 0 + Rm) × q m matrix, 0 is the zero element of F q m , ξ u is an element of F q m , {ξ 1 , ξ 2 , . . . , ξ q m } = F q m . An element of F q m written in B j denotes an m-dimensional q-ary column vector that is a q-ary representation of this element.
Theorem 4.1. In Construction QM 1 , the new code V with the parity check matrix (4.1), (4.2) is an [n, n − (r 0 + Rm), 3] q R, R surface-covering code with covering radius R and length n = q m n 0 . Moreover, if the starting code V 0 is locally optimal (non-shortening), then the new code V is locally optimal too.
Proof. The length of the code V directly follows from the construction.
The minimum distance d is equal to 3 since for any pair of columns b j (ξ u 1 ), b j (ξ u 2 ) of B j , a 3-rd one can be found such that the column triple corresponds to a codeword of weight 3. Take a, b, c ∈ F * q with a + b + c = 0. Put ξ u 3 = (−aξ u 1 − bξ u 2 )/c. Then for all j we have where 0 is the zero (r 0 + Rm)-positional column. We show that covering radius R V of V is equal to R.
Since V 0 is an [n 0 , n 0 − r 0 ] q R, R code, there exists a linear combination of the form where values of x k are obtained from the linear system with nonzero determinant. If for j k in (4.4) we have β j k ∈ F q m for all k, then the system has the form As usual, we put 0 0 = 1. If in (4.4) we have, for example, β j R = * , then the system is as follows: If V 0 is a locally optimal code, then every column h j of H 0 takes part in a representation of the form (4.4). If we remove b j k (ξ u ) from B j k then there is (s 1 , s 2 , . . . , s Rm ) such that the system (4.6) or (4.7) gives x k = ξ u . As a result, for some t the representation (4.5) becomes impossible. So, all columns of H V are essential and the code V is locally optimal.
Construction QM 2 . Let θ m,q = q m+1 −1 q−1 . Let columns h j belong to F r 0 q and let H 0 = [h 1 h 2 . . . h n 0 ] be a parity check matrix of an [n 0 , n 0 − r 0 ] q R, ℓ 0 starting code V 0 with ℓ 0 = R − 1, R ≥ 2. Let m ≥ 1 be an integer such that q m ≥ n 0 . To each column h j we associate an element β j ∈ F q m so that β i = β j if i = j. Let a new code V be the [n, n − (r 0 + Rm)] q R V , ℓ V code with n = q m n 0 + θ m,q and parity check matrix of the form where B j is an (r 0 + Rm) × q m matrix as in (4.2), C is an (r 0 + Rm) × θ m,q matrix,  is an [n, n − (r 0 + Rm), 3] q R, R surface-covering code with covering radius R and length n = q m n 0 + q m+1 −1 q−1 . Moreover, if the starting code V 0 is locally optimal (non-shortening), then the new code V is locally optimal too.
Proof. The length of the code V directly follows from the construction.
The minimum distance is equal to 3 as the Hamming code is a code with d = 3. Also we can use (4.3) from the proof of Theorem 4.1.
We show that covering radius R V of V is equal to R.
Since V 0 is an [n 0 , n 0 − r 0 ] q R, ℓ 0 code with ℓ 0 = R − 1, there exists a linear combination of ϕ(f) distinct columns of H 0 of the form see Definition 1.4. If ϕ(f) = R we act similarly to the proof of Theorem 4.1.
Let ϕ(f) = R − 1. We represent t as a linear combination (with nonzero coefficients) of at most R distinct columns of H V . We have, see (4.2), (4.9), where c is a column of C and η = 0 means that the summand ηc is absent. Also, in (4.10), values of x k are obtained from the linear system with nonzero determinant. Finally, in (4.10), c = (0w) where 0 is the zero (r 0 +(R−1)m)positional column and w is a column of W m that satisfies the equality the needed column ηw always exists as the Hamming code has covering radius 1. Now we show that V is an [n, n − (r 0 + Rm), 3] q R, R code, i.e. ℓ V = R. The critical situation is when in (4.10) and (4.11) η = 0, i.e. the summand ηc is absent. We use the approach of the proof of Theorem 4.1 regarding (4.3). In (4.3) we put j = j 1 , ξ u 1 = x 1 , a = −c 1 with j 1 , x 1 , c 1 taken from (4.10). Then Thus, we always can represent t ∈ F r 0 +Rm q as a linear combination with nonzero coefficients of exactly R columns of H V .
By above, if we remove any column of H V , some representation of t becomes impossible. So, all columns of H V are essential and the code V is locally optimal.

New infinite code families with fixed radius R ≥ 4 and growing codimension tR
In the minimal ρ-saturating set of Construction S (3.1), (3.2), we consider a point P j (in the homogeneous coordinates) as a column h j of the parity check matrix H ρ that defines the [qR + 1, qR + 1 − 2R, 3] q R, ℓ locally optimal code V ρ of covering radius R = ρ + 1.
We consider some properties of H ρ useful to estimate ℓ. Let f ∈ F r q . Let J (f) = {h j 1 , . . . , h j β } and I w = {h i 1 , . . . , h iw } be sets of distinct columns of H ρ such that f = β k=1 c k h j k , h j k ∈ J (f) and c k ∈ F * q for all k; (5.1) w k=1 m k h i k = 0, h i k ∈ I w and m k ∈ F * q for all k, 0 ∈ F r q is the zero column; Note that I w is a set of columns corresponding to a weight w codeword of V ρ . In the representation (5.3), the number of distinct columns of H ρ , say β new , depends on the intersection I w ∩J (f) and the values of nonzero coefficients c k , m k , µ. For example, To use (5.3), (5.4), note that submatrices of H ρ can be treated as parity check matrices of codes; we call them component codes and write in Table 1, where u = 1, . . . , ρ, "MDS" notes a minimum distance separable code and "AMDS" says on an Almost MDS code.

AMDS
Remark 5.1. The weight spectrum of MDS codes is known, see e.g. [29]. In particular, in [n, n − r, d] q MDS code any d columns of a parity check matrix correspond to a weight d codeword. If q odd, for AMDS component codes C T u and C ∞T ρ we note that T u lies on two tangents to C u (in A 0 u , A ∞ u ) and on q−1 2 bisecants of C * u . Every of these bisecants gives rise to a weight 3 codeword. The (q − 1)-set of points of C * u is partitioned by q−1 2 point pairs; every pair forms a bisecant through T u .
Note that from the proofs of Section 3 it can be seen that for the representation of a column f ∈ F r q it is sufficient to use (for every u) at most 3 columns corresponding to C * u . Similarly, one can use 2 columns corresponding to {A 0 0 } ∪ L * 0 . Therefore, if q ≥ 7 we have in {A 0 0 } ∪ L * 0 and in every C * u several points (columns) that can be used to form sets I w useful to increase β and β new in (5.2)- (5.4).
Assume that for a column f ∈ F r q we have the representation (5.1) with 1 ≤ β < R. Then using weight w codewords of the component codes we can increase β by w, w − 1, w − 2, see (5.4). The increase by w − 1, w − 2 is possible if some column of J (f) and I w corresponds to the same component code. In particular, the situations with w = 3, w − 2 = 1 can be provided if some column or a column pair of J (f) and I w correspond to the same code L 0 (for all q) or to the same code C T u , C ∞T ρ (for q odd). There exist columns f ∈ F r q such that L 0 is not used for their representation. Therefore, in general, for even q (where MDS codes C T u , C ∞T ρ have minimum distance d = 4) we are not able to do β new = R when β = R − 1, see (5.3), (5.4). In the other side, for odd q, AMDS codes C T u , C ∞T ρ have d = 3 that allows us to increase β by w − 2 = 1. Note also, see Remark 5.1, that for q ≥ 7 the structure of minimum weight codewords in the component codes provides the situation that some columns of J (f) and I w correspond to the same code.
By above, we have the following lemma. In Theorems 5.3 and 5.4 we consider R ≥ 4 since for R = 1, 2, 3, several short covering codes with r = tR are given in detail in [11,13,14,16,17] and the references therein. Theorem 5.3. Let q ≥ 7 be odd. Let t be an integer. Then for all R ≥ 4 there is an infinite family of [n, n − r, 3] q R, R locally optimal surface-covering codes with the parameters n = Rq (r−R)/R + q (r−2R)/R , r = tR, t = 2 and t ≥ ⌈log q R⌉ + 3.
6 New infinite code families with fixed even radius R ≥ 2 and growing codimension tR + R

2
In the projective plane PG(2, q), a blocking (resp. double blocking) set S is a set of points such that every line of PG(2, q) contains at least one (resp. two) points of S. There is an useful connection between double blocking sets and 1-saturating sets.  [25] Let q be a square. Any double blocking set in the subplane PG(2, √ q ) ⊂ PG(2, q) is a 1-saturating set in the plane PG(2, q).
Note also that if q = p 2 , i.e. η = 1, then the size (i) is the smallest in Theorem 6.3. It is why we pay attention to this case, see Remarks 6.5-6.7 and Problem 5 below.
Remark 6.5. Let a point of PG(2, q) have the form (x 0 , x 1 , x 2 ) where x i ∈ F q , the leftmost nonzero coordinate is equal to 1. Let β be a primitive element of F q .
Proof. Let n q be the size of the 1-saturating sets of Theorem 6.3(iii),(iv). We treat every point (in homogeneous coordinates) of the set as a column of an 3×n q parity check matrix of an [n q , n q − 3] q 2 code. For these codes it can be shown that n q < q and q + 1 ≥ 2n q . Then we use Proposition 6.8.
The direct sum construction [14,Sect. 4.2] gives the following lemma.


s2fieldsofstudy:
Computer Science
Business

text:
Cross Layer Design for Maximizing Network Utility in Multiple Gateways Wireless Mesh Networks

We investigate the problem of network utility maximization in multiple gateways wireless mesh networks by considering Signal to Interference plus Noise Ratio (SINR) as the interference model. The aim is a cross layer design that considers joint rate control, traffic splitting, routing, scheduling, link rate allocation and power control to formulate the network utility maximization problem. As this problem is computationally complex, we propose the Joint dynamic Gateway selection, link Rate allocation and Power control (JGRP) algorithm based on the differential backlog as a sub-optimal solution. This algorithm first constructs the initial network topology, and then in each time slot, determines the generation rate and destination gateway of each traffic flow, simultaneously. The other main task of this algorithm is joint routing, scheduling, links rate allocation and node power allocation in each time slot. Moreover, for improving the fairness, we propose some new parameters instead of the differential backlog in JGRP algorithm. Simulation results show that using the proposed parameters in JGRP algorithm improves fairness from throughput and delay point of views.

I. INTRODUCTION We study the network utility maximization problem by jointly considering rate control, traffic splitting among gateways, routing, scheduling, link rate allocation and power control in multiple gateways wireless mesh networks. Over the past two decades, the mesh structure has been considered as an appropriate solution to increase the coverage area and capacity of wireless networks [1]. Important features of the wireless mesh networks include low cost deployment, distributed communication and robustness. However, the performance of these networks could be degraded, which is mainly due to poor design of network protocols [2], [3].
In recent years, various approaches have been provided to improve the performance of wireless mesh networks, among them is cross layer design which could be performed with various aims, such as improvement of throughput, delay and other network parameters. Another approach is using multiple gateways in these networks. In the following, we briefly review some related works according to these approaches.
First, some researches on cross layer design in wireless mesh networks. In [4], the authors investigated joint routing, channel assignment, power control and rate adaptation to improve the throughput, load balancing and fault-tolerant in multi-radio multi-channel wireless mesh networks. As this problem is NPhard, they proposed a heuristic algorithm with two levels. In the first level, a K-connectivity network topology is created using channel assignment and routing. In the second level, power control, rate adaption and scheduling are jointly considered for maximizing the throughput while K-connectivity network topology is preserved. In order to maximize the capacity of multi-radio mult-channel wireless mesh networks, the authors in [5], considered the link rate allocation, routing and channel assignment. In [6] the scheduling and routing design are performed jointly with the aim of minimizing the superframe length to support any random demand in multi-Tx/Rx wireless mesh networks. The authors of [7] considered joint scheduling and routing in multi-Tx/Rx wireless mesh networks for minimizing the endto-end delays and superframe length. In [8], joint optimization of channel assignment, power control and routing is investigated under the Signal to Interference plus Noise Ratio (SINR) model with the aim of some new parameters instead of the differential backlog to improve the fairness of our JGRP algorithm.
The rest of the paper is organized as follows: In Section II, we describe the network model. In Section III, the network utility maximization problem is formulated. Section IV describes the proposed JGRP algorithm as a sub-optimal solution to solve the network utility maximization problem. In Section V, we attempt to improve the fairness by defining some new parameters. We provide some simulation results in Section VI, and finally Section VII concludes the paper.
II. NETWORK MODEL We consider a wireless mesh network, where we have N mesh nodes and L links. We model the network with directed graph G = (Γ, E), where Γ is the set of mesh nodes and E is the set of links. We assume that there are multiple gateways in this networks and GW ⊂ Γ represents the set of mesh gateways.

A. Interference Model
In order to model the interference, we consider SINR model, where two directed links (p, q),(i, j) could be activated with r i j and r pq rates, simultaneously if and only if these links satisfy the following conditions: where P i j is the transmission power from node i to node j, β(r i j ) is the SINR threshold for acceptable bit error probability, and N 0 is the background noise power. Moreover, G i j denotes the channel gain between nodes i and j and equals G i j = ( where d i j is the distance between nodes i and j, d 0 is the reference distance and α denotes the path loss exponent.

B. Scheduling, Link Rate Allocation and Power Control
Considering the interference model, scheduling specifies which of the links could be activated, simultaneously. We represent the set of feasible schedules with Φ and the vector s m as the m th feasible schedule in which the links with common nodes could not be activated. We denote the element of s m corresponding to link (i, j) with Y m i j which is equal to one if the link (i, j) is activated in this schedule and zero, otherwise. In addition, π m denotes the fraction of time slot when s m is activated. Now, we extend equation (1) for a feasible schedule as follows: where the links may have different transmission rates and powers in nonidentical feasible schedules. Assuming that Y m i j = 1, r m i j is the allocated rate to link (i, j) and P m i j is the transmit power from node i to node j where the transmission rate is equal to r m i j .

C. Traffic and Queueing Model
Traffic Model: We assume that the number of traffic flows in our network is K, where F = {1, 2, ..., K } represents the set of all traffic flows in the network. We show the acceptable amount of traffic for flow f at time slot t by r where s( f ) is the source node of flow f and considering f : ∀i ∈ Γ as a constraint that shows the limitation of each node i in generating traffic. We assume that each of the gateways could be chosen as the destination of the packets of each flow f , where y ( f ) d shows the fraction of the traffic of flow f forwarded to gateway d.
Queening Model: We assume that there are multiple queues in each node, where each queue is corresponding to one of the gateways. The packets corresponding to a gateway lie in the same queue, even if they belong to different flows. We represent the length of the queue in node i corresponding to gateway d at the beginning of time slot t by Q (d) i (t), where the queue of gateway d corresponding to this gateway is assumed empty, i.e., Q (d) d (t) = 0. In addition, we denote the number of packets belong to destination d, which is transmitted over link (i, j) at time slot t by µ (d) i j (t) and the long term average of this parameter by µ (d) i j . Moreover, we represent all traffic on link (i, j) by µ i j . By these definitions, it is clear that the queue evolution is as follows [25]: is the input traffic to node i from upstream nodes and is the generated traffic in node i.

III. PROBLEM FORMULATION
Now, we formulate the network utility maximization problem under the constraints corresponding to scheduling, rate control, link rate allocation and power control. We define r = [r (1) s (1) , r (2) s (2) , . . . , r (K) s(K) ] T as the long-term average traffic vector. The aim is to maximize of the sum of long-term average traffics of all network flows. Moreover, as we would like to have fairness among the flows, log(.) function is considered as the utility function of the problem, which is also considered in [13], [14], [24], d∈GW The constraint (4b) states that the total input traffic rate to the queue of gateway d in node i must be equal to the output traffic rate from this queue. The constraint (4c) ensures that the total traffic of flow f is forwarded to the gateways. The constraint (4d) indicates that the sum rate transmitted over link (i, j) by different destinations must be equal to all traffic rate on the link (i, j). The constraint (4e) means that sum of the fractions of the time slot corresponding to various feasible schedules must be equal to one. The constraint (4f) ensures that the allocated rate and the activation time of the link (i, j) are enough for carrying the desired amount of traffic, where l t and l p represent the duration of each time slot and packet length, respectively. The constraint (4i) shows that each of the nodes in each scheduling could not be connected to more than one of the other nodes. The constraint (4j) limits the transmission power of the nodes.
IV. SUB-OPTIMAL SOLUTION We must note that problem (4) is NP-hard (see e.g. [26]), then in this section, we propose a sub-optimal solution to solve the network utility maximization problem (4). Accordingly, we offer JGRP algorithm which has three parts: • In the first parts, we prune the full mesh network and form an initial network topology to reduce the computational complexity of the third part of the algorithm. • In the second part, we jointly obtain the mechanism of the traffic splitting and rate control. • In the third part, we determine the routing, scheduling, rate allocation to the links and power allocation to the nodes, Simultaneously. We must note that the first part of the algorithm runs at the beginning (before network operation) ; but other parts run repeatedly at the beginning of each time slot.

A. Construction of Initial Network Topology
Assume that the number of links that could be connected to each node is an integer number between N 3 and 2 N 3 , where N is the number of the nodes. Considering the channels between the nodes, we propose Algorithm 1 to form the initial network topology.
Algorithm 1 Constructing the initial network topology. Require: The set of the mesh nodes Γ, The channel gains between nodes i, j ∈ Γ G i j .
1: For each node i, arrange the other nodes decreasingly, according to the channel gains between each of the nodes and node i. 2: Considering the priorities of all the nodes based on ordering in step 1, establish a link between the nodes which are in the first N 3 priority of each other.
For each node i which is not connected to its j th priority node, if the number of the links of the j th priority node of node i is equal to k, establish a link between this node and its j th priority node. 6: end for 7: end for

B. Rate Control and Traffic Splitting
Similar to [24], at the beginning of each time slot t, the rate controller at the source node s( f ) of each flow f ∈ F selects the gateway with the shortest queue length and enters the traffic to the queue as follows: r where V is a constant parameter which controls the trade-off between the network utility and the queue length, d * is the gateway which has the shortest queue in s( f ) and

C. Routing, Scheduling, Link Rate Allocation and Power Control
For each link (i, j), the differential backlog is defined as, This parameter specifies the gateways whose traffic is carried over link (i, j). In addition, the differential backlog is related to the amount of congestion at nodes i and j.
We must note the existed congestion in the nodes and maximization of the network links throughput during the specification of routing, scheduling and the rate allocation to the links and the power allocation to the nodes. In this end, we involve W i j , π m and r m i j in the objective function of the problem to consider the amount of congestion of the nodes and the throughput of the links. So, we formulate the problem as follows: In order to solve the problem (7), we first assume that the variable π m be constant and reformulate the problem as follows: In problem (8) the variables r m i j and β(r m i j ) should be selected from the discrete set of allowable rates and the variable Y m i j is binary. Accordingly, we need a full search to obtain the optimal solution, which is not practical. Hence, we propose a sub-optimal search (Algorithm 2) to solve the problem. As a prerequisite, we rewrite the SINR constraints corresponding to a typical set of links which have not any common nodes denoted by S ⊂ E. In other words, for all values of (i k , j k ) ∈ S and (i n , j m ) ∈ S, we have i m i n , i m j n , j m i n , j m j n . The SINR constraint for link (i k , j k ) would be, By replacing the inequality to equality in the above constraint, we have: Now, by writing (10) for all links, we have: Where matrix A is: Then, in Algorithm 2 after solving problem (8), in finally step of this algorithm, we obtain π 1 , . . . , π M by solving the following problem:s V. IMPROVEMENT OF THE FAIRNESS In Algorithm 2 for link rate allocation and finding the active feasible scheduling in each time slot, we only considered the congestion of the nodes and the total rate of the activated links in each scheduling. Moreover, we allocated more rate to the links with larger W i j . This approach does not lead to an acceptable fairness among the flows from the average delay and throughput point of views. In this section, in order Algorithm 2 Obtaining joint scheduling, routing, power control and link rate allocation. Require: The graph of the network the channels between the nodes i and j ∀i, j, The set of rates in the Standard 802.11a; R = {R 1 , R 2 , . . . , R 8 |R 1 > R 2 · · · > R 8 }, the set of SINRs corresponding to the rates in the set R; β = {β(R 1 ), . . . , β(R 8 )}, the length of queue corresponding to gateway d in node i; Q d i (t). Ensure: The activated schedules, the rates of the links and the power of the nodes, in each time slot.
1: For each link (i, j) ∈ E, compute the differential backlog as: 2: Sort W i j s decreasingly and lie them in the first row of W sort ∈ R 3×L , and set the second and third row of the column of W sort corresponding to W i j , as [i, j] T . Set the rate of the link corresponding to [W sort ] 1q , as R n , set SINR of this link as β(R n ) and set temp r = {R n } ∪ R s m .

11:
Considering the saved rates in temp r , formulate problem (11) for temp and compute the powers; If the power of all nodes in temp were positive and smaller than P max , set r m i j = R n , R s m = temp r , sch m = temp and [W 1 ] q = 1. to improve the fairness among the traffic flows, we define some new parameters to be used in Algorithm 2 instead of W i j . These parameters are explained in the following, 1) Let R (T) i j (t) be sum of the allocated rates to link (i, j) until the beginning of time slot t and define W (r) i j as: By using W (r) i j , the proposed algorithm allocates higher rates to the links to which we allocated less rate before the beginning of time slot t. 2) Let D i j as, By using W (D) i j , we increase the probability of sending the packets which have experienced more delay.
3) In order to have trade-off between the packets delay and the allocated rate to links, we define W (r,D) i j as, 4) Assume d ∈ GW be the gateway corresponding to W i j and R (T,d) i j (t) be the sum of allocated rates to link (i, j) for transmitting the traffic of gateway d until the beginning of time slot t. We define W (r d ) i j as, 5) In order to jointly consider all of the previously defined parameters related to delay, allocated rate to the links and allocated rate to transmit the traffic of the gateways, we define W (r d ,D) i j as, VI. SIMULATION RESULTS In order to evaluate and compare the proposed algorithms some simulation results are provided. the algorithms are implemented using MATLAB. In all simulations, we assume eight flows and two gateways. We set the simulation parameters as shown in Tables I and II.

A. Investigation of the performance of JGRP algorithm
In the simulated network, 10 nodes are distributed in 350m × 350m square area uniformly. By running Algorithm 1, the topology is constructed as shown in Fig. 1. We select two nodes 1 and 10 (which have the maximum distance from each other) as the mesh gateways, and we assume that nodes 2 to node 9 are the sources of traffic flows numbered 1 to 8, respectively. We run JGRP algorithm based on the six parameters W i j , W (r) In Fig. 2, we observe that by using the JGRP algorithm based on W i j , the throughput of different flows are different and therefore there is no fairness among flows. Moreover, we observe that this algorithm based N 0 power of background noise [27] −90 dBm α path loss exponent [28] 3 d 0 reference distance 10 m duration of time slot [29] 625 µs packet length [29] 1470 bytes V [24] 30 R max i [24] 10 P max 20 dBm , the throughput of various flows are close to each other. This is because of the reduction in throughput of the flows which achieve more throughput using parameters W (r) i j , W (D) i j and W (r d ) i j . In Fig. 3, we observe that by using JGRP algorithm based on W i j , the number of packets corresponding to various flows received by the gateways are very different. Moreover, it can be observed that using JGRP algorithm based on W (r) i j increases the number of packets received by the gateways from flows 4 and 5 whose source nodes are not connected directly to the gateways. Furthermore, we observe that using parameters W (r,D)  In Fig. 4, we observe that using W (r) i j improves the delay of all traffic flows which have high delay using W i j parameter. But, using the parameters W (D) i j and W r d (i, j) improves the delay of only some of those flows. Moreover, we observe that using parameters W (r,D) So far we investigated fairness using intuitive metrics. Now, we use the Jain's fairness index to indicate the amount of fairness more accurately. If x 1 , . . . , x n be the samples of random variable X and x i > 0, i = 1, . . . , n, then the Jain's fairness index is defined as [31]: where 0 < JF I ≤ 1 and JF I = 1 indicate the complete fairness. Replacing x i s in equation (19) with the desired parameters, the amount of the fairness corresponding to each of these parameters could be obtained. Here, we would like to investigate the fairness from throughput and delay points of view; then we substitute the parameters such as the throughput of each flow, the average delay of each flow and the ratio of the throughput and the average delay of each flow in (19). Then, we obtain the amount of    Table III. From this table, we observe that Jain's fairness index corresponding to throughput for W (r,D) i j and W (r d ,D) i j is equal to one, which means that employing these parameters, complete fairness will be provided among flows. Comparing JFI corresponding to the average delay of flow packets, we observe that all parameters W (r) i j obtain the most amount of fairness. By considering the ratio of the throughput and the average delay of each flow as the parameter of Jain's fairness index, we can compare the fairness from both of the throughput and delay point of views as shown in the third row of Table III. We observe that parameters W (r,D) i j although improve the fairness in comparison with using W i j parameter, increase the average delay and reduce the aggregate throughput and the number of packets received by the gateways. Therefore, in order to justify the performance of this algorithm, for each flow, , we show the ratio of the number of packets received by each gateway to the number of packets sent to that gateway for each flow in Tables IV and V. In Table IV, we observe that by using W i j , W (r) i j , W (D) i j and W (r d ) i j , gateway 1 almost does not receive the packets of flows which their source nodes is connected directly to gateway 2, but by using W (r,d) i j these packets are received more. This fact is also true for nodes with direct link to gateway 1 as shown in Table V. This is because the mentioned parameters consider the rate of links and the delay of packets simultaneously, and this leads to the result that the intermediate links be activated and all the flows be communicated to all the gateways. Due to the multi-hop distance between the nodes and the non-adjacent gateway, the activation of intermediate links increases the average delay and decreases the aggregate throughput. Now, we investigate the performance of the JGRP algorithm in networks with different sizes by running it based on all the parameters on the networks with 10, 15 and 20 nodes over 2600 time slots. For simulating networks with 15 and 20 nodes, we respectively distribute 15 and 20 nodes in a 450m × 450m and 500m × 500m square areas uniformly. Then, we form the topology of each of the networks using Algorithm 1. In order to obtain the simulation results of the networks with 15 and 20 nodes, we randomly select eight nodes as source nodes of the flows. We compare the simulation results of the networks with 10, 15 and 20 nodes as shown in Tables VI, VII, VIII and IX.
In Table VI, we observe that JGRP algorithm based on W i j obtains the most aggregated throughput in the networks wit all three 10, 15 and 20 nodes. Moreover, we observe that while increasing the number of nodes, the aggregated throughput obtained by JGRP algorithm based on W i j is not reduced. But, in JGRP algorithm based on the other parameters, the aggregated throughput is reduced when the number of the nodes is increased. This subject has two reasons; the first reason is that by using parameters W (r) i j , i j , in each time slot, the packet delay and the total allocated rate to the links are considered to fairly allocate the rates to the links. The second reason is that the number of nodes in the network is more than the number of the flows. These reasons lead to the fact that the links whose nodes are not the sources of the flows or a gateway, are likely to be activated. Then we have more packets remaining in the flow source nodes and consequently the generated traffic is reduced.
In Table VII, we observe that by increasing the number of nodes, the average delay of one packet in the JGRP algorithm based on all parameters increases. This subject is because of that when the number of the nodes is increased, the number of hops between the flow source nodes and the gateways could be increased.
In Table VIII, it can be observed that increasing the number of the nodes in the networks, the number of the packets received by the gateways is reduced for all the parameters, But, this reduction is more pronounced for W (r) . It can also be observed that increasing the number of nodes, the difference between the number of the received packets by the gateways using W i j and the other parameters increases. This subject is because the number of the flows is less than the number of    In Table IX, we observe that increasing or decreasing the fairness does not have any direct relation with the increase in the number of the nodes. The reason is that the factors that affects the fairness are the allocated rate to the links and the number of hops between the source nodes and the gateways.  B. Multi-Radio Multi-Channel JGRP algorithm (MR-MC JGRP) Now, we introduce MR-MC JGRP as an extension of the JGRP algorithm for multi-radio multi-channel networks. In the special case where the number of radios on each node is equal to the number of frequency channels, the extension is very simple. For this purpose, in the 20 th step of Algorithm 2, partition the set of schedules to some subsets and in each of them, use one of the frequency channels. Then solve problem (13) for each of the frequency channels individually.
For simulation, we assume that each network node has two radios and the number of accessible frequency channels equals to the number of radios. Then, we run the JGRP algorithm based on W (r) i j In Fig. 5, we observe that in the JGRP algorithm based on both parameters W (r) i j and W (r,D) i j using two frequency channels doubles the throughput of the flows comparing with the case of one radio one frequency channel.
In Fig. 6, we observe that in the JGRP algorithm based on both parameters W (r) i j and W (r,D) i j using two frequency channels and two radios per node reduces the average delay and improves the fairness from the delay point of view.
VII. CONCLUSION In this paper, we formulated the problem of network utility maximization for multiple gateways wireless mesh networks by considering joint rate control, traffic splitting, scheduling, routing, link rate allocation and power control assuming SINR interference model. In addition, by considering the complexity of this problem, we proposed the JGRP algorithm as a sub-optimal solution. Then, in order to improve the fairness, we defined W (r) i j , W (D) i j , W (r,D) as new parameters to be used in the JGRP algorithm instead of the differential backlog (W i j ). Simulation results illustrate that using parameters W (r) i j and W (r d ) i j in which the sum of the allocated link rates are considered in their definition, improved the fairness from average delay and throughput points of view. Moreover, by using these parameters, the number of packets received by the gateways is not reduced and the average delay is not increased in comparison to W i j parameter . We also showed that using W (r,D) i j and W (r d ,D) i j in which the sum of the allocated link rates and the delay of packets were considered in their definition, not only improves the fairness, but also improves the communication between mesh nodes and gateways. However, its negative effects increase the average delay and decrease the number of packets received by the gateways in comparison with other parameters. Finally, we extended the JGRP algorithm for multi-radio multi-channel networks in which the number of radios per node is equal to the number of accessible frequency channels. We showed that using two frequency channels and radios when W (r) i j and W (r,D) i j are used doubles the throughput of the flows and reduces the average delay in comparison to the single radio single channel case.


extfieldsofstudy:
Computer Science
Mathematics

text:
Context Vectors are Reflections of Word Vectors in Half the Dimensions

This paper takes a step towards theoretical analysis of the relationship between word embeddings and context embeddings in models such as word2vec. We start from basic probabilistic assumptions on the nature of word vectors, context vectors, and text generation. These assumptions are well supported either empirically or theoretically by the existing literature. Next, we show that under these assumptions the widely-used word-word PMI matrix is approximately a random symmetric Gaussian ensemble. This, in turn, implies that context vectors are reflections of word vectors in approximately half the dimensions. As a direct application of our result, we suggest a theoretically grounded way of tying weights in the SGNS model.

Introduction and Main Result
Today word embeddings play an important role in many natural language processing tasks, from predictive language models and machine translation to image annotation and question answering, where they are usually 'plugged in' to a larger model. An understanding of their properties is of interest as it may allow the development of better performing embeddings and improved interpretability of models using them. This paper takes a step in this direction. Notation: We let R denote the real numbers. Bold-faced lowercase letters (x) denote vectors in Euclidean space, bold-faced uppercase letters (X) denote matrices, plain-faced lowercase letters (x) denote scalars, plain-faced uppercase letters (X) denote scalar random variables, · denotes the Euclidean norm: x := √ x x, 'i.i.d.' stands for 'independent and identically distributed'. We use the sign ∼ to abbreviate the phrase 'distributed as', and the sign ∝ to abbreviate 'proportional to'. Tr(A) is used to denote the trace of a matrix A. M x (t) is the moment-generating function of a random vector x at t: is the Hadamard product (element-wise multiplication). Assuming that words have already been converted into indices, let {1, . . . , n} be a finite vocabulary of words. Following the setup of the widely used word2vec model (Mikolov et al., 2013), we will use two vectors per each word i: • w i when i is a center word, • c i when i is a context word.
We make the following key assumptions in our work. Assumption 1. A priori word vectors w 1 , . . . , w n ∈ R d are i.i.d. draws from isotropic multivariate Gaussian distribution: where I is the d × d identity matrix.
This is motivated by the work of Arora et al. (2016), where the ensemble of word vectors consists of i.i.d draws generated by v = s ·v, withv being from the spherical Gaussian distribution N (0, I), and s being a scalar random variable with bounded expectation and range. In their work, the norm v i of the word vector for a word i is related to its unigram probability p(i), and to allow a sufficient dynamic range for these probabilities they needed the multiplier s. In our work, unigram probabilities are not mapped to vector lengths, and this is why we do not need such multiplier. Direct relationship between word probabilities and word vector norms is also implied by the model of Hashimoto et al. (2016).
Assumption 2. Context vectors c 1 , . . . , c n are related to word vectors according to for some orthogonal matrix Q ∈ R d×d . This is mainly guided by the work of Press and Wolf (2017), who showed that context vectors in the SGNS model of Mikolov et al. (2013) are distributed similarly to word vectors in the sense that pairwise cosine distances between word (input) embeddings strongly correlate with the corresponding pairwise cosine distances between context (output) embeddings (see their Table 4). This is why we choose the transform from word vectors to context vectors to be orthogonal as it preserves inner products and consequently Euclidean norms. Notice, that c i iid ∼ N 0, 1 d I . Assumption 3. Given a word j, probability of any word i being in its context 1 is given by where p i = p(i) is the unigram probability for the word i, which is inverse proportional to its smoothed frequency rank r i , i.e.
This is similar to the log-linear model of Arora et al. (2016), but differs in the following aspects: c i is not assumed to do a random walk over the unit sphere with bounded displacement; we use the factor p i to directly capture word frequencies and do not model them via vector norms. Equation (3) can be interpreted as follows: probability that the word i occurs in the context of the word j is probability that the word i occurs anywhere in a large corpus, corrected for the relationship between words i and j. This approach was already considered by Melamud et al. (2017) but in their work i is the entire left context of the word j, and c i is a vector representation of this entire context. Also, like Arora et al. (2016) but unlike Melamud et al. (2017), we use the model (3) for a theoretical analysis rather than for fitting to data. Smoothing of the unigram probabilities (i.e. raising them to power 1 − α) is motivated by the works of Mikolov et al. (2013), Levy et al. (2015), Pennington et al. (2014), where α = 0.25 is a typical choice. We notice here that α = 0 + gives us Zipf's law (Zipf, 1935), whereas α = 1 gives us uniform distribution of word frequencies which is not valid empirically but on the other hand can be used to explain additivity of word vectors (Gittens, Achlioptas, & Mahoney, 2017). The specific value of α is important for The relationship between word (input) and context (output) vectors was addressed in several previous works. E.g., in recurrent neural network language modeling (RNNLM), tying input and output embeddings is a useful regularization technique introduced earlier (Bengio et al., 2001) and studied in more details recently (Press & Wolf, 2017;Inan et al., 2017). This technique improves language modeling quality (measured as perplexity of a held-out text) while decreasing the total number of trainable parameters almost two-fold since most of the parameters in RNNLM are due to embedding matrices. The direct application of this regularization technique to SGNS worsens the quality of word vectors as was shown empirically by Press and Wolf (2017) and by Gulordava et al. (2018). This worsening was predicted earlier by Goldberg and Levy (2014) using a simple linguistic observation that words usually do not appear in the contexts of themselves. This basically means that Q = I in (2). At the same time, there is empirical evidence that the relationship between input and output embeddings is linear (Mimno & Thompson, 2017;Gulordava et al., 2018). In this paper, we provide a theoretical justification for this and reveal the exact form of the transform Q. Our main contribution is the following Theorem 1. Under Assumptions 1, 2, and 3 above, context vector c i for a word i is the reflection of the word vector w i in approximately half of the dimensions. Figure 1 illustrates this idea for the case d = 2. In general, our word and context vectors live in a d-dimensional vector space over real numbers (R d ). By Theorem 1 we can settle them in a d/2-dimensional vector space over complex numbers (C d/2 ) in such way that the context vector c i ∈ C d/2 for a word i is the complex conjugate of the word vector w i ∈ C d/2 . This is in line with the Theorem 2 of Allen et al. (2018), however they use completely different set of basic assumptions and their primary goal is to encode statistical properties of words directly into word vectors.

Proof of Theorem 1
The proof is divided into three steps: first we show that the partition function in (3) concentrates around 1, and thus ∝ can be replaced by ≈; using this fact we show that Q is (approximately) an involutary matrix, i.e. similar to diag({+1, −1}); and finally we show that the word-word pointwise-mutual information matrix is approximately symmetric Gaussian random matrix with weakly dependent entries. The latter fact immediately implies the statement of the Theorem 1.

Concentration of the partition function
We first need the following auxiliary result. Lemma 1. Let w ∼ N (0, σ 2 I), then ∀t > 0 and any orthogonal Q Proof. Consider the random variable X = w Qw, and let Q = [q ij ]. We have Further, where we dropped the terms containing odd powers of w i , as their expectations are zeros. Hence, From (7) and (8) we have It is easy to see that i q 2 ii + i =j q 2 ij = d (the sum of squared elements of an orthogonal matrix). In this way, Applying Chebyshev inequality to X, and taking into account (6) and (8), we have ∀ > 0 Since Q 2 is orthogonal, its trace does not exceed d, and we obtain (5).
Now we are ready to show that the partition function in (3) concentrates around 1 + 1 2d .
Lemma 2. Let Z j be a partition function in (3) Proof. We will first show that the conditional expectation E[Z j | w j ] depends on w j mainly through its norm w j : where M c i (w j ) is the moment-generating function of c i at w j . In Lemma 1 and Corollary 1.1 it is shown that w j Qw j and w j 2 concentrate well around their means Tr(Q) 1 d and 1 respectively and thus we can approximate The quantity 1 2d is small for d ≥ 50 which is typical for dimensionality of word vectors (Mikolov et al., 2013). Thus, using (14), (15), and Maclaurin expansion for x → e x in the last term of (13), we obtain This approximation is very helpful as the right-hand side does not contain w j and thus it is an approximation for the E[Z j ] as well. Let H n,α be the normalizer in (4), then Now, combining (16), (17), and (15), we get For the variance terms we have and 2. We abuse the notation here and use '∼' to denote asymptotic equivalence, i.e. f (n) ∼ g(n) iff limn→∞ f (n) g(n) = 1.
Conditioned on w j , the random variables {e w j c i } i =j are independent, while e w j c j is constant, and thus Cov e w j c i , e w j c k w j = 0, i = k.
Remark 2.1. Lemma 2 basically says that under the Assumptions 1 and 2, the model (3) self-normalizes, i.e. the normalization term is almost constant and moreover it is almost 1. This result is similar to the result of Andreas and Klein (2015), but differs in that our model (3) is not log-linear as its condition (j) and prediction (i) are both parameterized. The result of Goldberger and Melamud (2018) on self-normalization of the NCE language models is closer to ours but the setup differs in that p i does not appear as a factor in their model. We finally notice that Lemma 2 is an analogue of Lemma 2.1 from Arora et al.
(2016) but adapted to our settings.

Q is an involutary matrix
Lemma 3. Let Q be the matrix mapping word vectors to context vectors as in (2). Then, under Assumptions 1, 2, and 3, Q is approximately an involutary matrix.
Proof. The dimensionality d of word vectors is usually in the range [50, 1000] (Mikolov et al., 2013), and thus we can neglect the term 1 2d in (12) and approximate Z j ≈ 1. This means that the model (3) simplifies to where p(i, j) is the probability that the words i and j co-occur in the same context window. Notice that the left-hand side in (26) is the pointwise mutual information (PMI) between words i and j. From (2) and (26) we have where PMI stands for the PMI-matrix, and W is a n × d matrix in which i-th row is w i . Since p(i, j) = p(j, i), we should have PMI = PMI , which implies where we used the fact that W W ≈ 1 d I. Since Q is assumed to be orthogonal, from (27) In this way, context vectors are word vectors with some of the coordinates being multiplied by −1. The natural question is: how many of the coordinates should be "flipped"?

PMI as a random matrix
Let x i ∈ R l be the vector consisting of the first l coordinates of w i , i.e.
x i = w i,1:l = w i1 , . . . , w il , and let y i ∈ R d−l be the vector consisting of the last d − l coordinates of w i , i.e.
Due to Assumption (1), x i 's are i.i.d. draws from N 0, 1 d I l×l , y i 's are i.i.d. draws from N 0, 1 d I (d−l)×(d−l) , and {x i }, {y i } are jointly independent. Without restricting the generality, assume that the first l diagonal elements in (28) are equal to +1, and the rest d − l elements are equal to −1. Thus random variables with mean 0 and variance 1 d 2 , and by Central Limit Theorem, For i = j, we have where χ 2 l is a chi-square random variable with l degrees of freedom. By combinatorial argument (similar to that of Lemma 1) one can show that covariance between any two distinct and non-symmetric entries of WQ W is zero, and thus Moreover, we can show that PMI ij and PMI pq tend to be independent when d is large enough. For the case i = p, j = q this follows directly from the Assumption (1). Now consider the case i = p, j = q (two distinct elements from the same row). The case i = p, j = q (two distinct elements from the same column) can be analyzed similarly. Let t = t 1 t 2 . Then the moment-generating function (m.g.f.) of PMI ij PMI iq at t is which is the m.g.f. of a twodimensional Gaussian vector with distribution N (0, 1 d I 2×2 ). Hence which implies approximate independence between PMI ij and PMI iq . Hence, from (31) and (32) we conclude that for the PMI matrix • the above-diagonal entries have (approximately) distribution N 0, 1 d , • all entries on and above its diagonal tend to pairwise independence.
This means that the PMI matrix is an approximately symmetric Gaussian random matrix with weakly dependent entries and it is known that the empirical distribution of eigenvalues of such matrix approaches symmetric around 0 distribution as its size n increases (de Monvel et al., 1999). 4 Thus, we should have Recall, that d x i 2 ∼ χ 2 l and d y i 2 ∼ χ 2 d−l . Hence, taking expectation on both sides of (36) we have which concludes the proof of Theorem 1.
Remark 3.1. In terms of the introduced notation (29) and (30), each word's vector w i splits into two subvectors x i and y i , and due to Theorem 1, our model (3) for generating a word i in the context of a word j can be rewritten as Interestingly, embeddings of the first type (x i and x j ) are responsible for pulling the word i into the context of the word j, while embeddings of the second type (y i and y j ) are responsible for pushing the word i away from the context of the word j. We hypothesize that the x-embeddings are more related to semantics, whereas the y-embeddings are more related to syntax. We defer testing of this hypothesis to our future work.  To verify that the real-world PMI matrices have indeed symmetric (around 0) distribution of their eigenvalues, we consider two widely-used datasets, text8 and enwik9, 5 from which we extract PMI matrices using the hyperwords tool of Levy et al. (2015). We use the default settings for all hyperparameters, except word frequency threshold and context window size. We were ignoring words that appeared less than 100 times and 150 times in text8 and enwik9 correspondingly, resulting in vocabularies of 11,815 and 29,145 correspondingly. We additionally experiment with context window 5, which by default is set to 2, and which we believe could affect the results. The eigenvalues of the PMI matrices are then calculated using the TensorFlow library (Abadi et al., 2016), and the above-mentioned threshold of 150 for enwik9 was chosen to fit the resulting PMI matrix into the GPU memory (12GB, NVIDIA Titan X Maxwell). The histograms of eigenvalues are provided in Figure 2. As we can see, the distributions are not perfectly symmetric with a little right skewness, but in general they seem to be symmetric. Notice, that this is in stark contrast with the equation (2.5) from Arora et al. (2016) Table 2: Evaluation of word embeddings in the analogy tasks (Google and MSR) and in the similarity tasks (the rest). For word similarities evaluation metric is the Spearman's correlation with the human ratings, while for word analogies it is the percentage of correct answers. Model sizes are in number of trainable parameters. (Levy & Goldberg, 2014b). Since our Assumptions lead to the same conclusion up to a constant shift (26), we believe that Theorem 1 can be directly applied to tie word (w i ) and context (c i ) embeddings in the SGNS model. For this purpose we form a vector q ∈ R d of d i.i.d. draws from the Rademacher distribution 6 and then put

Empirical verification
for all words i in the vocabulary. This is equivalent to (2) when the matrix Q has the special diagonal form (28). Such modification of the SGNS is refered to as 'SGNS + WT'. The word embeddings w i are initialized randomly, and then trained on text8 and enwik9 using the reference word2vec implementation from the TensorFlow codebase 7 with all hyperparameters set to their default values except that we choose the learning rate to decay 20% faster in the weight-tied model. This additional tuning of the learning rate decay is not surprising: the model with tied embeddings has two times less parameters compared to the model with untied weights, and this leads to a significant change of the optimization landscape, which in turn results in the need to tune the most sensitive hyperparameterthe learning rate (or its decay schedule). As is standard nowadays the trained embeddings are evaluated on several word similarity and word analogy tasks. We used the hyperwords tool of Goldberg and Levy (2014) and we refer the reader to their paper for the methodology of evaluation. We only mention here few key points: • Our goal is not to beat state of the art, but to empirically validate the statement of Theorem 1. This is why we were evaluating only word (input) embeddings for both SGNS and SGNS+WT. I.e., we were not adding context vectors to word vectors in the similarity tasks, as it is usually done nowadays.
• Word similarity datasets contain word pairs together with human-assigned similarity scores. The word vectors are evaluated by ranking the pairs according to their cosine similarities and measuring the correlation (Spearman's ρ) with the human ratings.
6. Rademacher distribution is a discrete probability distribution where a random variate X has a 50% chance of being +1 and a 50% chance of being −1. 7. https://github.com/tensorflow/models/blob/master/tutorials/embedding/word2vec.py • For answering analogy questions (a is to b as c is to ?) we use the 3CosMul of Levy and Goldberg (2014a) and the evaluation metric for the analogy questions is the percentage of correct answers.
The results of evaluation are provided in Table 2. As we can see, SGNS + WT produces embeddings comparable in quality with those produced by the baseline SGNS model despite having 50% fewer parameters. This also empirically validates the statement of our Theorem 1. We notice that similar results can be obtained by letting the linear transform Q be a trainable matrix as shown by Gulordava et al. (2018). The main difference of our approach is that we know exactly the form of Q, and thus we do not need to learn it.

Conclusion
There is a remarkable relationship between human language and other branches of science, and we can get interesting and practical results by studying deeper such relationships. For example, the modern theory of random matrices is replete with theoretical results that can be immediately applied to models of natural language once such models are cast into the appropriate probabilistic setting, as is done in this paper.