Codes in the q-ary Lee Hypercube

Abstract: Let Fq={0,1,...,q−1}be an alphabet of size q, so that Fn

qis the q-ary hypercube of dimension n.

Let x= (x1,...,xn)and y= (y1, . . . , yn)be two elements in Fn

q. The Lee distance between xand yis equal to

i=1 min(|xi−yi|, q − |xi−yi|). Let C⊆Fn

q;Cis called a code. Given an integer radius r>1, we consider

three types of codes with respect to the Lee distance: an r-dominating code C(also called an r-covering code) is

such that any element x∈Fn

qis within distance rfrom at least one codeword c∈C(then c r-dominates x); an r-

locating-dominating code Cis (i) r-dominating and (ii) such that any two vertices x, y in Fn

q\Care r-dominated

by distinct sets of codewords; an r-identifying code Cis (i) r-dominating and (ii) such that any two vertices x, y

in Fn

qare r-dominated by distinct sets of codewords. We look for minimum such codes. For the above three types

of codes, we give tables of upper bounds on their smallest cardinalities, for alphabet size q∈ {4,5,6}, dimension

nup to 7, and radius rup to 5. These bounds are obtained mainly by using different heuristics (greedy, descent,

noising). We conclude with conjectures and open problems.

Key-Words: Dominating codes, Covering codes, Locating-dominating codes, Identifying codes, Hamming

distance, Lee distance, q-ary hypercube, Graph theory, Combinatorial optimization, Heuristics.

Received: May 17, 2021. Revised: February 16, 2022. Accepted: March 15, 2022. Published: April 13, 2022.

1Introduction

We consider the q-ary hypercube of dimension n,

endowed with the Lee distance and, using different

heuristics, we search for subsets of vertices, with the

smallest possible sizes, satisfying different properties

that we are now going to deﬁne in the more gene-

ral setting of a ﬁnite, undirected, connected graph

G= (V, E).

1.1 General notation and deﬁnitions

For a given integer radius r>1and a given distance

d, the closed r-neighbourhood of a vertex v∈Vis

the set Nr[v] = {u∈V: 0 6d(u, v)6r}.

Acode is simply a subset of V, whose elements

are called codewords.

Two vertices within distance rfrom each other

are said to r-dominate each other. A vertex is r-

dominated by a code Cif it is r-dominated by at least

one codeword. Two vertices xand yare r-separated

by a vertex zif we have z∈Nr[x]and z /∈Nr[y]

or if we have z∈Nr[y]and z /∈Nr[x](note that

zcan be equal to xor y). Two vertices xand yare

r-separated by a code Cif they are r-separated by at

least one codeword.

Deﬁnition 1. An r-dominating code (r-D code for

short) is a code C⊆Vsuch that any vertex has at

least one codeword at distance at most r:

∀v∈V, ∃c∈Csuch that d(v, c)6r.

Equivalently, every vertex is r-dominated by C, or

∪c∈CNr[c]=V, which implies:

c∈C

|Nr[c]|>|V|.(1)

Dominating codes constitute a wide topic in graph

theory, explored mostly in the case r= 1. See, e.g.,

[16], [17].

Deﬁnition 2. An r-locating-dominating code (r-LD

code for short) is an r-D code C⊆Vwhich more-

over satisﬁes:

∀v1∈V\C, ∀v2∈V\C, v16=v2:

Nr[v1]∩C6=Nr[v2]∩C.

Equivalently, a code Cis an r-LD code if Cis

r-dominating and r-separates all the pairs of non-

codewords. An r-LD code always exists in G(e.g.,

C=V), and we can see that the previous deﬁni-

tion states that every non-codeword is characterized

(or located) by the set of codewords r-dominating it.

Deﬁnition 3. An r-identifying code (r-Id code for

short) is an r-D code C⊆Vwhich moreover satis-

ﬁes:

∀v1∈V, ∀v2∈V, v16=v2:

Nr[v1]∩C6=Nr[v2]∩C.

Equivalently, a code Cis an r-Id code if Cis r-

dominating and r-separates all the pairs of vertices.

Here, every vertex, whether it is a codeword or not,

IRENE CHARON1, OLIVIER HUDRY1, ANTOINE LOBSTEIN2

1Institut polytechnique de Paris, T´el´ecom Paris, 91123 Palaiseau

2Laboratoire Interdisciplinaire des Sciences du Num´erique

(UMR 9015), CNRS, Universit´e Paris-Saclay, 91400 Orsay

FRANCE

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.24

Irene Charon, Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

173

Volume 21, 2022

is characterized (or identiﬁed) by the codewords r-

dominating it. It is easy to see that an r-Id code exists

in Gif and only if we have:

∀v1∈V, ∀v2∈V, v16=v2:Nr[v1]6=Nr[v2].

Locating-dominating codes were introduced in

1983 [30], but for more easily accessible sources,

see [26] or [8]. The term “identifying code” is used

in [20], which certainly marks the starting point for

the blossoming of works on this topic, but the con-

cept is already contained in [27]. For both locating-

dominating and identifying codes, see the ongoing

bibliography at [23].

We usually search for the smallest possible codes

and introduce the notation γr(G), LDr(G), and

Idr(G)for the smallest sizes of an r-D, an r-LD, and

an r-Id code (when there is one), respectively. Any

code with this size is called optimal with respect to

the desired property. Obviously, every r-Id code is

r-LD and every r-LD code is an r-D code; hence:

γr(G)6LDr(G)6Idr(G).(2)

1.2 The q-ary Lee hypercube of dimension n

We now restrict our attention to a speciﬁc class of

graphs.

Let qbe an integer, q>2. Let Fq={0,...,q−1}

be an alphabet of size q. All calculations will be

modulo q. The q-ary hypercube of dimension n, de-

noted Fn

q, is the Cartesian product of Fq, carried out

ntimes: its elements are the qnvertices or vectors

v= (v1, v2,...,vn), where vi∈Fqfor 16i6n.

One can deﬁne two distances on Fn

- the Hamming distance between

u= (u1, u2,...,un)and v= (v1, v2,...,vn)in

qis given by:

dH(u, v) = |{i∈ {1,2,...,n}:ui6=vi}|

or equivalently dH(u, v) = Pn

i=1 min{1,|ui−vi|};

- the Lee distance between u= (u1, u2,...,un)

and v= (v1, v2,...,vn)in Fn

qis given by:

dL(u, v) =

i=1

min{|ui−vi|, q − |ui−vi|}.

Note that both distances coincide for q∈ {2,3}.

If we draw edges between any two vectors which are

at distance one, we obtain, for given qand n, two

graphs, according to the distance we consider. We

shall use the obvious notation Hn

qand Ln

q; by our pre-

vious observation, we have Hn

2=Ln

2and Hn

3=Ln

Example. For r= 2 in L2

-C={(0,0); (2,1)}is a 2-D code (for instance,

(3, 2) is 2-dominated by (2, 1)) but not a 2-LD code:

for instance, (1, 1) and (3, 0) are not 2-separated by C

since they are both 2-dominated by (0, 0) and (2,1),

nor a 2-Id code; hence γ2(L2

4)62;

-C={(0,1); (1,2); (2,0); (2,1); (3,1)}is a 2-

LD code but not a 2-Id code: for instance (2, 1) and

(1, 1) are both 2-dominated by the ﬁve codewords and

thus are not 2-separated by C; hence LD2(L2

4)65;

-C={(0,0); (0,1); (0,2); (1,0); (2,0); (3,3)}

is a 2-Id code; hence Id2(L2

4)66.

These three codes are optimal, see Table 2.

The study of r-dominating codes in Hn

q(these

codes are also called r-covering codes or simply r-

coverings in this case) is of importance for coding and

information theory, see [7] and its large bibliography,

updated at [22]; the case q= 3 can lead to applica-

tions for football bets, see, e.g., [15]. Also in Hn

q, re-

sults on “good” locating-dominating and identifying

codes can be found in, among many others, [18], [3],

[12], [10]. Much less is known when considering Ln

for q>4, see [1], [20], [21], [9], [28], [11].

From now on, we consider only the Lee distance,

that is, the graph Ln

qwith q>4. Due to the regularity

of the graph, the size of the r-neighbourhood is the

same for all vertices; we denote by Vn,r,q the size of

Nr[v]in Ln

q, where vis any vertex.

Consider v= (v1, v2,...,vn)∈Ln

q. When qis

even, the vertex (v1+q

2, v2+q

2,. . . , vn+q

2)is at Lee

distance δe=n×q

2from v, and all other vertices are

at distance at most δe−1from v. When qis odd, the

2nvertices (v1+q±1

2, v2+q±1

2,. . . , vn+q±1

2)are

at distance δo=n×q−1

2from v, and the remaining

vertices are at distance at most δo−1.

As a ﬁrst consequence, if n,qand rare such that

r>δefor even q, or r>δofor odd q, then all

vertices are within distance rfrom each other in Ln

Then obviously:

Remark 1. If n,qand rare such that r>n×q

2for

even q, or r>n×q−1

2for odd q, then γr(Ln

q) = 1,

LDr(Ln

q) = qn−1and Ln

qadmits no r-identifying

code. Otherwise, it is easy to see that Ln

qadmits r-

identifying codes.

Assume now that qis even and n,qand rare

such that r=n×q

2−1. Then all vectors are

within distance rfrom each other, except for the pairs

(v1, v2,...,vn)and (v1+q

2, v2+q

2, . . . , vn+q

2),

which are at distance r+ 1 from one another. In

other words, the r-th power (or r-transitive-closure)

of Ln

q, denoted (Ln

q)r, is the complete graph deprived

of a perfect matching. Then it is not very difﬁcult

to see that γ1((Ln

q)r) = 2, LD1((Ln

q)r) = qn

2and

Id1((Ln

q)r) = qn−1, which in turns implies the fol-

lowing:

Remark 2. If n,qand rare such that qis even and

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.24

Irene Charon, Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

174

Volume 21, 2022

r=n×q

2−1, then γr(Ln

q) = 2, LDr(Ln

q) = qn

2and

Idr(Ln

q) = qn−1.

Remark 3. Using (1) and (2) and Remarks 1 and 2,

one obtains the following bounds:

Vn,r,q

6γr(Ln

q)6LDr(Ln

q)6Idr(Ln

q)6qn−1.

(3)

Our goal here is to use different heuristics, already

used elsewhere for other optimization problems, in

order to construct r-D, r-LD and r-Id codes as small

as possible in Ln

q. As a result, for the above three

types of codes, Tables 2, 3 and 4 will provide upper

bounds on their smallest cardinalities, for alphabet

size q∈ {4,5,6}, dimension nup to 7, and radius r

up to 5. Deﬁne the density of a code Cas the ratio

|C|/qnbetween the cardinality of Cand the number

of vertices; Tables 5, 6 and 7 will provide the den-

sities of the computed codes, also for alphabet size

q∈ {4,5,6}, dimension nup to 7, and radius rup

to 5.

2 The methods for obtaining r-D,

r-LD or r-Id codes

2.1 The combinatorial optimization

problems

The combinatorial optimization problems that we

want to solve are the following: given n,rand q,

minimize |C|where Cis an r-D or an r-LD or an

r-Id code in Ln

q. We call these problems (n, r, q)-

DP, (n, r, q)-LDP and (n, r, q)-IdP respectively. In

the general case of any graph, the decision problems

associated with these problems are NP-complete

(see [6], [14], [2] or [24] for more references).

In order to solve (n, r, q)-DP, (n, r, q)-LDP and

(n, r, q)-IdP, we solve subproblems that we deﬁne

now. For any subset Cof V, let α(C)be the number

of vertices which are not r-dominated by C,ζ(C)be

the number of pairs of vertices belonging to V\C

which are not r-separated by C, and ξ(C)be the

number of pairs of vertices belonging to Vwhich

are not r-separated by C. We set: fD(C) = α(C),

fLD(C) = α(C)+ζ(C)and fId(C) = α(C)+ξ(C).

Observe that:

-Cis an r-D code if and only if fD(C)is equal to 0;

-Cis an r-LD code if and only if fLD(C)is equal

to 0;

-Cis an r-Id code if and only if fId(C)is equal to 0.

The subproblems associated with (n, r, q)-DP,

(n, r, q)-LDP and (n, r, q)-IdP consist in generating

codes Cand in trying to minimize fD(C),fLD(C)

or fId(C)respectively. If we ﬁnd a code C0with

fD(C0) = 0,fLD(C0) = 0 or fId(C0) = 0, then C0

is an r-D or an r-LD or an r-Id code respectively and

we may try again with a smaller code.

In order to minimize fD,fLD or fId, we apply

a greedy algorithm, some metaheuristics (namely, a

descent method and a noising method; for references

on metaheuristics, see for instance [29] or [25] among

many possibilities) and, for small instances, an exact

enumerative method.

2.2 Greedy method

The greedy method performed here consists in adding

new vertices successively to the code Cin construc-

tion until Cbecomes an r-D or an r-LD or an r-Id

code according to the studied problem. More pre-

cisely, at each step of the method, we choose to add

one vertex; the chosen vertex is such that the decrease

of fDfor (n, r, q)-DP, of fLD for (n, r, q)-LDP, or

of fId for (n, r, q)-IdP is as large as possible. The

aim of such additions of extra vertices is to obtain a

value equal to 0 for fD,fLD or fId, in which case

the current code is an r-D or an r-LD or an r-Id code

respectively.

We may start from the empty set for C. Other

possibilities consist in starting from a random subset

of Vor, for (n, r, q)-LDP and (n, r, q)-IdP, from an r-

dominating set of Ln

q(for instance, from the solution

obtained for (n, r, q)-DP); this allows to save time but

may build less good r-LD or r-Id codes (similarly, we

may start from an r-LD code for (n, r, q)-IdP).

The greedy method can be improved thanks to the

following two remarks.

1. For (n, r, q)-LDP or (n, r, q)-IdP, when a vertex v

is added to C, the complexity for evaluating the varia-

tions of ζ(C)or ξ(C)is about Vn,r,q ×(qn− Vn,r,q).

Another way to compute this variation consists in

scanning a list containing the pairs of vertices which

are not r-separated and, for each such pair {a, b}of

this list, in checking whether vis a r-neighbour of a

but not of bor of bbut not of a. The complexity is

then about the number of pairs of vertices which are

not r-separated. So, when this number becomes less

than Vn,r,q ×(qn− Vn,r,q), we build an array contain-

ing the pairs of vertices which are not r-separated.

Of course, we update this array when a vertex is

added to the current code. This speeds up the greedy

method, and even more and more as the method runs

since the number of pairs of vertices which are not

r-separated decreases (anyway, we cannot apply this

trick from the beginning, because it usually requires

a too large memory-space).

2. When we look for a vertex which maximizes the

decrease of the objective function, we keep all the

vertices yielding this maximum decrease in a list L.

Let µdenote this maximum decrease. Then we go

through the list L. For each vertex vof L, if adding

vto the current code still allows to decrease the

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.24

Irene Charon, Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

175

Volume 21, 2022

objective function by µwith respect to the current

code (this is necessarily the case for the ﬁrst element

of L), then vis added to the current code before

considering the next element of L. This avoids the

computation of the maximal decrease at each step,

which is usually long; thus this considerably speeds

up the greedy algorithm, specially at the end of its

run.

2.3 Descent method (iterative improvement

method)

In order to improve the r-D or r-LD or r-Id code

provided by the greedy algorithm (or by any other

constructive method), we design a descent method

(also called iterative improvement method, or still hill

climbing method for a maximization problem).

We start from an r-D or an r-LD or an r-Id

code C. We wish to decrease the cardinality of C

by removing vertices of C, one by one. For this, we

ﬁrst remove a vertex randomly chosen in C. We up-

date the objective function fD,fLD or fId according

to the problem. Then we try to restore an r-D or an

r-LD or an r-Id code without changing the current

number of codewords. If we succeed, we apply the

same process (i.e., removing a vertex) to the new r-D

or r-LD or r-Id code.

In order to recover an r-D or an r-LD or an r-

Id code, we perform elementary transformations (or

local transformations) with respect to the current

code C. An elementary transformation consists here

in removing a vertex ubelonging to Cand, simul-

taneously, in adding a vertex vwhich does not be-

long to C. The vertices uand vare randomly chosen.

We say that the transformation is good if the objec-

tive function fD,fLD or fId does not increase (the

variation of the objective function can be equal to 0);

otherwise, we say that it is bad.

Observe a main difference with respect to a usual

design of a descent method: in order to ensure the

convergence of the process, a good transformation

is quite often required to involve a strict decrease of

the objective function (this variation cannot be equal

to 0). It appears from our experiments that allowing

transformations which do not change the value taken

by the objective function may be preferable. Indeed,

when we cannot improve the current conﬁguration

with only one transformation, then it is necessary to

perform several transformations if we want to escape

a local minimum in order to reach a better conﬁgura-

tion. The negative counterpart of this is that the pro-

cess can cycle without improving the current conﬁgu-

ration; it is then necessary to upper bound the number

of iterations performed by the method.

So, in the descent method, we try a given number

of elementary transformations, which is a parameter

of the method (of course directly related to the CPU

time that we want to spend to ﬁnd an r-D or an r-LD

or an r-Id code). Only the good transformations are

actually performed: the objective function can never

increase. If the objective function fD,fLD or fId

according to the problem becomes equal to 0, then

the current code is again an r-D or an r-LD or an

r-Id code respectively; in this case, we remove a ran-

domly chosen vertex from the new r-D code or r-LD

code or r-Id code and we start a new descent. On

the contrary, if we perform the total number of trials

without obtaining a new r-D or r-LD or r-Id code,

we stop the whole process.

2.4 Noising method

This metaheuristic (see [5] for a review of its prin-

ciples and of applications) can be seen as a genera-

lization of the simulated annealing method (as well

as other metaheuristics; see [4]). The version of the

noising method applied in our experiments is very

close to the usual scheme of simulated annealing,

from which we draw the terminology of temperature.

In particular, a bad transformation may be accepted,

unlike in the descent method.

Four parameters are involved: the initial tempe-

rature T0, the number of temperature changes, the

number of elementary transformations tried for each

value of the temperature and a ﬁxed real number λ

with 0< λ < 1, meant to control the geometric

decrease of the temperature T: when Tchanges, T

becomes λT . The values of these parameters depend

on the considered problem. For example, to ﬁnd a

2-D code of size 30 for (5, 2, 4)-DP, we applied the

noising method with an initial temperature equal to

50, 100 temperature changes, 107elementary trans-

formations and λ= 0.95 (the CPU time was equal to

268 014 seconds, i.e. a little more than three days).

Consider an elementary transformation involving

a variation ∆of the objective function fD,fLD or

fId (with ∆>0when we deal with a bad elemen-

tary transformation). For each tried transformation,

we draw a real number pbetween 0 and 1 with a uni-

form distribution. The transformation is accepted if

we have ∆6pT (hence, the main difference here

with simulated annealing is that, in simulated annea-

ling, the acceptance criterion would be ∆6−Tln p;

the results obtained by a classic simulated annealing

are about the same as the ones reported below; the

noising method applied here avoids the computations

of logarithms). When Tbecomes less than 1, the

behaviour of the noising method at the end of its run

is qualitatively the same as the one of a descent.

2.5 Removing the unnecessary vertices

At the end of any of the previous methods, we con-

sider each vertex vof the computed r-D or r-LD

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.24

Irene Charon, Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

176

Volume 21, 2022

or r-Id code according to the problem. If removing

vleaves anyway a suitable code, we deﬁnitively re-

move v.

According to our experiments, this simple prin-

ciple may improve the current conﬁguration quite

often, especially when many elementary tranforma-

tions were performed with a variation of the objec-

tive function equal to 0 (see above). Indeed, these

zero-variation transformations then achieve a “mi-

xing” that increases diversity by changing the code-

words inside the current conﬁguration, which can be

proﬁtable to move away from a local minimum.

2.6 Exact method

For small values of nand q, we also looked for mini-

mum r-D or r-LD or r-Id codes by using an exact

method. Such a method is based on an exhaustive

enumeration of the codes. We start with a code Cof

low cardinality k. While Cis not an r-D or an r-LD

or an r-Id code according to the considered problem,

we generate the next (according to the lexicographic

order) code of cardinality k. If all the codes of size k

have been tried in vain, we increase kand we repeat

the same process.

Another way to apply this enumerative method is

to start with an r-D or an r-LD or an r-Id code of

size kand to decrease k: while we ﬁnd a suitable code

with a given cardinality k, we decrease k; when we

do not ﬁnd any longer a suitable code of cardinality k,

we conclude that k+ 1 is the minimum size. This

is particularly useful for checking the optimality of a

given r-D or r-LD or r-Id code of cardinality k, when

kis not too large: we try all the (k−1)-sized codes to

check that none of them is appropriate. In the tables

below, this is indicated by the key “*b”; more gene-

rally, a star “*” denotes the minimum cardinality of

an r-D or an r-LD or an r-Id code.

3 Tables of results

Tables of bounds for identifying codes are given in

[11] for 46q66,26n67and 16r65.

This is why we chose the same values for the para-

meters q, n, r in our study, even if we considered

codes other than identifying, namely dominating and

locating-dominating.

The lower bounds ⌈qn

Vn,r,q ⌉given in Table 1 are

weak, specially for locating-dominating codes and

identifying codes, but probably also for dominating

codes. Indeed, even for small values of rand n, we

may observe that the lower bounds and the minimum

values are not equal (for instance, for n= 3,r= 1,

q= 4: 10 versus 12, see Table 2; for n= 2,r= 2,

q= 5: 2 versus 3, see Table 3; for n= 2,r= 2,

q= 6: 3 versus 4, see Table 4). For identifying

codes, better lower bounds exist for q= 4 (see [21]

for r= 1 and [11] for r > 1), and for q > 4,qeven

and r= 1 [20]. They are given in Tables 2, 3 and 4,

together with the upper bounds (all constructive).

The results reported in these tables were obtained

with different computers and by the application of

different methods among the ones depicted above.

The aim of this paper is not to study and to compare

the efﬁciency of these methods by putting them in

competition, but on the contrary to make them colla-

borate in order to compute the best possible codes.

For these reasons, we do not report the CPU times

required to compute the r-D, r-LD or r-Id codes.

These CPU times can be very large, up to several

weeks: for instance, we needed 699 809 seconds (i.e.

a little more than 8 days) to improve by 1 a 4-D code

with 119 vertices for n=q= 6 by the descent

method, and then 1 448 007 extra seconds (i.e. about

16.8 days) in order to obtain a code with 117 vertices

from the code with 118 vertices.

The r-D, r-LD or r-Id codes that we computed

and of which the sizes are reported in Tables 2, 3

and 4 can be found at the following address:

https://perso.telecom-

paristech.fr/hudry/LeeHypercubesCodes.html

The codewords available in the ﬁles displayed

at this address are encoded as integers thanks to

the function ϕdeﬁned as follows. Each vertex

uof Ln

q, i.e. a vector u= (u1, u2,...,un),

can be associated with an integer ϕ(u)deﬁned by

ϕ(u) = Pn

i=1 uiqi−1. For instance, for q= 4, we get

ϕ(1,2,0,2) = 1×40+2×41+0×42+2×43= 137.

Obviously, ϕis a one-to-one function between the

vertices of Ln

qand the integer values between 0 and

qn−1. This representation saves space.

If we succeed in improving the values reported in

Tables 2, 3 and 4 later on, we will update these ﬁles.

Keys to Tables 2, 3 and 4

Lower bounds are given for r-identifying codes, for

q= 4, and q= 6 with r= 1. They are in italics.

Also for identifying codes, our new upper bounds are

followed by the previously best known upper bounds

between brackets. Keys are mainly for identifying

codes, relying on [20], [21], and [11]:

a= because LDr(G)6Idr(G)(but none of our

heuristics could ﬁnd the LD-code; this happens only

once, for n= 7,r= 1,q= 6)

∗b= optimal: exhaustive search

∗c= optimal: r=n×q

2−1for qeven (for r-D, r-LD

and r-Id-codes, see Remark 2)

∗d= optimal: r>n×q

2,qeven, and r>n×q−1

qodd (for r-D or r-LD-codes, see Remark 1)

∗e= optimal: the upper bound coincides with the

lower bound given in Table 1

∗f= optimal, other cases

g,hand irefer to articles: g= [20], h= [21], i= [11].

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.24

Irene Charon, Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

177

Volume 21, 2022

4 Analysis of the results, conjectures

and open problems

Tables 2, 3 and 4 provide upper bounds for the mini-

mum sizes of r-D codes, r-LD codes and r-Id codes

in the graphs Ln

qfor 46q66,26n67and

16r65(remember that, for q= 2 and q= 3, Lee

distance and Hamming distance are the same, yiel-

ding the equality Ln

q=Hn

q; so we do not give results

for q∈ {2,3}: they can be found in the references

given above, in Section 1).

Some of these values are optimal: they are indi-

cated by a star in the tables. Is it possible to improve

some of the others? This is a challenge...

From the values displayed in Tables 2, 3 and 4, we

may observe interesting phenomena.

•Almost all the known upper bounds are signiﬁ-

cantly improved.

•For any ﬁxed parameters nand q,γr(Ln

q)is

non-increasing when rincreases; this is quite

obvious, since the size Vn,r,q of the closed r-

neighbourhood of any vertex increases with r:

any vertex r-dominates more and more vertices

and any r-dominating code is also an (r+ 1)-

dominating code.

•This is not the case for LDr(Ln

q)and Idr(Ln

q).

Indeed, when rincreases, the number of vertices

r-dominated by a given codeword increases too,

exactly as for γr, but not necessarily the number

of r-separated vertices. More precisely, for any

ﬁxed parameters nand q, the computed values

for LDr(Ln

q)and Idr(Ln

q)ﬁrst non-incresase and

then non-decrease. This suggests the following

conjecture:

Conjecture 1 and open problem 1. [Unimodality

with respect to r] Let nand qbe given. When rin-

creases (starting from r= 1), the function LDr(Ln

q),

after a possible non-increase, non-decreases until it

reaches the value qn−1; the function Idr(Ln

q), after a

possible non-increase, non-decreases until Ln

qadmits

no r-identifying code.

If so, what are the values of rin function of nand

qfor which LDr(Ln

q)and Idr(Ln

q)reach their mini-

mum values?

•If now whe ﬁx rand q, we observe that

γr(Ln

q)non-decreases when nincreases

(note that γrmay be steady: for instance

γ3(L2

4) = γ3(L3

4) = 2). This behaviour is sys-

tematic, as shown by the following proposition:

Proposition 1. Let rand qbe given. When n

decreases until n= 2, the function γr(Ln

q)is non-

increasing.

Proof. Let Cn+1 be an optimal r-dominating

code in Ln+1

q, and Cnbe the code deﬁned in

qby Cn={(c1,...,ci−1, ci+1 ,...,cn+1) :

∃j∈ {0,1,...,q−1}such that

(c1, c2,...,ci−1, j, ci+1 ,...,cn+1)∈Cn+1},

that is, we simply delete the i-th coordinate in

Cn+1, for one i∈ {1,2,...,n + 1}. In the follo-

wing, for simplicity, we take i=n+ 1. Consider

any vertex (v1,...,vn)∈Ln

q. For every vertex

v= (v1,...,vn, vn+1)∈Ln+1

q, there is a codeword

c= (c1,...,cn, cn+1)∈Cn+1 with dL(v, c)6r.

Then dL((v1,...,vn),(c1,...,cn)) 6r, which

proves that Cnis r-dominating in Ln

q. Hence

γr(Ln

q)6|Cn|6|Cn+1|=γr(Ln+1

q).

•The behaviour of LDr(Ln

q)is not the same as

the one of γr(Ln

q)and seems more erratic when

nincreases with ﬁxed rand q: for r= 5 and

q= 4, LD5(Ln

4)ﬁrst increases (LD5(L2

4) = 15,

LD5(L3

4) = 32) then decreases and, if we

consider the computed values, ﬁnally increases

again (21 for n= 4, 16 for n= 5, 25 for

n= 6, 41 for n= 7). Such a behaviour

may be rather surprising since the number of ver-

tices to be r-dominated and the number of pairs

of vertices to be r-separated increase dramati-

cally: thus LDr(Ln

q)may be expected to increase

when nincreases. Similarly, Idr(Ln

q)does not

inscrease with every value of n. But in fact, these

phenomena seem to appear only when nis small

enough with respect to r. Hence the following

conjecture and open problem:

Conjecture 2 and open problem 2. [Increase of LDr

and Idrwith respect to nfor nlarge enough] Let r

and qbe given. There exist integers NLD(r, q)and

NId(r, q)such that, respectively for n>NLD(r, q)

and n>NId(r, q), the values of LDr(Ln

q)and of

Idr(Ln

q)increase when nincreases.

If so, what are the values of NLD(r, q)and

NId(r, q)in function of rand q?

•When considering the Hamming distance, we

have the following inequality ([13]; see also [3]):

for p > r >1, Idr(Hn+p

2)62pIdr(Hn

2). On

the other hand, we have the following theorem

for γr, thanks to the so-called direct sum cons-

truction:

Theorem 1. Let rand qbe given. Then,

for any dimension n, we have the inequality

γr(Ln+1

q)6q×γr(Ln

q).

Proof. Let Cnbe a minimum r-D code in

q:|Cn|=γr(Ln

q). For each codeword

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.24

Irene Charon, Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

178

Volume 21, 2022

u= (u1, u2, ..., un)of Cn, consider the qvertices

(u1, u2, ..., un, i)of Ln+1

qwith i∈ {0,1, ..., q −1}.

Let Cn+1 be the code of Ln+1

qthus obtained.

Let v= (v1, ..., vn, vn+1)be any vertex of

Ln+1

q. Since Cnis an r-D code of Ln

q, there

exists a codeword (u1, u2, ..., un)∈Cnwith

dL((v1, ..., vn),(u1, ..., un)) 6r. Hence the inequa-

lity dL((v1, ..., vn, vn+1),(u1, ..., un, vn+1)) 6r.

Since (u1, ..., un, vn+1)belongs to Cn+1,Cn+1 is an

r-D code of Ln+1

qwith q×γr(Ln

q)codewords. 

Note that, if the computed values for γ1(L6

and γ1(L7

4), i.e. 385 and 1540, or for γ1(L4

6),γ1(L5

6),

γ1(L6

6)and γ1(L7

6), i.e. respectively 144, 864, 5 184

and 31 104, are the minimum ones, then the inequa-

lity γ1(Ln+1

q)6q×γ1(Ln

q)of the theorem would be

tight for these values.

These observations lead us to the following

conjecture (which would extend the inequality

Idr(Hn+p

2)62pIdr(Hn

2)to any value of p, in

particular for r=p= 1):

Conjecture 3. [Bounded increase of LDrand

Idrwhen the dimension nincreases by 1].

Let rand qbe given. For any dimen-

sion n, we have LDr(Ln+1

q)6q×LDr(Ln

q)and

Idr(Ln+1

q)6q×Idr(Ln

q).

•Tables 5, 6 and 7 provide the densities of the

computed codes, i.e. the ratios between the

computed cardinalities and the number of ver-

tices. For γr, the computed densities are non-

increasing both with respect to n(as announ-

ced by Theorem 1) and r(see above for the

decrease with respect to r) but not with res-

pect to q(compare for instance the – exact –

densities for γ1(L2

5)and γ1(L2

6)). For LDr

and Idr, the computed densities are decreasing

with respect to n(see Conjecture 3) but not

with respect to ror to q(compare for instance

the values for LD2(L2

4)and LD3(L2

4), the va-

lues for LD1(L3

4)and LD1(L3

5), the values for

Id2(L2

4)and Id3(L2

4), the values for Id1(L5

4)and

Id1(L5

5)).

Conjecture 4. [Non-increase of the densities with

respect to n]. Let rand qbe given. Conjecture 3

is equivalent to the non-increase of the densities for

LDr(Ln

q)and Idr(Ln

q); furthermore, we conjecture

that the densities for γr(Ln

q), LDr(Ln

q)and Idr(Ln

tend towards 0 when nincreases.

•The compared costs of r-domination, r-location-

domination and r-identiﬁcation, i.e. the diffe-

rences between optimal cardinalities, are studied

for general graphs in [19]. While the gaps bet-

ween optimal cardinalities can be very large for

general graphs, the differences between the com-

puted values for Ln

qare, for a large majority of

cases, rather small with respect to the number qn

of vertices, as shown by Tables 5, 6 and 7. In

particular, the computed values of LDr(Ln

q)and

Idr(Ln

q)become very close when nincreases for

given rand q:r-separating all the pairs of ver-

tices does not cost much more than r-separating

only the pairs of non-codewords. Sometimes, the

computed values of LDr(Ln

q)and Idr(Ln

q)are

the same (see Tables 2, 3 and 4). Hence an open

problem:

Open problem 3. [Equality between LDr(Ln

q)and

Idr(Ln

q)]. Can we characterize the values of n,rand

qfor which we have LDr(Ln

q)= Idr(Ln

q)?

•Figures 1, 2 and 3 allow to see the evolu-

tion of the ratios γr(Ln

q)/Id(Ln

q), or rather their

approximations, based on the computed va-

lues of these two parameters, respectively for

q= 4,q= 5 and q= 6. Each ﬁgu-

re contains ﬁve curves, one for each value

of r∈ {1,2,3,4,5}. The x-axis represents

the dimension n; the y-axis provides the

approximation of γr(Ln

q)/Id(Ln

q). As we have

γr(Ln

q)6Id(Ln

q), the ratios are always upper

bounded by 1. In a sense, a curve illustrates,

for the associated radius r, the part of the code

required for the r-domination and the one requi-

red for the r-separation. Except for few va-

lues, we observe that the curves are rather in-

creasing, which would mean that the part of the

r-domination becomes more and more impor-

tant inside the code when nincreases, for ﬁxed

qand r. Of course, as the computed values

of LD(Ln

q)and of Id(Ln

q)are quite similar, we

would observe the same phenomenon if studying

the ratios γr(Ln

q)/LD(Ln

q). This suggests the

next open problem.

Open problem 4. [Increase of γr(Ln

q)/LD(Ln

and of γr(Ln

q)/Id(Ln

q)with respect to nfor nlarge

enough] Let rand qbe given. Do there exist inte-

gers NLD(r, q)and NId(r, q)such that, respectively

for n>NLD(r, q)and n>NId(r, q), the values

of γr(Ln

q)/LD(Ln

q)and of γr(Ln

q)/Id(Ln

q)increase

when nincreases?

If so, what are the values of the limits of

γr(Ln

q)/LD(Ln

q)and of γr(Ln

q)/Id(Ln

q)? Are they

equal to 1? Otherwise, is the limit of LD(Ln

q)/Id(Ln

anyway equal to 1?

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.24

Irene Charon, Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

179

Volume 21, 2022

References:

[1] J. Astola, The theory of Lee codes, Research Re-

port 1, Lappeenranta University of Technology,

Department of Physics and Mathematics, 1982.

[2] D. Auger, I. Charon, O. Hudry and A. Lobstein,

Complexity results for identifying codes in pla-

nar graphs, International Transactions in Opera-

tional Research Vol. 17, No 6, 2010, pp. 691-710.

[3] I. Charon, G. Cohen, O. Hudry and A. Lob-

stein, New identifying codes in the binary Ham-

ming space, European J. Combin., Vol. 31,

2010, pp. 491–501. See also: perso.telecom-

paristech.fr/∼hudry/newIdentifyingNcube.html

[4] I. Charon and O. Hudry, The noising methods: a

generalization of some metaheuristics, European

Journal of Operational Research, Vol. 135, No 1,

2001, pp. 86-101.

[5] I. Charon and O. Hudry, The noising methods,

in: P. Siarry (ed.), Heuristics: Theory and Appli-

cations, Nova Publishers, 2013, pp. 1-30.

[6] I. Charon, O. Hudry and A. Lobstein, Minimizing

the size of an identifying or locating-dominating

code in a graph is NP-hard, Theoretical Com-

puter Science A, Vol. 290, No 3, 2003, pp. 2109-

2120.

[7] G. Cohen, I. Honkala, S. Litsyn and A. Lobstein,

Covering Codes, Elsevier, Amsterdam, 1997.

[8] C. J. Colbourn, P. J. Slater and L. K. Stewart,

Locating dominating sets in series parallel net-

works, Congr. Numer., Vol. 56, 1987, pp. 135–

162.

[9] R. Dhanalakshmi and C. Durairajan, On r-

identifying codes in binary Hamming space, q-

ary Lee space and incomplete hypercube, Dis-

crete Math., Algo. and Appl., Vol. 11, No 2, 2019,

article No 1950027.

[10] R. Dhanalakshmi and C. Durairajan, Con-

structions of r-identifying codes and (r, 6ℓ)-

identifying codes, Indian J. Pure Appl. Math.,

Vol. 50, No 2, 2019, pp. 531–547.

[11] R. Dhanalakshmi and C. Durairajan, Bounds on

r-identifying codes in q-ary Lee space, Contri-

butions to Discrete Mathematics, Vol. 16, No 1,

2021, pp. 53–71.

[12] G. Exoo, V. Junnila, T. Laihonen and S. Ranto,

Improved bounds on identifying codes in binary

Hamming spaces, European J. Combin., Vol. 31,

2010, pp. 813–827.

[13] G. Exoo, T. Laihonen, S. Ranto, Improved up-

per bounds on binary identifying codes, IEEE

Transactions on Information Theory, Vol. 53,

2007, pp. 4255–4260.

[14] S. Gravier, R. Klasing and J. Moncel, Hardness

results and approximation algorithms for iden-

tifying codes and locating-dominating codes in

graphs, Algorithmic Operations Research, Vol. 3,

No 1, 2008, pp. 43-50.

[15] H. O. H¨am¨al¨ainen, I. S. Honkala, S. Litsyn

and P. R. J. ¨

Osterg˚ard, Football pools – a game

for mathematicians, Am. Math. Mon., Vol. 102,

1995, pp. 579–588.

[16] T. W. Haynes, S. T. Hedetniemi and P. J. Slater,

Fundamentals of Domination in Graphs, Marcel

Dekker, New York, 1998.

[17] T. W. Haynes, S. T. Hedetniemi and M. A.

Henning (eds.), Topics in Domination in Graphs,

Springer, Berlin, 2020.

[18] I. Honkala, T. Laihonen and S. Ranto, On

locating-dominating codes in binary Hamming

spaces, Discrete Math. Theor. Comput. Sci.,

Vol. 6, 2004, pp. 265–282.

[19] O. Hudry and A. Lobstein, The compared costs

of domination, location-domination and identiﬁ-

cation, Discussiones Mathematicae-Graph Theo-

ry, Vol. 40, 2020, pp. 127–147.

[20] M. G. Karpovsky, K. Chakrabarty and L. B.

Levitin, On a new class of codes for identifying

vertices in graphs, IEEE Trans. Inform. Theory,

Vol. IT-44, 1998, pp. 599–611.

[21] J. L. Kim and S. J. Kim, Identifying codes

in q-ary hypercubes, Bull. Instit. Combin. Appl.,

Vol. 59, 2010, pp. 93–102.

[22] A. Lobstein, Covering radius.

https://www.lri.fr/∼lobstein/bib-a-jour.pdf

[23] A. Lobstein, Watching systems, identifying,

locating-dominating and discriminating codes in

graphs, a bibliography.

https://www.lri.fr/∼lobstein/debutBIBidetlocdom.pdf

[24] A. Lobstein, O. Hudry and I. Charon, Locating-

domination and identiﬁcation, in: T. Hayes,

S. Hedetniemi, M. Henning (eds.), Topics in

Domination in Graphs, Springer, Berlin, 2020,

pp. 251-299.

[25] R. Marti, P. M. Pardalos and M. G. C. Resende

(eds), Handbook of Heuristics, Springer, Berlin,

2018.

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.24

Irene Charon, Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

180

Volume 21, 2022

[26] D. F. Rall and P. J. Slater, On location-

domination numbers for certain classes of graphs,

Congr. Numer., Vol. 45, 1984, pp. 97–106.

[27] N. S. V. Rao, Computational complexity issues

in operative diagnosis of graph-based systems,

IEEE Trans. Comput., Vol. 42, 1993, pp. 447–

457.

[28] N. V. Shinde and B. N. Waphare, Improved

upper bounds for identifying codes in n-

dimensional q-ary cubes, Int. J. Appl. Comput.

Math., Vol. 6, 2020, article No 43.

[29] P. Siarry (ed.), Heuristics: Theory and Applica-

tions, Nova Publishers, New York, 2013.

[30] P. J. Slater, Domination and location in graphs,

Research Report No 93, National University of

Singapore, 1983.

Contribution of individual authors to

the creation of a scientiﬁc article

(ghostwriting policy)

The three authors contribute equally to all the aspects

of this work.

Creative Commons Attribution License 4.0

(Attribution 4.0 International, CC BY 4.0)

This article is published under the terms of the Creative

Commons Attribution License 4.0

https://creativecommons.org/licenses/by/4.0/deed.en_US

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.24

Irene Charon, Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

181

Volume 21, 2022

r= 1 r= 2 r= 3 r= 4 r= 5

n(qn)Vn,r,q ⌈qn

Vn,r,q ⌉ Vn,r,q ⌈qn

Vn,r,q ⌉

q= 4

2 (16) 5 4 11 2 15 2 16 1 16 1

3 (64) 7 10 22 3 42 2 57 2 63 2

4 (256) 9 29 37 7 93 3 163 2 219 2

5 (1024) 11 94 56 19 176 6 386 3 638 2

6 (4096) 13 316 79 52 299 14 794 6 1145 4

7 (16384) 15 1093 106 155 470 35 1471 12 3473 5

q= 5

2 (25) 5 5 13 2 21 2 25 1 25 1

3 (125) 7 18 25 5 57 3 93 2 117 2

4 (625) 9 70 41 16 121 6 257 3 417 2

5 (3125) 11 285 61 52 221 15 581 6 1173 3

6 (15625) 13 1202 85 184 365 43 1145 14 2777 6

7 (78125) 15 5209 113 692 561 140 2045 39 5797 14

q= 6

2 (36) 5 8 13 3 23 2 31 2 35 2

3 (216) 7 31 25 9 60 4 108 2 156 2

4 (1296) 9 144 41 32 125 11 285 5 517 3

5 (7776) 11 707 61 128 226 35 626 13 1378 6

6 (46656) 13 3589 85 549 371 126 1211 39 3143 15

7 (279936) 15 18663 113 2478 568 493 2136 132 6392 44

Table 1: lower bounds given by (3), for 46q66,26n67and 16r65.

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.24

Irene Charon, Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

182

Volume 21, 2022

n(qn)r= 1 r= 2 r= 3 r= 4 r= 5

γLD Id γLD Id γLD Id γLD Id γLD Id

2 (16) 4∗e6∗b7∗f[7h]2∗e5∗b4i6∗f[7i] 2∗c[8∗c] 15∗b[15∗c]1∗d[15∗d] - 1∗d[15∗d] -

3 (64) 12∗b16 18h19 [21i] 4∗b8∗b8∗f[8i]2∗e7∗b5i7∗b[7i]2∗e15 4i18 [20i] 2∗c[32∗c] [63∗c]

4 (256) 32 56 56h62 [67i] 12 20 17i21 [22i] 4∗b13 8i13 [14i] 2∗e11 5i13 [14i] 2∗e21 4i21 [22i]

5 (1024) 120 203 183h211 [266i] 30 57 42i60 [92i] 12 28 17i28 [51i] 4∗b16 8i16 [24i] 2∗e16 5i18 [28i]

6 (4096) 385 723 623h748 [1064i] 104 174 115i187 [352i] 31 67 35i70 [154i] 12 34 16i34 [64i] 4∗e25 8i25 [46i]

7 (16384) 1540 2690 2164h2711 [4256i] 341 568 334i586 [1407i] 96 182 81i184 [462i] 33 77 32i78 [176i] 13 41 15i41 [112i]

Table 2: bounds for q= 4

n(qn)r= 1 r= 2 r= 3 r= 4 r= 5

γLD Id γLD Id γLD Id γLD Id γLD Id

2 (25) 5∗e9∗b10∗b[10g] 3∗b6∗b6∗b[6i] 2∗e9∗b10∗b[11i] 1∗d[24∗d]- 1∗d[24∗d] -

3 (125) 20 32 36 [39i] 8∗b14 15 [16i] 3∗e10 11 [11i] 2∗e13 14 [15i] 2∗e27 32 [33i]

4 (625) 84 139 150 [195i] 20 44 48 [73i] 9 23 25 [42i] 4∗b18 18 [18i] 3∗b20 20 [20i]

5 (3125) 397 624 654 [975i] 98 163 175 [365i] 31 69 70 [160i] 13 37 37 [52i] 5∗b27 27 [38i]

6 (15625) 1792 2811 2912 [4875i] 391 639 685 [1521i] 113 217 219 [624i] 40 93 93 [256i] 16 52 52 [176i]

7 (78125) 8422 13135 13539 [24375i] 1648 2613 2701 [7605i] 419 733 739 [2847i] 130 264 265 [1168i] 48 121 124 [520i]

Table 3: bounds for q= 5

n(qn)r= 1 r= 2 r= 3 r= 4 r= 5

γLD Id γLD Id γLD Id γLD Id γLD Id

2 (36) 8∗e12∗b12g14∗b[14i] 4∗b7∗b8∗b[9g] 2∗e7∗b8∗b[9i] 2∗e9∗b13∗b[14i] 2∗c[18∗c] [35∗c]

3 (216) 36 52 54∗g54 [54∗g] 12 23 24 [27i] 6∗b14 14 [16i] 2∗e11 11 [13i] 2∗e14 14 [16i]

4 (1296) 144 288 260g310 [324g] 47 94 98 [149i] 16 46 47 [75i] 9 26 27 [48i] 4∗b23 23 [29i]

5 (7776) 864 1552 1296g1609 [1701g] 241 416 445 [756i] 79 167 168 [378i] 30 79 81 [224i] 14 47 47 [117i]

6 (46656) 5184 8616 6666g8747 [8748g] 1195 1992 2039 [2916i] 338 636 644 [1458i] 117 255 259 [729i] 47 126 128 [432i]

7 (279936) 31104 [34992a] [34992∗f g ] 5961 9378 10540 [17496i] 1517 2583 2882 [8046i] 473 887 901 [4023i] 177 376 389 [2025i]

Table 4: bounds for q= 6

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.24

Irene Charon, Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

183

Volume 21, 2022

n(qn)r= 1 r= 2 r= 3 r= 4 r= 5

γLD Id γLD Id γLD Id γLD Id γLD Id

2 (16) 25 %* 37.5 %* 43.75 %* 12.5 %* 31.25 %* 37.5 %* 12.5 %* 50 %* 93.75 %* 6.25 %* 93.75 %* - 6.25* % 93.75* % -

3 (64) 18.75 %* 25 % 29.69 % 6.25 %* 12.5 %* 12.5 %* 3.13 %* 10.94 %* 10.94 %* 3.13 %* 23.44 % 28.13 % 3.13 %* 50 %* 98.44 %*

4 (256) 12.5 % 21.88 % 24.22 % 4.69 % 7.81 % 8.20 % 1.56 %* 5.08 % 5.08 % 0.78 %* 4.30 % 5.08 % 0.78 %* 8.20 % 8.20 %

5 (1024) 11.72 % 19.82 % 20.61 % 2.93 % 5.57 % 5.86 % 1.17 % 2.73 % 2.73 % 0.39 %* 1.56 % 1.56 % 0.20 %* 1.56 % 1.76 %

6 (4096) 9.40 % 17.65 % 18.26 % 2.54 % 4.25 % 4.57 % 0.76 % 1.64 % 1.71 % 0.29 % 0.83 % 0.83 % 0.10 %* 0.61 % 0.61 %

7 (16384) 9.40 % 16.42 % 16.55 % 2.08 % 3.47 % 3.58 % 0.59 % 1.11 % 1.12 % 0.20 % 0.47 % 0.48 % 0.08 % 0.25 % 0.25 %

Table 5: upper bounds for densities for q= 4

n(qn)r= 1 r= 2 r= 3 r= 4 r= 5

γLD Id γLD Id γLD Id γLD Id γLD Id

2 (25) 20 %* 36 %* 40 %* 12 %* 24 %* 24 %* 8 %* 36 %* 40 %* 4 %* 96 %* - 4 %* 96 %* -

3 (125) 16 % 25.6 % 28.8 % 6.4 %* 11.2 % 12 % 2.4 %* 8 % 8.8 % 1.6 %* 10.4 % 11.2 % 1.6 %* 21.6 % 25.6 %

4 (625) 13.44 % 22.24 % 24 % 3.2 % 7.04 % 7.68 % 1.44 % 3.68 % 4 % 0.64 %* 2.88 % 2.88 % 0.48 %* 3.2 % 3.2 %

5 (3125) 12.7 % 19.97 % 20.93 % 3.14 % 5.22 % 5.6 % 0.99 % 2.21 % 2.24 % 0.42 % 1.18 % 1.18 % 0.16 %* 0.86 % 0.86 %

6 (15625) 11.47 % 17.99 % 18.64 % 2.50 % 4.09 % 4.38 % 0.72 % 1.39 % 1.40 % 0.26 % 0.60 % 0.60 % 0.10 % 0.33 % 0.33 %

7 (78125) 10.78 % 16.81 % 17.33 % 2.11 % 3.34 % 3.46 % 0.54 % 0.94 % 0.95 % 0.17 % 0.34 % 0.34 % 0.06 % 0.15 % 0.16 %

Table 6: upper bounds for densities for q= 5

n(qn)r= 1 r= 2 r= 3 r= 4 r= 5

γLD Id γLD Id γLD Id γLD Id γLD Id

2 (36) 22.22 %* 33.33 %* 38.89 %* 11.11 %* 19.44 %* 22.22 %* 5.56 %* 19.44 %* 22.22 %* 5.56 %* 25 %* 36.11 %* 5.56 %* 50 %* 97.22 %*

3 (216) 16.67 % 24.07 % 25 %* 5.56 % 10.65 % 11.11 % 2.78 %* 6.48 % 6.48 % 0.93 %* 5.09 % 5.09 % 0.93 %* 6.48 % 6.48 %

4 (1296) 11.11 % 22.22 % 23.92 % 3.63 % 7.25 % 7.56 % 1.23 % 3.55 % 3.63 % 0.69 % 2.01 % 2.08 % 0.31 %* 1.77 % 1.77 %

5 (7776) 11.11 % 19.96 % 20.69 % 3.10 % 5.35 % 5.72 % 1.02 % 2.15 % 2.16 % 0.39 % 1.02 % 1.04 % 0.18 % 0.60 % 0.60 %

6 (46656) 11.11 % 18.47 % 18.75 % 2.56 % 4.27 % 4.37 % 0.72 % 1.36 % 1.38 % 0.25 % 0.55 % 0.56 % 0.10 % 0.27 % 0.27 %

7 (279936) 11.11 % 12.5 % 12.5 %* 2.13 % 3.35 % 3.77 % 0.54 % 0.92 % 1.03 % 0.17 % 0.32 % 0.32 % 0.06 % 0.13 % 0.14 %

Table 7: upper bounds for densities for q= 6

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.24

Irene Charon, Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

184

Volume 21, 2022

Figure 1: Approximation of the ratios γr(Ln

4)/Id(Ln

4)from the computed values.

Figure 2: Approximation of the ratios γr(Ln

5)/Id(Ln

5)from the computed values.

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.24

Irene Charon, Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

185

Volume 21, 2022

Figure 3: Approximation of the ratios γr(Ln

6)/Id(Ln

6)from the computed values.

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.24

Irene Charon, Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

186

Volume 21, 2022