Optimal Quasi-Gray Codes: Does the Alphabet Matter?∗
Diptarka Chakraborty†1 , Debarati Das‡2 , Michal Koucký§ 3 , and Nitin Saurabh¶4
1,2,3,4

Computer Science Institute of Charles University, Malostranské náměstí 25, 118 00
Praha 1, Czech Republic

arXiv:1712.01834v1 [] 5 Dec 2017

December 7, 2017

Abstract
A quasi-Gray code of dimension n and length ℓ over an alphabet Σ is a sequence of
distinct words w1 , w2 , . . . , wℓ from Σn such that any two consecutive words differ in at most
c coordinates, for some fixed constant c > 0. In this paper we are interested in the read and
write complexity of quasi-Gray codes in the bit-probe model, where we measure the number
of symbols read and written in order to transform any word wi into its successor wi+1 .
We present construction of quasi-Gray codes of dimension n and length 3n over the
ternary alphabet {0, 1, 2} with worst-case read complexity O(log n) and write complexity 2.
This generalizes to arbitrary odd-size alphabets. For the binary alphabet, we present quasiGray codes of dimension n and length at least 2n − 20n with worst-case read complexity
6 + log n and write complexity 2.
Our results significantly improve on previously known constructions and for the odd-size
alphabets we break the Ω(n) worst-case barrier for space-optimal (non-redundant) quasiGray codes with constant number of writes. We obtain our results via a novel application
of algebraic tools together with the principles of catalytic computation [Buhrman et al. ’14,
Ben-Or and Cleve ’92, Barrington ’89, Coppersmith and Grossman ’75]. We also establish
certain limits of our technique in the binary case. Although our techniques cannot give
space-optimal quasi-Gray codes with small read complexity over the binary alphabet, our
results strongly indicate that such codes do exist.

The research leading to these results has received funding from the European Research Council under the
European Union’s Seventh Framework Programme (FP/2007-2013)/ERC Grant Agreement no. 616787. The
third author was also partially supported by the Center of Excellence CE-ITI under the grant P202/12/G061 of
GA ČR.
†
diptarka@iuuk.mﬀ.cuni.cz
‡
debaratix710@gmail.com
§
koucky@iuuk.mﬀ.cuni.cz
¶
nitin@iuuk.mﬀ.cuni.cz
∗

1

1

Introduction

One of the fundamental problems in the domain of algorithm design is to list down all the objects
belonging to a certain combinatorial class. Researchers are interested in eﬃcient generation of a
list such that an element in the list can be obtained by small amount of changes to the element
that precedes it. One of the classic examples is the binary Gray code introduced by Gray [16],
initially used in pulse code communication. The original idea of a Gray code was to list down all
the binary strings of length n, i.e, all the elements of Zn2 such that any two successive strings diﬀer
by exactly one bit. The idea was later generalized for other combinatorial classes. Interested
reader may refer to an excellent survey by Savage [29] for a comprehensive treatment on this
subject.
In this paper we study the construction of Gray codes over Znm for any m ∈ N. Originally,
Gray codes were meant to list down all the elements from its domain but later studies focused
on the generalization where we list ℓ distinct elements from the domain, each two consecutive
elements diﬀering in one position. We refer to such codes as Gray codes of length ℓ [14]. When
the code lists all the elements from its domain it is referred to as space-optimal. It is often
required that the last and the ﬁrst strings appearing in the list also diﬀer in one position. Such
codes are called cyclic Gray codes. Throughout this paper we consider only cyclic Gray codes
and we refer to them simply as Gray codes. Researchers also study codes where two successive
strings diﬀer in at most c positions, for some ﬁxed constant c > 0, instead of diﬀering in exactly
one position. Such codes are called quasi-Gray codes [3]1 or c-Gray codes.
We study the problem of constructing quasi-Gray codes over Znm in the cell probe model [34],
where each cell stores an element from Zm . The eﬃciency of a construction is measured using
three parameters. First, we want the length of the quasi-Gray code to be as large as possible,
ideally we want space-optimal codes. Second, we want to minimize the number of coordinates
of the input string the algorithm reads in order to generate the next (or, previous) string in the
code. Finally, we also want the number of cells written in order to generate the successor (or,
predecessor) string to be as small as possible. Since our focus is on quasi-Gray codes, the number
of writes will always be bounded by a universal constant. We are interested in the worst-case
behavior and we use decision assignment trees of Fredman [14] to measure these complexities.
Although there are known quasi-Gray codes with logarithmic read complexity and constant
write complexity [14, 27, 3, 4], none of these constructions is space-optimal. The best result
misses at least 2n−t strings from the domain when having read complexity t+O(log n) [4]. Despite
of an extensive research under many names, e.g., construction of Gray codes [14, 26, 11, 17],
dynamic language membership problem [13], eﬃcient representation of integers [27, 4], so far we
do not have any quasi-Gray code of length 2n − 2ǫn , for some constant ǫ < 1, with worst-case
read complexity o(n) and write complexity o(n). The best worst-case read complexity for spaceoptimal Gray code is n − 1 [15]. Indeed, there are various conjectures [27, 3] on non-existence of
space-optimal Gray codes with sub-linear read complexity and constant write complexity. Our
main result dispels such conjectures for quasi-Gray codes over Znm , when m is odd. In particular,
we construct space-optimal quasi-Gray codes over {0, 1, 2}n with read complexity 4 log3 n and
write complexity 2.
Theorem 1.1. Let m ∈ N be odd and n ∈ N be sufficiently large. Then, there is a spaceoptimal quasi-Gray code C over Znm for which, the two functions next(C, w) and prev(C, w) can
be implemented by inspecting at most 4 logm n cells while writing only 2 cells.
In the statement of the above theorem, next(C, w) denotes the element appearing after w in
1
Readers may note that the deﬁnition of quasi-Gray code given in [14] was diﬀerent. The code referred as
quasi-Gray code by Fredman [14] is called Gray code of length ℓ where ℓ < mn , in our notation.

2

the cyclic sequence of the code C, and analogously, prev(C, w) denotes the preceding element.
In the case of space-optimal quasi-Gray codes over binary strings, the read complexity must be
at least Ω(log n) bits [14, 26]. This readily generalizes to a lower bound of Ω (logm n) in the
bit-probe model when the domain is Znm . Hence our result is optimal up to some small constant
factor.
Using a diﬀerent technique we also get a quasi-Gray code over the binary alphabet which
enumerates all but O(n) many strings. This result generalizes to the domain Znq for any prime
power q.
Theorem 1.2. Let n ∈ N be sufficiently large. Then, there is a quasi-Gray code C of length at
least 2n −20n over Zn2 , such that the two functions next(C, w) and prev(C, w) can be implemented
by inspecting at most 6 + log n cells while writing only 2 cells.
We remark that the points that are missing from C in the above theorem are all of the form
{0, 1}O(log n) 0n−O(log n) .
If we are allowed to read and write constant fraction of n bits then Theorem 1.2 can be
adapted to get a quasi-Gray code of length 2n − O(1) (see Section 5). In this way we get a
trade-oﬀ between length of the quasi-Gray code and the number of bits read in the worst-case.
All our constructions can be made uniform.
Using Chinese Remainder Theorem (cf. [9]), we also develop a technique that allows us
to compose Gray codes over various domains. Hence, from quasi-Gray codes over domains
Znm1 , Znm2 , . . . Znmk , where mi ’s are pairwise co-prime, we can construct quasi-Gray codes over
′
Znm , where m = m1 · m2 · · · mk . Using this technique on our main results, we get a quasi-Gray
code over Znm for any m ∈ N that misses only O(n · on ) strings where m = 2ℓ o for an odd o, while
achieving the read complexity similar to that stated in Theorem 1.1. It is worth mentioning that
if we get a space-optimal quasi-Gray code over the binary alphabet with non-trivial savings in
read complexity, then we will have a space-optimal quasi-Gray code over the strings of alphabet
Zm for any m ∈ N with similar savings.
The technique by which we construct our quasi-Gray codes relies heavily on simple algebra
which is a substantial departure from previous mostly combinatorial constructions. We view
Gray codes as permutations on Znm and we decompose them into k simpler permutations on
Znm , each being computable with read complexity 3 and write complexity 1. Then we apply
′
a diﬀerent composition theorem, than mentioned above, to obtain quasi-Gray codes on Znm ,
n′ = n + log k, with read complexity O(1) + log k and write complexity 2. The main issue is the
decomposition of permutations into few simple permutations. This is achieved by techniques of
catalytic computation [5] going back to the the work of Coppersmith and Grossman [8, 1, 2].
It follows from the work of Coppersmith and Grossman [8] that our technique is incapable
′
of designing a space-optimal quasi-Gray code on Zn2 as any such code represents an odd permutation. The tools we use give inherently only even permutations. However, we can construct
quasi-Gray codes from cycles of length 2n − 1 on Zn2 as they are even permutations. Indeed, that
is what we do for our Theorem 1.2. Any eﬃciently computable odd permutation on Zn2 , with say
read complexity (1 − ǫ)n and write complexity O(1), could be used together with our technique
′
to construct a space-optimal quasi-Gray code on Zn2 with read complexity at most (1 − ǫ′ )n′
and constant write complexity. This would represent a major progress on space-optimal Gray
codes. (We would compose the odd permutation with some even permutation to obtain a full
cycle on Zn2 . The size of the decomposition of the even permutation into simpler permutations
would govern the read complexity of the resulting quasi-Gray code.)
Our results imply that any potential lower bound on the complexity of quasi-Gray codes
′
over Zn2 must distinguish between the binary and ternary alphabets with certain consequences
on algebraic properties of permutations.
3

In addition to our positive results we provide also an impossibility result for the construction
of Gray codes in a certain structured way.

1.1

Related works

The construction of Gray codes is central to the design of algorithms for many combinatorial
problems [29]. Frank Gray [16] ﬁrst came up with a construction of Gray code over binary
strings of length n, where to generate the successor or predecessor strings one needs to read
n bits in the worst-case. The type of code described in [16] is known as binary reflected Gray
code. Later Bose et al. [3] provided a diﬀerent type of Gray code construction, namely recursive
partition Gray code which attains O(log n) average case read complexity while having the same
worst-case read requirements. The read complexity we referred here is in the bit-probe model.
It is easy to observe that any space-optimal binary Gray code must read log n + 1 bits in the
worst-case [14, 26, 15] and surprisingly this is the best known lower bound till date. An upper
bound of even n − 1 was not known until very recently [15]. This is also the best known so far.
Fredman [14] extended the deﬁnition of Gray codes by considering codes that may not
enumerate all the strings (though presented in a slightly diﬀerent way in [14]) and also introduced
the notion of decision assignment tree (DAT) to study the complexity of any code in bit-probe
model. He provided a construction that generates a Gray code of length 2c·n for some constant
c < 1 while reducing the worst-case bit-read to O(log n). Using the idea of Lucal’s modiﬁed
reﬂected binary code [22], Munro and Rahman [27] got a code of length 2n−1 with worst-case read
complexity only 4 + log n. However in their code two successive strings diﬀer by 4 coordinates
in the worst-case, instead of just one and we refer to such codes as quasi-Gray codes following
the nomenclature used in [3]. Brodal et al. [4] extended the results of [27] by constructing a
quasi-Gray code of length 2n − 2n−t for arbitrary 1 ≤ t ≤ n − log n − 1, that has t + 3 + log n
bits (t + 2 + log n bits) worst-case read complexity and any two successive strings in the code
diﬀer by at most 2 bits (3 bits).
In contrast to the Gray codes over binary alphabets, Gray codes over non-binary alphabets
received much less attention. The construction of binary reﬂected Gray code was generalized to
the alphabet Zm for any m ∈ N in [12, 7, 18, 28, 19]. However, each of those constructions read
n coordinates in the worst-case to generate the next element. As mentioned before, we measure
the read complexity in the well studied bit-probe model [34] where we assume that each cell
stores an element of Zm . The argument of Fredman in [14] implies a lower bound of Ω(logm n)
on the read complexity of quasi-Gray code on Znm . To the best of our knowledge, for non-binary
alphabets, there is nothing known similar to the results of Munro and Rahman or Brodal et al.
[27, 4]. We summarize the previous results along with ours in Table 1.
Additionally, many variants of Gray codes have been studied in the literature. A particular
one that has garnered a lot of attention in the past 30 years is the well-known middle levels
conjecture. See [23, 24, 25, 17], and the references therein. It has been established only recently
[23]. The conjecture says that there exists a Hamiltonian cycle in the graph induced by the
vertices on levels n and n + 1 of the hypercube graph in 2n + 1 dimensions. In other words,
there exists a Gray code on the middle levels. Mütze et al. [24, 25] studied the question of
eﬃciently enumerating such a Gray code in the word RAM model. They [25] gave an algorithm
to enumerate a Gray code in the middle levels that requires O(n) space and on average takes
O(1) time to generate the next vertex. In this paper we consider the bit-probe model, and Gray
codes over the complete hypercube. It would be interesting to know whether our technique can
be applied for the middle level Gray codes.

4

Reference
[16]
[14]
[13]
[27]
[3]
[4]
[4]
[15]
Theorem 1.2
[7]
Theorem 1.1

Value of m
2
2
2
2
2
2
2
2
2
any m
any odd m

length
2n
2Θ(n)
Θ(2n /n)
2n−1
2n − O(2n /nt )
2n − 2n−t
2n − 2n−t
2n
2n − O(n)
mn
mn

Worst-case cell read
n
O(log n)
log n + 1
log n + 4
O(t log n)
log n + t + 3
log n + t + 2
n−1
log n + 4
n
4 logm n + 3

Worst-case cell write
1
O(1)
log n + 1
4
3
2
3
1
2
1
2

Table 1: Taxonomy of construction of Gray/quasi-Gray codes over Znm

1.2

Our technique

Our construction of Gray codes relies heavily on the notion of s-functions deﬁned by Coppersmith and Grossman [8]. An s-function is a permutation τ on Znm deﬁned by a function
f : Zsm → Zm and an (s + 1)-tuple of indices i1 , i2 , . . . , is , j ∈ [n] such that τ (hx1 , x2 , . . . , xn i) =
(hx1 , x2 , . . . , xj−1 , xj + f (xi1 , . . . , xis ), xj+1 , . . . , xn i), where the addition is inside Zm . Each sfunction can be computed by some decision assignment tree that given a vector x = hx1 , x2 , . . . , xn i,
inspects s + 1 coordinates of x and then it writes into a single coordinate of x.
A counter C (quasi-Gray code) on Znm can be thought of as a permutation on Znm . Our goal
is to construct some permutation α on Znm that can be written as a composition of 2-functions
α1 , . . . , αk , i.e., α = αk ◦ αk−1 ◦ · · · ◦ α1 .
r+n , where r = ⌈log n⌉,
Given such a decomposition, we can build another counter C ′ on Zm
m
for which the function next(C ′ , x) operates as follows. The ﬁrst r-coordinates of x serve as an
instruction pointer i ∈ [mr ] that determines which αi should be executed on the remaining n
coordinates of x. Hence, based on the current value i of the r coordinates, we perform αi on the
remaining coordinates and then we update the value of i to i + 1. (For i > k we can execute the
identity permutation which does nothing.)
We can use known Gray codes on Zrm to represent the instruction pointer so that when
incrementing i we only need to write into one of the coordinates. This gives a counter C ′ which
can be computed by a decision assignment tree that reads r + 3 coordinates and writes into 2
coordinates of x. (A similar composition technique is implicit in Brodal et al. [4].) If C is of
length ℓ = mn − t, then C ′ is of length mn+r − tmr . In particular, if C is space-optimal then so
is C ′ .
Hence, we reduce the problem of constructing 2-Gray codes to the problem of designing
large cycles in Znm that can be decomposed into 2-functions. Coppersmith and Grossman [8]
studied precisely the question of, which permutations on Zn2 can be written as a composition of
2-functions. They show that a permutation on Zn2 can be written as a composition of 2-functions
if and only if the permutation is even. Since Zn2 is of even size, a cycle of length 2n on Zn2 is an
odd permutation and thus it cannot be represented as a composition of 2-functions. However,
their result also implies that a cycle of length 2n − 1 on Zn2 can be decomposed into 2-functions.
We want to use the counter composition technique described above in connection with a
cycle of length 2n − 1. To maximize the length of the cycle C ′ in Z2n+r , we need to minimize k,
the number of 2-functions in the decomposition. By a simple counting argument, most cycles of
length 2n − 1 on Zn2 require k to be exponentially large in n. This is too large for our purposes.
5

Luckily, there are cycles of length 2n − 1 on Zn2 that can be decomposed into polynomially many
2-functions, and we obtain such cycles from linear transformations.
There are linear transformations Zn2 → Zn2 which deﬁne a cycle on Zn2 of length 2n − 1. For
example, the matrix corresponding to the multiplication by a ﬁxed generator of the multiplicative
group (Zn2 )∗ of the Galois ﬁeld GF [2n ] is such a matrix. Such matrices are full rank and they can
be decomposed into O(n2 ) elementary matrices, each corresponding to a 2-function. Moreover,
there are matrices derived from primitive polynomials that can be decomposed into at most
′
′
4n elementary matrices.2 We use them to get a counter on Zn2 of length at least 2n − 20n′
whose successor and predecessor functions are computable by decision assignment trees of read
complexity ≤ 6 + log n′ and write complexity 2. Such counter represents 2-Gray code of the
prescribed length. For any prime q, the same construction yields 2-Gray codes of length at least
′
q n − 5q 2 n′ with decision assignment trees of read complexity ≤ 6 + logq n′ and write complexity
2.
The results of Coppersmith and Grossman [8] can be generalized to Znm as stated in Richard
Cleve’s thesis [6].3 For odd m, if a permutation on Znm is even then it can be decomposed into
2-functions. Since mn is odd, a cycle of length mn on Znm is an even permutation and so it can
be decomposed into 2-functions. If the number k of those functions is small, so the logm k is
small, we get the sought after counter with small read complexity. However, for most cycles of
length mn on Znm , k is exponential in n.
We show though, that there is a cycle α of length mn on Znm that can be decomposed
′
into O(n3 ) 2-functions. This in turn gives space-optimal 2-Gray codes on Znm with decision
assignment trees of read complexity O(logm n′ ) and write complexity 2.
We obtain the cycle α and its decomposition in two steps. First, for i ∈ [n], we consider
the permutation αi on Znm which maps each element 0i−1 ay onto 0i−1 (a + 1)y, for a ∈ Zm and
n−i , while other elements are mapped to themselves. Hence, α is a product of mn−i
y ∈ Zm
i
disjoint cycles of length m. We show that α = αn ◦ αn−1 ◦ · · · ◦ α1 is a cycle of length mn . In
the next step we decompose each αi into O(n2 ) 2-functions.
For i ≤ n − 2, we can decompose αi using the technique of Ben-Or and Cleve [2] and its
reﬁnement in the form of catalytic computation of Buhrman et al. [5]. We can think of x ∈ Znm
as content of n memory registers, where x1 , . . . , xi−1 are the input registers, xi is the output
register, and xi+1 , . . . , xn are the working registers. The catalytic computation technique gives a
program consisting of O(n2 ) instructions, each being equivalent to a 2-function, which performs
the desired adjustment of xi based on the values of x1 , . . . , xi−1 without changing the ultimate
values of the other registers. (We need to increment xi iﬀ x1 , . . . , xi−1 are all zero.) This program
directly gives the desired decomposition of αi , for i ≤ n − 2. (Our proof in Section 6 uses the
language of permutations.)
The technique of catalytic computation fails for αn−1 and αn as the program needs at least
two working registers to operate. Hence, for αn−1 and αn we have to develop entirely diﬀerent
technique. This is not trivial and quite technical but it is nevertheless possible, thanks to the
speciﬁc structure of αn−1 and αn .

Organization of the paper
In Section 2 we deﬁne the notion of counter, Gray code and our computational model, namely
decision assignment tree and also provide certain known results regarding the construction of
Gray codes. Then in Section 3 we describe how to combine counters over smaller alphabets to
2
Primitive polynomials were previously also used in a similar problem, namely to construct shift-register
sequences (see e.g. [19]).
3
Unfortunately, there is no written record of the proof.

6

get another counter over larger alphabet, by introducing the Chinese Remainder Theorem for
counters. Next we provide some basic facts about the permutation group and the underlying
structure behind all of our constructions of quasi-Gray codes. We devote Section 5 to construction of a quasi-Gray code over binary alphabet that misses only a few words, by using full rank
linear transformation. In Section 6 we construct a space-optimal quasi-Gray code over any oddsize alphabet. Finally in Section 7 we rule out the existence of certain kind of space-optimal
binary counters.

2

Preliminaries

In the rest of the paper we only present constructions of the successor function next(C, w) for our
codes. Since all the operations in those constructions are readily invertible, the same arguments
also give the predecessor function prev(C, w).
Notations: We use the standard notions of groups and ﬁelds, and mostly we will use only
elementary facts about them (see [10, 21] for background.). By Zm we mean the set of integers
modulo m, i.e., Zm := Z/mZ. Throughout this paper whenever we use addition and multiplication operation between two elements of Zm , then we mean the operations within Zm that is
modulo m. For any m ∈ N, we let [m] denote the set {1, 2, . . . , m}. Unless stated otherwise
explicitly, all the logarithms we consider throughout this paper are based 2.
Now we deﬁne the notion of counters used in this paper.
Definition 1 (Counter). A counter of length ℓ over a domain D is any cyclic sequence C =
(w1 , . . . , wℓ ) such that w1 , . . . , wℓ are distinct elements of D. With the counter C we associate
two functions next(C, w) and prev(C, w) that give the successor and predecessor element of w
in C, that is for i ∈ [ℓ], next(C, wi ) = wj where j − i = 1 mod ℓ, and prev(C, wi ) = wk where
i − k = 1 mod ℓ. If ℓ = |D|, we call the counter a space-optimal counter.
Often elements in the underlying domain D have some “structure” to them. In such cases,
it’s desirable to have a counter such that consecutive elements in the sequence diﬀer by a “small”
change in the “structure”. We make this concrete in the following deﬁnition.
Definition 2 (Gray Code). Let D1 , . . . , Dn be finite sets. A Gray code of length ℓ over the
domain D = D1 × · · · × Dn is a counter (w1 , . . . , wℓ ) of length ℓ over D such that any two
consecutive strings wi and wj , j − i = 1 mod ℓ, differ in exactly one coordinate when viewed as
an n-tuple. More generally, if for some constant c ≥ 1, any two consecutive strings wi and wj ,
j − i = 1 mod ℓ, differ in at most c coordinates such a counter is called a c-Gray Code.
By a quasi-Gray code we mean c-Gray code for some unspeciﬁed ﬁxed c > 0. In the literature
sometimes people do not place any restriction on the relationship between wℓ and w1 and they
refer to such a sequence a (quasi)-Gray code. In their terms, our codes would be cyclic (quasi)Gray codes. If ℓ = |D|, we call the codes space-optimal (quasi-)Gray codes.
Decision Assignment Tree: The computational model we consider in this paper is called
Decision Assignment Tree (DAT). The deﬁnition we provide below is a generalization of that
given in [14]. It is intended to capture random access machines with small word size.
Let us ﬁx an underlying domain D n whose elements we wish to enumerate. In the following,
we will denote an element in D n by hx1 , x2 , . . . , xn i. A decision assignment tree is a |D|-ary tree
such that each internal node is labeled by one of the variables x1 , x2 , . . . , xn . Furthermore, each
outgoing edge of an internal node is labeled with a distinct element of D. Each leaf node of the
7

tree is labeled by a set of assignment instructions that set new (ﬁxed) values to chosen variables.
The variables which are not mentioned in the assignment instructions remain unchanged.
The execution on a decision assignment tree on a particular input vector hx1 , x2 , . . . , xn i ∈ D n
starts from the root of the tree and continues in the following way: at a non-leaf node labeled
with a variable xi , the execution queries xi and depending on the value of xi the control passes
to the node following the outgoing edge labeled with the value of xi . Upon reaching a leaf, the
corresponding set of assignment statements is used to modify the vector hx1 , x2 , . . . , xn i and the
execution terminates. The modiﬁed vector is the output of the execution.
Thus, each decision assignment tree computes a mapping from D n into D n . We are interested
in decision assignment trees computing the mapping next(C, hx1 , x2 , . . . , xn i) for some counter
C. When C is space-optimal we can assume, without loss of generality, that each leaf assigns
values only to the variables that it reads on the path from the root to the leaf. (Otherwise,
the decision assignment tree does not compute a bijection.) We deﬁne the read complexity of a
decision assignment tree T , denoted by READ(T ), as the maximum number of non-leaf nodes
along any path from the root to a leaf. Observe that any mapping from D n into D n can be
implemented by a decision assignment tree with read complexity n. We also deﬁne the write
complexity of a decision assignment tree T , denoted by WRITE(T ), as the maximum number
of assignment instructions in any leaf.
Instead of the domain D n , we will sometimes also use domains that are a cartesian product
of diﬀerent domains. The deﬁnition of a decision assignment tree naturally extends to this case
of diﬀerent variables having diﬀerent domains.
For any counter C = (w1 , . . . , wℓ ), we say that C is computed by a decision assignment tree
T if and only if for i ∈ [ℓ], next(C, wi ) = T (wi ), where T (wi ) denotes the output string obtained
after an execution of T on wi . Note that any two consecutive strings in the cyclic sequence of
C diﬀer by at most WRITE(T ) many coordinates.
For a small constant c ≥ 1, some domain D, and all large enough n, we will be interested
in constructing cyclic counters on D n that are computed by decision assignment trees of write
complexity c and read complexity O(log n). By the deﬁnition such cyclic counters will necessarily
be c-Gray codes.

2.1

Construction of Gray codes

For our construction of quasi-Gray codes on a domain D n with decision assignment trees of small
read and write complexity we will need ordinary Gray codes on a domain D O(log n) . Several
constructions of space-optimal binary Gray codes are known where the oldest one is the binary
reﬂected Gray code [16]. This can be generalized to space-optimal (cyclic) Gray codes over
non-binary alphabets (see e.g. [7, 19]).
Theorem 2.1 ([7, 19]). For any m, n ∈ N, there is a space-optimal (cyclic) Gray code over Znm .

3

Chinese Remainder Theorem for Counters

In this paper we consider quasi-Gray codes over Znm for m ∈ N. Below we describe how to
compose decision assignment trees over diﬀerent domains to get a decision assignment tree for
a larger mixed domain.
Theorem 3.1 (Chinese Remainder Theorem for Counters). Let r, n1 , . . . , nr ∈ N be integers,
and let D1,1 , . . . , D1,n1 , D2,1 , . . . , Dr,nr be some finite sets of size at least two. Let ℓ1 ≥ r − 1 be
an integer, and ℓ2 , . . . , ℓr be pairwise co-prime integers. For i ∈ [r], let Ci be a counter of length
ℓi over Di = Di,1 × · · · × Di,ni computed by a decision assignment tree Ti over ni variables. Then,
8

Pr
there exists
a
decision
assignment
tree
T
over
i=1 ni variables that implements a counter C of
Qr
length i=1 ℓi over D1 × · · · × Dr . Furthermore, READ(T ) = n1 + max{READ(Ti )}ri=2 , and
WRITE(T ) = WRITE(T1 ) + max{WRITE(Ti )}ri=2 .
Proof. For any i ∈ [r], let the counter Ci = (wi,1 , . . . , wi,ℓi ). Let x1 , . . . , xr be variables taking
values in D1 , . . . , Dr , respectively. The following procedure, applied repeatedly, deﬁnes the
counter C:
If

x1 = w1,i for some i ∈ [r − 1] then
xi+1 ← next(Ci+1 , xi+1 )
x1 ← next(C1 , x1 )

else
x1 ← next(C1 , x1 ).
It is easily seen that the above procedure deﬁnes a valid cyclic sequence when starting
at w1,i1 , . . . , wr,ir for any hi1 , i2 , . . . , ir i ∈ [ℓ1 ] × · · · × [ℓr ]. That is, every element has a unique
predecessor and a unique successor, and that the sequence is cyclic. It can easily be implemented
by a decision assignment tree, say T . First it reads the value of x1 . Since x1 ∈ D1 = D1,1 ×
· · · × D1,n1 , it queries n1 components. Then, depending on the value of x1 , it reads and updates
another component, say xj . This can be accomplished using the decision assignment tree Tj . We
also update the value of x1 , and to that end we use the appropriate assignments from decision
assignment tree T1 . Observe that irrespective of how eﬃcient T1 is, we read x1 completely
to determine which of the remaining r − 1 counters to update. Hence, READ(T ) = n1 +
max {READ(Ti )}ri=2 , and WRITE(T ) = WRITE(T1 ) + max {WRITE(Ti )}ri=2 .
Q
Now it only remains to show that the counter described above is indeed of length ri=1 ℓi .
Thus, it suﬃces to establish that starting with the string hw1,1 , . . . , wr,1 i, we can generate the
string hw1,i1 , . . . , wr,ir i for any hi1 , . . . , ir i ∈ [ℓ1 ] × · · · × [ℓr ]. Let us assume i1 = 1. At the end of
the proof we will remove this assumption. Suppose the string hw1,1 , w2,i2 , . . . , wr,ir i is reachable
from hw1,1 , w2,1 , . . . , wr,1 i in t steps. As our procedure always increment x1 , t must be divisible
by ℓ1 . Let d = t/ℓ1 . Furthermore, the procedure increments a variable xi , i 6= 1, exactly after ℓ1
steps. Thus, hw1,1 , w2,i2 , . . . , wr,ir i is reachable if and only if d satisﬁes the following equations:
d ≡ i2 − 1 (mod ℓ2 )
d ≡ i3 − 1 (mod ℓ3 )
..
.
d ≡ ir − 1

(mod ℓr ).

Since ℓ2 , . . . , ℓr are pairwise co-prime, Chinese Remainder Theorem (for a reference,
see [9])
Q
guarantees the existence of a unique integral solution d such that 0 ≤Qd < ri=2 ℓi . Hence,
hw1,1 , w2,,i2 , . . . , wr,ir i is reachable from hw1,1 , w2,1 , . . . , wr,1 i in at most ri=1 ℓi steps.
Now we remove the assumption i1 = 1, i.e., w1,i1 6= w1,1 . Consider the string hw1,1 , w2,i′ , . . . , wr,i′ i
r
2
where wj,i′ = wj,ij −1 for 2 ≤ j ≤ min{i1 , r}, and wj,i′ = wj,ij for j > min{i1 , r}. From the
j

j

arguments in the previous paragraph, we know that this tuple is reachable. We now observe
that the next i1 − 1 steps increment w1,1 to w1,i1 and wj,i′ to wj,ij for 2 ≤ j ≤ min{i1 , r}, thus,
j

reaching the desired string hw1,i1 , . . . , wr,ir i.
Remark. We remark that if Ci ’s are space-optimal in Theorem 3.1, then so is C.

9

In the above proof, we constructed a special type of a counter where we always read the
ﬁrst coordinate, incremented it, and further depending on its value, we may update the value
of another coordinate. From now on we refer to such type of counters as hierarchical counters.
In Section 7 we will show that for such type of a counter the co-primality condition is necessary
at least for ℓ1 = 2, 3. One can further note that the above theorem is similar to the well
known Chinese Remainder Theorem and has similar type of application for constructing of
space-optimal quasi-Gray codes over Znm for arbitrary m ∈ N.
Lemma 3.2. Let n, m ∈ N be such that m = 2k o, where o is odd and k ≥ 0. Given decision
assignment trees T1 and T2 computing space-optimal (quasi-)Gray codes over (Z2k )n−1 and Zon−1 ,
respectively, there exists a decision assignment tree T implementing a space-optimal quasi-Gray
code over Znm such that READ(T ) = 1 + max{READ(T1 ), READ(T2 )}, and WRITE(T ) =
1 + max{WRITE(T1 ), WRITE(T2 )}.
Proof. We will view Znm as Zm × (Z2k )n−1 × (Zo )n−1 and simulate a decision assignment tree
operating on Zm × (Z2k )n−1 × (Zo )n−1 on Znm . From the Chinese Remainder Theorem (see [9]),
we know that there exists a bijection (in fact, an isomorphism) f : Zm → Z2k × Zo . We denote the tuple f (z) by hf1 (z), f2 (z)i. From Theorem 3.1 we know that there exists a decision assignment tree T ′ over Zm × (Z2k )n−1 × (Zo )n−1 computing a space-optimal quasiGray code such that READ(T ′ ) = 1 + max{READ(T1 ), READ(T2 )}, and WRITE(T ′ ) =
1 + max{WRITE(T1 ), WRITE(T2 )}.
We can simulate actions of T ′ on an input Znm to obtain the desired decision assignment tree
T . Indeed, whenever T ′ queries x1 , T queries the ﬁrst coordinate of its input. Whenever T ′
queries the i-th coordinate of (Z2k )n−1 , T queries the (i+1)-th coordinate of its input and makes
its decision based on the f1 (·) value of that coordinate. Similarly, whenever T ′ queries the j-th
coordinate of (Zo )n−1 , T queries the (j + 1)-th coordinate and makes its decision based on the
f2 (·) value of that coordinate. Assignments by T are handled in similar fashion by updating only
the appropriate part of hf1 (z), f2 (z)i. (Notice, queries made by T might reveal more information
than queries made by T ′ .)
Before proceeding further, we would also like to point out that to get a space-optimal decision
assignment tree over Z2k , it suﬃces to a get space-optimal decision assignment trees over Z2
for arbitrary dimensions. Thus, to get a decision assignment tree implementing space-optimal
quasi-Gray codes over Zm , we only need decision assignment trees implementing space-optimal
quasi-Gray codes over Z2 and Zo . This also justiﬁes our sole focus on construction of spaceoptimal decision assignment trees over Z2 and Zo in the later sections.
Lemma 3.3. If, for all n ∈ N, there exists a decision assignment tree T implementing a spaceoptimal (quasi-)Gray code over Zn2 , then for any k and n ∈ N, there exists a decision assignment
tree T ′ implementing a space-optimal (quasi-)Gray code over (Z2k )n such that the read and write
complexity remain the same.
Proof. Consider any bijective map f : Z2k → Zk2 . For example, one can take standard binary
encoding of integers ranging from 0 to 2k − 1 as the bijective map f . Next, deﬁne another
map g : (Z2k )n → Zkn
2 as follows: g(x1 , . . . , xn ) = hf (x1 ), . . . , f (xn )i. Now consider T that
implements a space-optimal (quasi-)Gray code over Zkn
2 . We ﬁx a partition of the variables
{1, . . . , k} ⊎ · · · ⊎ {(n − 1)k + 1, . . . , nk} into n blocks of k variables each.
We now construct a decision assignment tree T ′ over (Z2k )n using T and the map f . As in
the proof of Lemma 3.2, our T ′ follows T in the decision making. That is, if T queries a variable,
then T ′ queries the block in the partition where the variable lies. (Again, as noted before, T ′
may get more information than required by T .) Upon reaching a leaf, using f , T ′ updates the
blocks depending on T ’s updates to the variables.
10

We devote the rest of the paper to the construction of counters over Zn2 , and Znm for any odd
m.

4

Permutation Group and Decomposition of Counters

We start this section with some basic notation and facts about the permutation group which we
will use heavily in the rest of the paper. The set of all permutations over a domain D forms a
group under the composition operation, denoted by ◦, which is deﬁned as follows: for any two
permutations σ and α, σ ◦ α(x) = σ(α(x)), where x ∈ D. The corresponding group, denoted SN ,
is the symmetric group of order N = |D|. We say, a permutation σ ∈ SN is a cycle of length ℓ
if there are distinct elements a1 , . . . , aℓ ∈ [N ] such that for i ∈ [ℓ − 1], ai+1 = σ(ai ), a1 = σ(aℓ ),
and for all a ∈ [N ] \ {a1 , a2 , . . . , aℓ }, σ(a) = a. We denote such a cycle by (a1 , a2 , · · · , aℓ ). Below
we state few simple facts about composition of cycles.
Proposition 4.1. Consider two cycles C1 = (t, a1 , · · · , aℓ1 ) and C2 = (t, b1 , · · · , bℓ2 ) where for
any i ∈ [ℓ1 ] and j ∈ [ℓ2 ], ai 6= bj . Then, C = C2 ◦ C1 is the cycle (t, a1 , · · · , aℓ1 , b1 , · · · , bℓ2 ) of
length ℓ1 + ℓ2 + 1.
Proposition 4.2. If σ ∈ SN is a cycle of length ℓ, then for any α ∈ SN , α ◦ σ ◦ α−1 is also a
cycle of length ℓ. Moreover, if σ = (a1 , a2 , · · · , aℓ ), then α ◦ σ ◦ α−1 = (α(a1 ), α(a2 ), · · · , α(aℓ )).
The permutation α ◦ σ ◦ α−1 is called the conjugate of σ with respect to α. The above
proposition is a special case of a well known fact about the cycle structure of conjugates of any
permutation and can be found in any standard text book on Group Theory (e.g., Proposition 10
in Chapter 4.3 of [10].).
Roughly speaking, a counter of length ℓ over D, in the language of permutations, is nothing
but a cycle of the same length in S|D| . We now make this correspondence precise and give a
construction of a decision assignment tree that implements such a counter.
Lemma 4.3. Let D = D1 × · · · × Dr be a domain. Suppose σ1 , . . . , σk ∈ S|D| are such that
σ = σk ◦ σk−1 ◦ · · · ◦ σ1 is a cycle of length ℓ. Let T1 , . . . , Tk be decision assignment trees that
implement σ1 , . . . , σk respectively. Let D ′ = D ′ 1 × · · · × D ′ r′ be a domain such that |D ′ | ≥ k,
and let T ′ be a decision assignment tree that implements a counter C ′ of length k′ over D ′ where
k′ ≥ k.
Then, there exists a decision assignment tree T that implements a counter of length k′ ℓ over
′
D × D such that READ(T ) = r ′ + max{READ(Ti )}ki=1 , and WRITE(T ) = WRITE(T ′ ) +
max{WRITE(Ti )}ki=1 .
Proof. Suppose C ′ = (a1 , . . . , ak′ ). Now let us consider the following procedure P : on any input
hx1 , x2 i ∈ D ′ × D,
If

x1 = aj for some j ∈ [k] then
x2 ← σj (x2 )
x1 ← next(C ′ , x1 )

else
x1 ← next(C ′ , x1 ).
Now using a similar argument as in the proof of Theorem 3.1, the above procedure is easily
seen to be implementable using a decision assignment tree T of the prescribed complexity. Each
11

time we check the value of x1 ∈ D ′ = D ′ 1 × · · · × D ′ r′ . Thus, we need to read r ′ components.
Depending on the value of x1 , we may apply σj on x2 using the decision assignment tree Tj . Then
we update the value of x1 . Hence, READ(T ) = r ′ + max{READ(Ti )}ki=1 , and WRITE(T ) =
WRITE(T ′ ) + max{WRITE(Ti )}ki=1 .
Let (w1 , w2 · · · , wℓ ) be the cycle of length ℓ given by σ. We now argue that the procedure P
generates a counter of length k′ ℓ over D ′ × D starting at ha1 , w1 i. Without loss of generality, let
us assume that σ = σk′ ◦ · · · ◦ σk+1 ◦ σk ◦ σk−1 ◦ · · · ◦ σ1 , where for j ≥ k + 1, σj is the identity
map. Fix j ∈ [k′ ]. Deﬁne αj = σj−1 ◦ · · · ◦ σ1 , and τj = αj ◦ σ ◦ α−1
j = σj−1 ◦ · · · ◦ σ1 ◦ σk ′ ◦ · · · ◦ σj .
′
′
ik
ik
For i = 0, 1, . . . , ℓ, let hgi , ei i = P (haj , αj (w1 )i) where P denotes ik′ invocations of P . Since
P increments x1 in every invocation, for i = 1, 2, . . . , ℓ, gi = aj and ei = τj (ei−1 ).
By Proposition 4.2, τj is a cycle (αj (w1 )αj (w2 ) · · · αj (wℓ )) of length ℓ. Hence, e1 , . . . , eℓ are
all distinct and eℓ = e0 .
As a consequence we conclude that for any x ∈ D ′ ×D and 1 ≤ j1 6= j2 ≤ k′ ℓ, P j1 (x) 6= P j2 (x)
′
and P k ℓ (x) = x. This completes the proof.
In the next two sections we describe the construction of σ1 , · · · , σk ∈ SN where N = mn for
some m, n ∈ N and how the value of k depends on the length of the cycle σ = σk ◦ σk−1 ◦ · · · ◦ σ1 .

5

Counters via Linear Transformation

The construction in this section is based on linear transformations. Consider the vector space
Fnq , and let L : Fnq → Fnq be a linear transformation. A basic fact in linear algebra says that
if L has full rank, then the mapping given by L is a bijection. Thus, when L is full rank, the
mapping can also be thought of as a permutation over Fnq . Throughout this section we use many
basic terms related to linear transformation without deﬁning them, for the details of which we
refer the reader to any standard text book on linear algebra (e.g. [20]).
A natural way to build counter out of a full rank linear transformation is to ﬁx a starting
element, and repeatedly apply the linear transformation to obtain the next element. Clearly this
only list out elements in the cycle containing the starting element. Therefore, we would like to
choose the starting element such that we enumerate the largest cycle. Ideally, we would like the
largest cycle to contain all the elements of Fnq . However this is not possible because any linear
transformation ﬁxes the all-zero vector. But there do exist full rank linear transformations such
that the permutation given by them is a single cycle of length q n −1. Such a linear transformation
would give us a counter over a domain of size q n that enumerates all but one element. Clearly,
a trivial implementation of the aforementioned argument would lead to a counter that reads
and writes all n coordinates in the worst-case. In the rest of this section, we will develop an
implementation and argue about the choice of linear transformation such that the read and write
complexity decreases exponentially.
We start with recalling some basic facts from linear algebra.
Definition 3 (Linear Transformation). A map L : Fnq → Fnq is called a linear transformation if
L(c · x + y) = cL(x) + L(y), for all x, y ∈ Fnq and c ∈ Fq .
It is well known that every linear transformation L is associated with some matrix A ∈ Fqn×n
such that applying the linear transformation is equivalent to the left multiplication by A. That
is, L(x) = Ax where we interpret x as a column vector. Furthermore, L has full rank iﬀ A is
invertible over Fq .
Definition 4 (Elementary matrices). An n × n matrix over a field F is said to be an elementary
matrix if it has one of the following forms:
12

(a) The off-diagonal entries are all 0. For some i ∈ [n], (i, i)-th entry is a non-zero c ∈ F.
Rest of the diagonal entries are 1. For a fixed i, we denote all matrices of this type by Ei,i .
(See Fig. 1.)
(b) The diagonal entries are all 1. For some i and j, 1 ≤ i 6= j ≤ n, (i, j)-th entry is a
non-zero c ∈ F. Rest of the off-diagonal entries are 0. For each i and j, i 6= j, we denote
all matrices of this type by Ei,j . (See Fig. 1.)

j

i


(a)






i





1

..



.
1
c
1

..

.
1














or,

(b)








i



1

..



.
1
c

..

.
1

..

.
1












Figure 1: Elementary matrices
From the deﬁnition it is easy to see that left multiplication by an elementary matrix of type
Ei,i is equivalent to multiplying the i-th row with c, and by an elementary matrix of type Ei,j
is equivalent to adding c times j-th row to the i-th row.
Proposition 5.1. Let A ∈ Fn×n be invertible. Then A can be written as a product of k elementary matrices such that k ≤ n2 + 4(n − 1).
Proof. Consider the inverse matrix A−1 which is also full rank. It is easily seen from Gauss
elimination that by left multiplying A−1 with at most n2 many elementary matrices, we can
reduce A−1 to a permutation matrix. A permutation matrix is a {0, 1}-matrix that has exactly
one 1 in each row and column. Now we need at most (n − 1) row swaps to further reduce
the obtained permutation matrix to the identity matrix. We claim that a row swap can be
implemented by left multiplication with at most 4 elementary matrices. Indeed, to swap row i
and row j, the following sequence of operation suﬃces: (i) add j-th row to i-th row, (ii) subtract
i-th row from j-th row, (iii) add j-th row to i-th row, and (iv) multiply j-th row with −1. (The
last operation is not required if the characteristic of the underlying ﬁeld is 2.)
Hence, the inverse of A−1 which is our original matrix A is the product of k elementary
matrices.

5.1

Construction of the counter

Let A be a full rank linear transformation from Fnq to Fnq such that when viewed as permutation
n
it is a single cycle of length q n − 1. In other words, A(q −1) = I but for a non-zero j < q n − 1,
Aj 6= I where I is the identity matrix. Furthermore, let A = Ek Ek−1 · · · E1 where Ei ’s are
elementary matrices.
Theorem 5.2. Let q, A, and k be as defined above. Let r ≥ logq k. There exists a quasiGray code on the domain (Fq )n+r of length q n+r − q r that can be implemented using a decision
assignment tree T such that READ(T ) ≤ r + 2 and WRITE(T ) ≤ 2.

13

Proof. The proof follows readily from Lemma 4.3, where Ei ’s play the role of σi ’s, and noting
that the permutation given by any elementary matrix can be implemented using a decision
assignment tree that reads at most two coordinates and writes at most one. For the counter C ′
on (Fq )r we chose a Gray code of trivial read complexity r and write complexity 1.
Thus, we obtain a counter on a domain of size roughly kq n that misses at most qk elements.
Clearly, we would like to minimize k. A trivial bound on k is O(n2 ) that follows from Proposition 5.1. We now discuss the choice of A so that k becomes O(n). We start with recalling a
notion of primitive polynomials over ﬁnite ﬁelds.
Definition 5 (Primitive polynomials). A primitive polynomial p(z) ∈ Fq [z] of degree n is a
monic irreducible polynomial over Fq such that any root of it in Fqn generates the multiplicative
group of Fqn .
Theorem 5.3 ([21]). The number of primitive polynomials of degree n over Fq equals φ(q n −1)/n,
where φ(·) is the Euler φ-function.
Let p(z) be a primitive polynomial of degree n over Fq . The elements of Fqn can be uniquely
expressed as a polynomial in z over Fq of degree at most n − 1. In particular, we can identify an
element of Fqn with a vector in Fnq that is given by the coeﬃcient vector of the unique polynomial
expression of degree at most n − 1. But, since p(z) is primitive, we also know that Fqn =
n
{0, 1, z, z 2 , . . . , z q −2 }. This suggests a particularly nice linear transformation to consider: left
multiplication by z. This is so because the matrix A of the linear transformation computing the
multiplication by z is very sparse. In particular, if p(z) = z n +cn−1 z n−1 +cn−2 z n−2 +· · ·+c1 z+c0 ,
then A looks as follows:


−cn−1 1 0 · · · 0 0 0
−cn−2 0 1 · · · 0 0 0


−cn−3 0 0 · · · 0 0 0


 ..
.. .. . .
.. .. ..  .
 .
. . . .
. .


 −c2 0 0 · · · 0 1 0


 −c1 0 0 · · · 0 0 1
−c0 0 0 · · · 0 0 0

Thus, from the proof of Proposition 5.1, it follows that A can be written as a product of at
most n + 4(n − 1) elementary matrices. (When q is a power of 2, then the number of elementary
matrices in the product is at most n + 3(n − 1).) Hence, from the discussion above and using
Theorem 5.2, we obtain the following corollaries. Setting r = ⌈log(4n − 3)⌉ in Theorem 5.2 gives:
Corollary 5.4. For any n′ ≥ 2, and n = n′ + ⌈log(4n′ − 3)⌉, there exists a counter on (Z2 )n
that misses at most 8n strings and can be implemented by a decision assignment tree that reads
at most 4 + log n bits and writes at most 2 bits.

By doubling the number of missed strings and increasing the number of read bits by one we
can construct given counters for any Zn2 , where n ≥ 15. In the above corollary the number of
missed strings grows linearly with n. One might wonder if it is possible to keep the number of
missing strings o(n), while keeping the read complexity essentially the same. The next corollary
shows that this is indeed possible, but at the cost of increasing the write complexity.
Corollary 5.5. For n ≥ 2, there exists a counter on (Z2 )n+O(log n) that misses out at most
O(n/⌈log n⌉) strings. Furthermore, it can be implemented by a decision assignment tree that
reads and writes at most O(log n) bits.

14

Proof. The idea is simply to increase the underlying alphabet size. In particular, let q = 2⌈log n⌉
in Theorem 5.2.
n

We also remark that by taking q to be 2 C , where C > 1 is a universal constant, one would
get a counter on (Z2 )n+O(1) that misses only O(C) strings (i.e. independent of n). However, the
read and write complexity gets worse. They are at most 2 Cn + O(1).
For the general case, when q is a prime power, we obtain the following corollary by setting
r to ⌈logq (5n − 4)⌉ or 1 + ⌈logq (5n − 4)⌉ in Theorem 5.2.
Corollary 5.6 (Generalization of Theorem 1.2). Let q be any prime power. For n ≥ 15, there
exists a counter on Znq that misses at most 5q 2 n strings and that is computed by a decision
assignment tree with read complexity at most 6 + logq n and write complexity 2.
Remark. We remark that the algorithm given in this section can be made uniform. To achieve
that we need to obtain a primitive polynomial of degree n over Fq uniformly. To this end, we
can use a number of algorithms (deterministic or probabilistic); for example, [30, 33, 31]. For a
thorough treatment, we refer to Chapter 2 in [32].

6

Space-optimal Counters over Znm for any Odd m

This section deals with space-optimal counter over an odd-size alphabet. We start by recalling
Theorem 1.1 in terms of decision assignment tree complexity.
Theorem 6.1 (Restatement of Theorem 1.1). For any odd m ∈ N and n sufficiently large, there
is a space-optimal 2-Gray code over Znm that can be computed by a decision assignment tree T
such that READ(T ) ≤ 4 logm n.
Before providing our construction of the quasi-Gray code, we give a short overview of how
the construction will proceed. First we set n′ = n − c · log n for some constant c > 0 that will
′
be ﬁxed later. Then we deﬁne suitable permutations α1 , . . . , αn′ ∈ SN where N = mn such
′
that their composition αn′ ◦ · · · ◦ α1 is a cycle of length mn . Next we show that each αi can
be further decomposed into αi,1 , . . . , αi,j ∈ SN for some j, such that each αi,r for r ∈ [j] can
be computed using a decision assignment tree with read complexity 3 and write complexity 1.
Finally to complete the construction we use Lemma 4.3 with αi,r ’s playing the role of σ1 , . . . , σk
in the lemma.
We recall the notion of r-functions over Znm that was introduced by Coppersmith and Grossman [8] for m = 2. Below we generalize that deﬁnition for any m ∈ N.
Definition 6. For any r ∈ [n − 1], an r-function on Znm is a permutation τ over Znm identified
by a subset {i1 , . . . , ir , j} ⊆ [n] of size r + 1 and a function f : Zrm → Zm such that for any
ha1 , . . . , an i ∈ Znm ,
τ (ha1 , . . . , an i) = ha1 , . . . , aj−1 , aj + f (ai1 , . . . , air ), aj+1 , . . . , an i.
Observe that any r-function can be implemented using a decision assignment tree T that
queries xi1 , . . . , xir and xj at internal nodes, and at leaves it assigns value only to the variable
xj . Thus, READ(T ) = r + 1 and WRITE(T ) = 1.
Claim 6.2. Any r-function on Znm can be implemented using a decision assignment tree T with
n variables such that READ(T ) = r + 1 and WRITE(T ) = 1.
We are now ready to provide details of our construction of a space-optimal quasi-Gray code
over Znm for any odd m. Deﬁne n′ := n − c · logm n for some constant c > 0 that will be ﬁxed
later.
15

Step 1: Construction of α1 , . . . , αn′ .
′

We consider speciﬁc permutations α1 , . . . , αn′ over Znm such that α = αn′ ◦ · · · ◦ α1 is a cycle of
′
length mn . We deﬁne them below.
Definition 7. Let m and n′ be natural numbers. For i ∈ [n′ ], we define αi to be the permutation
′
given by the following map: for any hx1 , . . . , xi , . . . , xn′ i ∈ Znm ,
(
hx1 , . . . , xi−1 , xi + 1, xi+1 , . . . , xn′ i if xj = 0 for all j ∈ [i − 1],
αi (hx1 , . . . , xi , . . . , xn′ i) =
otherwise.
hx1 , . . . , xi , . . . , xn′ i
The addition operation in the mapping xi ← xi + 1 is within Zm .
The following observation is easily seen from the deﬁnitions of r-functions and αi .
′

Claim 6.3. For any i ∈ [n′ ], αi is an (i − 1)-function on Znm . Furthermore, each αi is composed
′
of disjoint cycles of length m over Znm .
We now establish a crucial property of the αi ’s, i.e., their composition is a full length cycle.
′

Claim 6.4. α = αn′ ◦ · · · ◦ α1 is a cycle of length mn .
Proof. Consider the sequence of permutations τ1 , . . . , τn′ such that τi = αi ◦ αi−1 ◦ · · · ◦ α1 for
i ∈ [n′ ]. Clearly, τn′ = α. We now prove the claim. In fact, we establish the following stronger
′
claim: for i ∈ [n′ ], τi is a permutation composed of mn −i disjoint cycles, each of the cycles
′
being of length mi . Furthermore, for every hai+1 , . . . , an′ i ∈ Znm−i there is a cycle that involves
′
all tuples of the form hx1 , . . . , xi , ai+1 , . . . , an′ i. The claim, α is a cycle of length mn , follows as
a consequence. We prove the stronger claim by induction on i.
Base case: τ1 = α1 . From the deﬁnition of α1 , it follows that there is a cycle of length m of
′
the form (h0, a2 , . . . , an′ i, h1, a2 , . . . , an′ i, . . . , hm − 1, a2 , . . . , an′ i) for each ha2 , . . . , an′ i ∈ Znm−1 .
Hence our induction hypothesis clearly holds for the base case.
Induction Step: Suppose our induction hypothesis holds until some i ∈ [n′ ] and we would
like to establish it for i+1. Let us consider the permutation αi+1 . We know that it is composed of
′
n′ −(i+1)
, αi+1 contains
mn −(i+1) disjoint cycles of length m. Indeed, for each hai+2 , . . . , an′ i ∈ Zm
a cycle that involves all m tuples where the ﬁrst i coordinates are all 0 and the last n′ − (i + 1)
coordinates are set to hai+2 , . . . , an′ i. From the cycle decomposition of αi+1 and τi into disjoint
cycles, it is clear that for any cycle say C in αi+1 there are m disjoint cycles C1 , . . . , Cm in τi ,
each of them intersecting C in exactly one element. Consider C ′ = C ◦CP
1 ◦· · · ◦Cm . By repeated
′
i+1 . (Here
application of Proposition 4.1, we conclude that C is a cycle of length m
i=1 |Ci | = m
′
by |Ci | we mean the length of the cycle Ci .) Also C involves tuples where the last n′ − (i + 1)
n′ −(i+1)
. Thus, C ′ is a cycle of length mi+1
coordinates are set to some ﬁxed hai+2 , . . . , an′ i ∈ Zm
containing all tuples of the form hx1 , . . . , xi+1 , ai+2 , . . . , an′ i. Since τi+1 = αi+1 ◦ τi and αi+1
′
′
contains mn −(i+1) disjoint cycles, we conclude that τi+1 consists of exactly mn −(i+1) disjoint
cycles, each of length mi+1 and containing tuples of the required form.
This ﬁnishes the proof.
Readers may note that this step does not use the fact that m is odd and, thus, it is true
for any m ∈ N. If we were to directly implement αi by a decision assignment tree, its read
complexity would be i. Hence, we would not get any savings in Lemma 4.3. So we need to
further decompose αi into permutations of small read complexity.

16

Step 2: Further decomposition of αi ’s.
Our goal is to describe αi as a composition of 2-functions. Recall, Claim 6.3, each αi is an
′
(i − 1)-function on Znm . Suppose, for i ∈ [n′ ], there exists a set of 2-functions αi,1 , . . . , αi,ki such
that αi = αi,ki ◦ · · · ◦ αi,1 . Then using Lemma 4.3, where αi,k ’s play the role of σj ’s, we obtain
a decision assignment tree implementing a 2-Gray code with potentially low read complexity.
Indeed, each αi,k has lowPread complexity by Claim 6.2, hence the read complexity essentially
depends on how large is i ki . In the following we will argue that αi ’s can be decomposed into
a small set of 2-functions, thus keeping the maximum ki small. As a result, the read complexity
bound in Theorem 6.1 will follow.
Note α1 , α2 and α3 are already 2-functions. In the case of αi , 4 ≤ i ≤ n′ − 2, we can
directly adopt the technique from [2, 5] to generate the desired set of 2-functions. However, as
discussed in Section 1.2, that technique falls short when i > n′ − 2. (It needs two free registers
to operate.) For i = n′ − 1, it is possible to generalize the proof technique of [8] to decompose
αn′ −1 . Unfortunately all the previously known techniques fail to decompose αn′ and we have to
develop a new technique.
First we provide the adaptation of [2, 5], and then develop a new technique that allows us to
express both αn′ −1 and αn′ as a composition of small number of 2-functions, thus overcoming
the challenge described above.
Lemma 6.5. For any 4 ≤ i ≤ n′ − 2, let αi be the permutation given by Definition 7. Then there
exists a set of 2-functions αi,1 , . . . , αi,ki such that αi = αi,ki ◦ · · · ◦ αi,1 , and ki ≤ 4(i − 1)2 − 3.
It is worth noting that, although in this section we consider m to be odd, the above lemma
holds for any m ∈ N. In [2], computation uses only addition and multiplication from the ring,
whereas we can use any function g : Zm → Zm . This subtle diﬀerence makes the lemma to be
true for any m ∈ N instead of being true only for prime powers.
Proof. Pick i ≤ n′ − 2. Let us represent αi as an (i − 1)-function. From the deﬁnition we have,
αi (ha1 , . . . , ai , . . . , an′ i) = ha1 , . . . , ai−1 , ai + f (a1 , . . . , ai−1 ), ai+1 , . . . , an′ i,
where the map f : Zi−1
m → Zm is deﬁned as follows:
(
1 if (a1 , . . . , ai−1 ) = (0, . . . , 0),
f (a1 , . . . , ai−1 ) =
0 otherwise.
Observe that f is an indicator function of a tuple; in particular, of the all-zeroes tuple. To
verify the lemma, we would prove a stronger claim than the statement of the lemma. Consider
the set S of r-functions, 1 ≤ r ≤ n′ − 3, such that the function f used to deﬁne them is
the indicator function of the all-zeroes tuple. That is, τ ∈ S if and only if there exists a set
{i1 , i2 , . . . , ir } ⊆ [n′ ] of size r and a j ∈ [n′ ] \ {i1 , i2 , . . . , ir } such that
τ (ha1 , . . . , an′ i) = ha1 , . . . , aj−1 , aj + f (ai1 , . . . , air ), aj+1 , . . . , an′ i,
where f (x1 , . . . , xr ) = 1 if (x1 , . . . , xr ) = (0, . . . , 0), and 0 otherwise. Observe that αi ∈ S for
4 ≤ i ≤ n′ − 2. We establish the following stronger claim.
Claim 6.6. For an r-function τ ∈ S, there exist 2-functions τ1 , . . . , τkr such that τ = τkr ◦· · ·◦τ1
and kr ≤ 4r 2 − 3. (We stress that τ1 , . . . , τkr need not belong to S.)

17

Clearly, the claim implies the lemma. We now prove the claim by induction on r. The base
case is r ≤ 2, in which case the claim trivially holds. Suppose the claim holds for all (r − 1)functions in S. Let τ ∈ S be an r-function identiﬁed by the set S := {i1 , i2 , . . . , ir } ⊆ [n′ ] and
j ∈ [n′ ] \ S. Since f is an indicator
Q function, it can be expressed as a product of indicator
functions. That is, f (ai1 , . . . , air ) = s∈S g(as ) where g : Zm → Zm is the following {0, 1}-map:
(
1 if y = 0,
g(y) =
0 otherwise.
Consider a partition of S into two sets A and B of sizes ⌊r/2⌋ and ⌈r/2⌉, respectively. Let
j1 and j2 be two distinct integers in [n′ ] \ S ∪ {j}. The existence of such integers is guaranteed
by the bound on r. We now express τ as a composition of (r/2)-functions and 2-functions, and
then use induction hypothesis to complete the proof. The decomposition of τ is motivated by
the following identity:
!
!
Y
Y
Y
aj2 +
g(as ) − aj2
aj +
g(as ) = aj + aj1 +
g(as ) − aj1
s∈S

s∈B

s∈A

= aj +

aj 1 +

Y

!

g(as )

s∈A

−

aj 1 +

Y

s∈A

!

aj 2 +

g(as ) aj2 − aj1

Y

!

g(as )

s∈B

aj2 +

Y

!

g(as )

s∈B

+ aj 1 aj 2 .
′

Therefore, we consider three permutations γ, τA and τB such that for any ha1 , . . . , an′ i ∈ Znm
their maps are given as follows:
γ (ha1 , . . . , an i) = ha1 , . . . , aj−1 , aj + aj1 aj2 , aj+1 , . . . , an′ i,
Q
τA (ha1 , . . . , an′ i) = ha1 , . . . , aj1 −1 , aj1 + s∈A g(as ), aj1 +1 , . . . , an′ i, and
Q
τB (ha1 , . . . , an′ i) = ha1 , . . . , aj2 −1 , aj2 + s∈B g(as ), aj2 +1 , . . . , an′ i,

where both the multiplications and additions are in Zm . Using the identity it is easy to verify
the following decomposition of τ :
τ = τB−1 ◦ γ −1 ◦ τA−1 ◦ γ ◦ τB ◦ γ −1 ◦ τA ◦ γ.
Clearly, γ is a 2-function, while τA and τB are ⌊r/2⌋-function and ⌈r/2⌉-function, respectively,
and belong to S. By induction hypothesis τA and τB can be expressed as a composition of 2functions. Thus their inverses too. Hence we obtain a decomposition of τ in terms of 2-functions.
The bound on kr , the length of the decomposition, follows from the following recurrence:
T (r) ≤ 2T (⌊r/2⌋) + 2T (⌈r/2⌉) + 4.

We would like to mention that another decomposition of τ in terms of 2-functions can be
obtained by following the proof of [8], albeit with a much worse bound on the value of kr .
Further, by strengthening the induction hypothesis, it is easily seen that the above proof can be
generalized to hold for certain special type of r-functions. Let β be an r-function, r ≤ n′ − 3,
′
such that for any ha1 , . . . , an′ i ∈ Znm ,
β (ha1 , . . . , an′ i) = ha1 , . . . , ai−1 , ai + fe (ai1 , . . . , air ), ai+1 , . . . , an′ i,
18

where the function fe : Zrm → Zm is deﬁned by:
(
b if x = e,
fe (x) =
0 otherwise,
for some b ∈ Zm and e ∈ Zrm , i.e., fe is some constant multiple of the characteristic function of
the tuple e. A crucial step in the proof is to express fe as a product of indicator functions. In
this case we consider the following functions gij : Zm → Zm for 1 ≤ j ≤ r. Deﬁne gi1 : Zm → Zm
such that for any y ∈ Zm , gi1 (y) = b if y = e1 , and 0 otherwise. For any 2 ≤ j ≤ r, deﬁne
gij : Zm → Zm as gij (y) = 1 if y = ei , and 0 otherwise. By deﬁnition, we have fe (x1 , . . . , xr ) =
gi1 (x1 )gi2 (x2 ) · · · gir (xr ). Thus we get the following generalization of Lemma 6.5.
Lemma 6.7. For any m ∈ N and 1 ≤ r ≤ n′ − 3, let τ be an r-function such that for any
′
ha1 , . . . , an′ i ∈ Znm ,
τ (ha1 , . . . , an′ i) = ha1 , . . . , aj−1 , aj + fe (ai1 , . . . , air ), aj+1 , . . . , an′ i
where the function fe : Zrm → Zm is defined by: fe (x) = b if x = e; and 0 otherwise. Then there
exists a set of 2-functions τ1 , . . . , τkr such that τ = τkr ◦ · · · ◦ τ1 , and kr ≤ 4r 2 − 3.
Comment on decomposition of general
r-functions for 3 ≤ r ≤ n′ − 3: Any function
P
f : Zrm → Zm can be expressed as f = e ce · χe , where χe is the characteristic function of
the tuple e ∈ Zrm , and ce ∈ Zm . Thus Lemma 6.7 suﬃces to argue that any r-function can be
decomposed into a set of 2-functions. However, the implied bound on kr may not be small. In
particular, the number of tuples where f takes non-zero value might be large.
It remains to decompose αn′ −1 and αn′ . The following lemma about cycles that intersect at
exactly one point serves as a key tool in our decomposition.
Lemma 6.8. Suppose there are two cycles, σ = (t, a1 , · · · , aℓ−1 ) and τ = (t, b1 , · · · , bℓ−1 ), of
length ℓ ≥ 2 such that ai 6= bj for every i, j ∈ [ℓ − 1]. Then, (σ ◦ τ )ℓ ◦ (τ ◦ σ)ℓ = σ 2 .
Proof. By Proposition 4.1, we have
β := τ ◦ σ = (t, a1 , · · · , aℓ−1 , b1 , · · · , bℓ−1 ), and
γ := σ ◦ τ = (t, b1 , · · · , bℓ−1 , a1 , · · · , aℓ−1 ).
Both β and γ are cycles of length 2ℓ − 1. Also note that 2ℓ − 1 is co-prime with ℓ. Thus both
β ℓ and γ ℓ are also cycles of length 2ℓ − 1 given as follow:
β ℓ = (t, b1 , a1 , b2 , a2 , · · · , bℓ−1 , aℓ−1 ), and
γ ℓ = (t, a1 , b1 , a2 , b2 , · · · , aℓ−1 , bℓ−1 ).
Now by Proposition 4.2,
σ ◦ β ℓ ◦ σ −1 = (σ(t), σ(b1 ), σ(a1 ), · · · , σ(aℓ−2 ), σ(bℓ−1 ), σ(aℓ−1 ))
= (a1 , b1 , a2 , b2 , · · · , aℓ−1 , bℓ−1 , t) = γ ℓ .
Therefore,
β ℓ ◦ σ −1 = (t, aℓ−1 , aℓ−2 , · · · , a1 ) ◦ (t, a1 , b1 , a2 , b2 , · · · , aℓ−1 , bℓ−1 )
= (a1 , b1 )(a2 , b2 ) · · · (aℓ−1 , bℓ−1 ).
19

It is thus evident that β ℓ ◦ σ −1

2

is the identity permutation. Hence,

γ ℓ ◦ β ℓ = σ ◦ β ℓ ◦ σ −1 ◦ β ℓ
= σ ◦ β ℓ ◦ σ −1 ◦ β ℓ ◦ σ −1 ◦ σ
= σ2 .

Before going into the detailed description of the decomposition procedure, let us brieﬂy
discuss the main idea. Here we ﬁrst consider αn′ . The case of αn′ −1 will be analogous. Recall
that αn′ = (h00 · · · 00i, h00 · · · 01i, h00 · · · 02i, · · · , h00 · · · 0(m−1)i) is a cycle of length m. For a =
(m+1)/2, we deﬁne σ = (h00 · · · 0(0·a)i, h00 · · · 0(1·a)i, h00 · · · 0(2·a)i, · · · , h00 · · · 0((m−1)·a)i),
and τ = (h(0 · a)00 · · · 0i, h(1 · a)00 · · · 0i, h(2 · a)00 · · · 0i, · · · , h((m − 1) · a)00 · · · 0i), where the
multiplication is in Zm . Since m is co-prime with (m + 1)/2, σ and τ are cycles of length m.
(Here we use the fact that m is odd.) Observe that σ 2 = αn′ , so by applying Lemma 6.8 to
σ and τ we get αn′ . It might seem we didn’t make much progress towards decomposition, as
now instead of one (n′ − 1)-function αn′ we have to decompose two (n′ − 1)-functions σ and
τ . However, we will not decompose σ and τ directly, but rather we obtain a decomposition for
(σ ◦ τ )m and (τ ◦ σ)m . Surprisingly this can be done using Lemma 6.7 although indirectly.
We consider an (n′ − 3)-function σ ′ whose cycle decomposition contains σ as one of its cycles.
Similarly we consider a 3-function τ ′ whose cycle decomposition contains τ as one of its cycles.
We carefully choose these σ ′ and τ ′ such that (σ ′ ◦ τ ′ )m = (σ ◦ τ )m and (τ ′ ◦ σ ′ )m = (τ ◦ σ)m .
We will use Lemma 6.7 to directly decompose σ ′ and τ ′ to get the desired decomposition.
′

Lemma 6.9. For any n′ − 1 ≤ i ≤ n′ , let αi be the permutation over Znm given by Definition 7
where m is odd. Then, there exists a set of 2-functions αi,1 , . . . , αi,ki such that αi = αi,ki ◦· · ·◦αi,1 ,
and ki = O(m · (i − 1)2 ).
Proof. For the sake of brevity, we will only describe the procedure to decompose αn′ into a set
of 2-functions. The decomposition of αn′ −1 is completely analogous. (We comment on this more
at the end of the proof.)
′
Let σ be the following permutation: for any ha1 , . . . , an′ i ∈ Znm ,
σ (ha1 , . . . , an′ i) = ha1 , . . . , an′ −1 , an′ + f (a1 , . . . , an′ −1 )i
′

where the function f : Znm−1 → Zm is deﬁned as follows:
(
(m + 1)/2 if x = h0, . . . , 0i,
f (x) =
0
otherwise.
Note that (m + 1)/2 is well deﬁned because m is odd. Further, since m and (m + 1)/2 are
co-prime, σ is a m length cycle. Moreover, σ 2 = αn′ . The description of σ uses crucially that
m is odd. If m were not odd, then the description fails. Indeed ﬁnding a substitute for σ is the
main hurdle that needs to be addressed to handle the case when m is even.
′
We also consider another permutation τ such that for any ha1 , . . . , an′ i ∈ Znm ,
τ (ha1 , . . . , an′ i) = ha1 + f (a2 , . . . , an′ ), a2 , . . . , an′ i
where the function f is the same as in the deﬁnition of σ. So τ is also a cycle of length m. Let
t = (m + 1)/2. Then the cycle decomposition of σ and τ are,
σ = (h0, 0, . . . , 0, 0 · ti, h0, 0, . . . , 0, 1 · ti, h0, 0, . . . , 0, 2 · ti, · · · , h0, 0, . . . , 0, (m − 1) · ti) , and
τ = (h0 · t, 0, 0, . . . , 0i, h1 · t, 0, 0, . . . , 0i, h2 · t, 0, 0, . . . , 0i, · · · , h(m − 1) · t, 0, 0, . . . , 0i)
20

where the multiplication is in Zm . Observe that h0, . . . , 0i is the only common element involved
in both cycles σ and τ . Therefore, by Lemma 6.8,
(σ ◦ τ )m ◦ (τ ◦ σ)m = σ 2 = αn′ .
We note that both σ and τ are (n′ − 1)-functions. Thus so far it is not clear how the above
identity helps us to decompose αn′ . We now deﬁne two more permutations σ ′ and τ ′ such that
they are themselves decomposable into 2-functions and, moreover, (σ ′ ◦ τ ′ )m = (σ ◦ τ )m and
(τ ′ ◦ σ ′ )m = (τ ◦ σ)m .
′
The permutations σ ′ and τ ′ are deﬁned as follows: for any ha1 , . . . , an′ i ∈ Znm ,
σ ′ (ha1 , . . . , an′ i) = ha1 , . . . , an′ −1 , an′ + g(a1 , . . . , an′ −3 )i, and
τ ′ (ha1 , . . . , an′ i) = ha1 + h(an′ −2 , an′ −1 , an′ ), a2 , . . . , an′ i
′

n −3 → Z is the following map:
where g : Zm
m
(
(m + 1)/2
g(x) =
0

if x = h0, . . . , 0i,
otherwise,

and h : Z3m → Zm is similarly deﬁned but on lower dimension:
(
(m + 1)/2 if x = h0, 0, 0i,
h(x) =
0
otherwise.
Since m and (m + 1)/2 are co-prime, σ ′ is composed of m2 disjoint cycles, each of length m.
′
Similarly, τ ′ is composed of m(n −4) disjoint cycles, each of length m. Moreover, σ is one of the
′
cycles among m2 disjoint cycles of σ ′ and τ is one of the cycles among m(n −4) disjoint cycles of
τ ′ . So, we can write
σ ′ = σ ◦ C1 ◦ · · · ◦ Cm2 −1 , and
′
τ ′ = τ ◦ C1′ ◦ · · · ◦ Cm
(n′ −4) −1

where each of Ci ’s and Cj′ ’s is a m length cycle. An important fact regarding σ ′ and τ ′ is that
the only element moved by both is the all-zeros tuple h0, . . . , 0i. This is easily seen from their
deﬁnitions. Recall we had observed that the all-zeroes is, in fact, moved by σ and τ . In other
′
words, cycles in the set {C1 , . . . , Cm2 −1 , C1′ , . . . , Cm
(n′ −4) −1 } are mutually disjoint, as well as
they are disjoint from σ and τ . Thus, using the fact that Ci ’s and Cj′ ’s are m length cycles, we
have
(τ ′ ◦ σ ′ )m = (τ ◦ σ)m , and
(σ ′ ◦ τ ′ )m = (σ ◦ τ )m .
Therefore, we can express αn′ in terms of σ ′ and τ ′ ,
αn′ = σ 2 = (σ ◦ τ )m ◦ (τ ◦ σ)m = (σ ′ ◦ τ ′ )m ◦ (τ ′ ◦ σ ′ )m .
But, by deﬁnition, σ ′ and τ ′ are an (n′ −3)-function and a 3-function, respectively. Furthermore,
they satisfy the requirement of Lemma 6.7. Hence both σ ′ and τ ′ can be decomposed into a set
of 2-functions. As a result we obtain a decomposition
of αn′ into a set of kn′ many 2-functions,

′
2
2
′
′
where kn ≤ 2m 4(n − 3) − 3 + 4 · 3 − 3 = m 8(n − 3)2 + 60 ≤ 60 · m (n′ − 3)2 .
21

The permutation αn′ −1 can be decomposed in a similar fashion. Note that αn′ −1 is composed
of m disjoint m length cycles. Each of the m disjoint cycles can be decomposed using the
procedure described above. If we do so, we get the length kn′ −1 = O(m2 · (n′ − 3)2 ), which
would suﬃce for our purpose. However, we can improve this bound to O(m · (n′ − 2)2 ) by a
slight modiﬁcation of σ, τ, σ ′ and τ ′ . Below we deﬁne these permutations and leave the rest of
the proof to the reader as it is analogous to the proof above. The argument should be carried
′
with σ, τ, σ ′ and τ ′ deﬁned as follows: for any ha1 , . . . , an′ i ∈ Znm ,
σ (ha1 , . . . , an′ i) = ha1 , . . . , an′ −2 , an′ −1 + f (a1 , . . . , an′ −2 ), an′ i,
τ (ha1 , . . . , an′ i) = ha1 + f (a2 , . . . , an′ −1 ), . . . , an′ −1 , an′ i,
σ ′ (ha1 , . . . , an′ i) = ha1 , . . . , an′ −2 , an′ −1 + g(a1 , . . . , an′ −3 ), an′ i, and
τ ′ (ha1 , . . . , an′ i) = ha1 + h(an′ −2 , an′ −1 ), a2 , . . . , an′ −1 , an′ i,

′

n −2 → Z is deﬁned as: f (x) = (m + 1)/2 if x = h0, . . . , 0i; otherwise
where the function f : Zm
m
′
f (x) = 0, the function g : Znm−3 → Zm is deﬁned as: g(x) = (m+1)/2 if x = h0, . . . , 0i; otherwise
g(x) = 0 and the function h : Z2m → Zm is deﬁned as: h(x) = (m + 1)/2 if x = h0, 0i; otherwise
h(x) = 0. The only diﬀerence is now that both σ and τ are composed of m disjoint cycles of
length m, instead of just one cycle as in case of αn′ . However every cycle of σ has non-empty
intersection with exactly one cycle of τ , and furthermore, the intersection is singleton. Hence
we can still apply Lemma 6.8 with m pairs of m length cycles, where each pair consists of one
cycle from σ and another from τ such that they have non-empty intersection.

Step 3: Invocation of Lemma 4.3
To ﬁnish the construction we just replace αi ’s in α = αn′ ◦ · · · ◦ α1 by αi,ki ◦ · · · ◦ αi,1 . Take
P ′
the resulting sequence as σ = σk ◦ · · · ◦ σ1 , where k = ni=1 ki ≤ c3 · m · n′3 for some constant
c3 > 0. Now we apply Lemma 4.3 to get a space-optimal counter over Znm . In Lemma 4.3, we
′
′
′
set k′ = mr such that r ′ is the smallest integer for which mr ≥ k and set D ′ = Zrm . Hence
r ′ ≤ logm k + 1 ≤ 3 logm n + c, for some constant c > 1. Since each of σi ’s is a 2-function, by
Claim 6.2 it can be implemented using a decision assignment tree Ti such that READ(Ti ) = 3
and WRITE(Ti ) = 1. In Lemma 4.3, we use the standard space-optimal Gray code over
′
D ′ = Zrm as C ′ . The code C ′ can be implemented using a decision assignment tree T ′ with
READ(T ′ ) = r ′ and WRITE(T ′ ) = 1 (Theorem 2.1). Hence the ﬁnal counter implied from
Lemma 4.3 can be computed using a decision assignment tree T with READ(T ) ≤ 4 logm n and
WRITE(T ) = 2.
Are odd permutations the bottleneck? We saw our decomposition procedure over Znm
into 2-functions (Lemma 6.9) requires that m be odd. It is natural to wonder whether such a
decomposition exists irrespective of the parity of m. That is, we would like to design a set of
2-functions that generates a cycle of length mn where m is even. Unfortunately, the answer
to this question is, unequivocally, NO. A cycle of length mn is an odd permutation when m is
even. However, Coppersmith and Grossman [8] showed that 2-functions are even permutations
for m = 2. Their proof is easily seen to be extended to hold for all m. Hence, 2-functions can
only generate even permutations. Thus, ruling out the possibility of decomposing a full cycle
into 2-functions when m is even. In fact, Coppersmith and Grossman [8] showed that (n − 2)functions are all even permutations. Therefore, the decomposition remains impossible even if
(n − 2)-functions are allowed.

22

We would like to give further evidence that odd permutations are indeed the bottleneck
towards obtaining an eﬃcient decision assignment tree implementing a space-optimal counter
over Zn2 . Suppose T is a decision assignment tree that implements an odd permutation σ over
Zn2 such that READ(T ) = r and WRITE(T ) = w. From the basic group theory we know that
there exists an even permutation τ such that τ ◦σ is a cycle of length 2n . Following the argument
in [8], but using an eﬃcient decomposition of (n − 3)-functions into 2-functions (in particular,
Lemma 6.7), we see that any even permutation can be decomposed into a set of 2-functions of
size at most O(2n−1 n2 ). Indeed, any even permutation can be expressed as a composition of
at most 2n−1 3-cycles, while any 3-cycle can be decomposed into at most O(n2 ) 2-functions.
2n+O(log n)
We implement τ ◦ σ using Lemma 4.3 to obtain a space-optimal counter over Z2
that
is computed by a decision assignment tree with read complexity n + O(log n) + r and write
complexity w + 1. Thus, savings made on implementing an odd permutation translate directly
to the savings possible in the implementation of some space-optimal counter.
Recall the main idea behind 2-Gray codes in Section 5, when m = 2, is to generate the cycle
of length 2n − 1 eﬃciently. Since a cycle of length 2n − 1 is an even permutation, we could
decompose it into 2-functions. In particular, we could choose an appropriate 3-cycle as αn in
Claim 6.4 such that α becomes a cycle of length 2n − 1. However, the counter thus obtained
misses out on O(n3 ) strings, instead of O(n).

6.1

Getting counters for even m

We can combine the results from Theorem 1.2 and Theorem 1.1 to get a counter over Znm for
any even m. We have already mentioned in Section 3 that if we have space-optimal quasiGray codes over the alphabet Z2 and Zo with o being odd then we can get a space-optimal
quasi-Gray code over the alphabet Zm for any even m. Unfortunately in Section 5, instead of
space-optimal counters we were only able to generate a counter over binary alphabet that misses
O(n) many strings. As a consequence we cannot directly apply Theorem 3.1. The problem is
following. Suppose m = 2ℓ o for some ℓ > 0 and odd o. By the argument used in the proof
of Lemma 3.3 we know that there is a counter over (Z2ℓ )n−1 of the same length as that over
′
(Z2 )ℓ(n−1) . Furthermore the length of the counter is of the form 2O(log n) (2n − 1), for some n′
that depends on the value of ℓn (see the construction in Section 5). Now to apply Theorem 3.1 as
′
in the proof of Lemma 3.2, 2n − 1 must be co-prime with o. However that may not always be the
case. Nevertheless, we can choose the parameters in the construction given in Section 5 to make
′
n′ such that 2n − 1 is co-prime with o. This is always possible because of the following simple
algebraic fact. In the following proposition we use the notation Z∗o to denote the multiplicative
group modulo o and ordo (e) to denote the order of any element e ∈ Z∗o .
Proposition 6.10. For any n ∈ N and odd o ∈ N, consider the set S = {n, n + 1, · · · , n +
′
ordo (2) − 1}. Then there always exists an element n′ ∈ S such that 2n − 1 is co-prime to o.
Proof. Inside Z∗o , consider the cyclic subgroup G generated by 2, i.e., G = {1, 2, · · · , 2ordo (2) }.
′
Clearly, {2s (mod o) | s ∈ S} = G. Hence there exists an element n′ ∈ S such that 2n − 1
′
(mod o) = 1. It is clear that if gcd(2n − 1, o) = 1 then we are done. Now the proposition
follows from the following easily veriﬁable fact: for any a, b, c ∈ N, if a ≡ b (mod c) then
gcd(a, c) = gcd(b, c).
So for any n ∈ N, in the proof of Lemma 3.2 we take the ﬁrst coordinate to be Zim for
some suitably chosen i ≥ 1 instead of just Zm . The choice of i will be such that the length of
the counter over (Z2ℓ )n−i will become co-prime with o. The above proposition guarantees the
existence of such an i ∈ [ordo (2)]. Hence we can conclude the following.

23

Theorem 6.11. For any even m ∈ N so that m = 2ℓ o where o is odd, there is a quasi-Gray code
C over Znm of length at least mn − O(non ), that can be implemented using a decision assignment
tree which reads at most O(logm n + ordo (2)) coordinates and writes at most 3 coordinates.
Remark. So far we have only talked about implementing next(·, ·) function for any counter.
However we can similarly define complexity of computing prev(·, ·) function in the decision assignment tree model. We would like to emphasize that all our techniques can also be carried over
to do that. To extend the result of Section 5, we take the inverse of the linear transformation
matrix A and follow exactly the same proof to get the implementation of prev(·, ·). As a consequence we achieve exactly the same bound on read and write complexity. Now for the quasi-Gray
code over Zm for any odd m, instead of α in the Step 1 (in Section 6), we simply consider the
−1
−1
α−1 which is equal to α−1
1 ◦ α2 ◦ · · · ◦ αn′ . Then we follow an analogous technique to decompose
α−1
i ’s and finally invoke Lemma 4.3. Thus we get the same bound on read and write complexity.

7

Lower Bound Results for Hierarchical Counter

We have mentioned that the best known lower bound on the depth of a decision assignment tree
implementing any space-optimal quasi-Gray code is Ω(logm n). Suppose we are interested in
getting a space-optimal quasi-Gray code over the domain Zm1 ×· · ·×Zmn . A natural approach to
achieve the O(log n) bound is to build a decision assignment tree with an additional restriction
that a variable labels exactly one internal node. We call any counter associated with such a
special type of decision assignment tree by hierarchical counter. We note that the aforementioned
restriction doesn’t guarantee an O(log n) bound on the depth; for example, a decision assignment
tree implementing a counter that increments by 1 to obtain the next element, reads a variable
exactly once. Nevertheless, informally, one can argue that if a hierarchical counter is lopsided it
must mimic the decision assignment tree in the previous example. We show that a space-optimal
hierarchical counter over strings of length 3 exists if and only if m2 and m3 are co-prime.
Theorem 7.1. Let m1 ∈ {2, 3} and m2 , m3 ≥ 2. There is no space-optimal hierarchical counter
over Zm1 × Zm2 × Zm3 unless m2 and m3 are co-prime.
In fact, we conjecture that the above theorem holds for all m1 ≥ 2.
Conjecture 1. There is no space-optimal hierarchical counter over Zm1 × Zm2 × Zm3 unless m2
and m3 are co-prime.
It follows already from Theorem 3.1 that a space-optimal hierarchical counter exists when
m2 and m3 are co-prime. Hence Theorem 7.1 establishes the necessity of co-primality in Theorem 3.1. It also provides a theoretical explanation behind the already known fact, derived from
an exhaustive search in [4], that there exists no space-optimal counter over (Z2 )3 that reads at
most 2 bits to generate the next element.
Proof of Theorem 7.1. We ﬁrst establish the proof when m1 = 2, and then reduce the case when
m1 = 3 to m1 = 2.
Following the deﬁnition of hierarchical counter, without loss of generality, we assume that
it reads the second coordinate if the value of the ﬁrst coordinate is 0; otherwise it reads the
third coordinate. Let C = (ha0 , b0 , c0 i, . . . , hak−1 , bk−1 , ck−1 i) be the cyclic sequence associated
with a space-optimal hierarchical counter over Z2 × Zm2 × Zm3 . We claim that for any two
consecutive elements in the sequence, hai , bi , ci i and ha(i+1) mod k , b(i+1) mod k , c(i+1) mod k i, the
following must hold:

24

1. If ai = 0, then bi+1 6= bi . For the sake of contradiction suppose not, i.e, bi+1 = bi . Since
ai = 0 we do not read the third coordinate, thus, implying ci+1 = ci . Hence, ai 6= ai+1 = 1.
Therefore, we observe that the second coordinate never changes henceforth. Thence it must
be that b1 = b2 = · · · = bk . We thus contradict space-optimality. Similarly, we can argue
if ai = 1, then ci+1 6= ci .
2. For i ∈ {0, 1, . . . , k − 1}, a(i+1) mod k 6= ai . Assume otherwise. Let i ∈ {0} ∪ [k − 1] be
such that a(i−1) mod k 6= ai = a(i+1) mod k . Clearly, such an i exists, else a1 = a2 = · · · = ak
which contradicts space-optimality. We are now going to argue that there exist two distinct
elements in the domain Z2 × Zm2 × Zm3 such that they have the same successor in C, thus
contradicting that C is generated by a space-optimal counter. For the sake of simplicity
let us assume ai = 0. The other case is similar. Since ai = 0, we have ai−1 = 1 and
ai+1 = 0. Thus, we have the tuple h0, bi+1 , ci+1 i following the tuple h0, bi , ci i in C. We
claim that the successor of the tuple h1, bi+1 , ci−1 i is also h0, bi+1 , ci+1 i. It is easily seen
because ci+1 = ci .
The second item above says that the period of each element in the ﬁrst coordinate is 2. That
is, in the sequence C the value in the ﬁrst coordinate repeats every second step. We will now
argue that the value in the second coordinate (respectively, third coordinate) repeats every 2m2
steps (respectively, 2m3 steps). We will only establish the claim for the second coordinate, as
the argument for the third coordinate is similar. First of all observe that C induces a cycle on
the elements of Zm2 . In particular, Consider the sequence b0 , b2 , b4 , . . . , bℓ such that bℓ is the ﬁrst
time when an element in the sequence has appeared twice. First of all, for C to be a valid cycle
bℓ must be equal to b0 . Secondly, b0 , b2 , . . . , bℓ−2 are the only distinct elements that appear in the
second coordinate throughout C. This is because the change in the second coordinate depends,
deterministically, on what value it holds prior to the change. Thus, for C to be space-optimal
ℓ/2 must be equal to m2 . Hence, an element in the second coordinate repeats every 2m2 steps
in C.
Therefore, for the cyclic sequence C, we get that k = lcm(2m2 , 2m3 ) = 2m2 m3 / gcd(m2 , m3 ).
Hence if m2 and m3 are not co-prime then k < 2m2 m3 implying C to be not space-optimal.
We now proceed to the case m1 = 3. As mentioned in the beginning, we will show that
from any space-optimal hierarchical counter over Z3 × Zm2 × Zm3 we can obtain a space-optimal
hierarchical counter over Z2 × Zm2 × Zm3 .
Let C = (ha0 , b0 , c0 i, . . . , hak−1 , bk−1 , ck−1 i) be the cyclic sequence associated with a spaceoptimal hierarchical counter T over Z3 × Zm2 × Zm3 . We query the ﬁrst coordinate, say x1 , at
the root of T . Let T0 , T1 , and T2 be the three subtrees rooted at x1 = 0, 1, and 2, respectively.
Without loss of generality, we assume that the roots of T0 and T2 are labeled by the second
coordinate, say x2 , and the root of T1 is labeled by the third coordinate, say x3 . We say that
there is a transition from Ti to Tj if there exists a leaf in Ti labeled with an instruction to change
x1 to j. We will use the shorthand Ti → Tj to denote this fact. For C to be space-optimal
there must be a transition from T1 to either T0 or T2 or both. We now observe some structural
properties of T . We ﬁrst assume that there is a transition from T1 to T0 . (The other case when
there is a transition from T0 to T2 will be dual to this.)
(i) If T1 → T0 , then T2 6→ T0 . Suppose not, and let h2, x2 , ∗i goes to h0, x′2 , ∗i. Since T1 → T0 ,
we have h1, ∗, x3 i goes to h0, ∗, x′3 i. It is easily seen that both h2, x2 , x′3 i and h1, x′2 , x3 i
have the same successor in C which is h0, x′2 , x′3 i. (Notice similarly we could also argue
that if T1 → T2 , then T0 6→ T2 .).
(ii) If T1 → T0 , then T1 6→ T2 . Suppose not, then from item (i) we know that T2 6→ T0 and
T0 6→ T2 . Thus, in the sequence C two tuples with ﬁrst coordinate 0 or 2 is separated by
25

a tuple with the ﬁrst coordinate 1. Since there are exactly equal number of tuples with a
ﬁxed ﬁrst coordinate, C can not be space-optimal.
(iii) If T1 → T0 , then T0 6→ T0 and T1 6→ T1 . The argument is similar to item (i).
We now prune T to obtain a space-optimal hierarchical counter T ′ over Z2 × Zm2 × Zm3 as
follows. We ﬁrst remove the whole subtree T2 , i.e., only T0 and T1 remain incident on x1 . We
don’t make any change to T1 . Now we change instructions at the leaves in T0 to complete the
construction of T ′ . Let ℓ be a leaf in T0 such that it is labeled with the assignment: x1 ← 2
and x2 ← b for some b ∈ Zm2 . As a thought experiment, let us traverse T2 in T until we reach
a leaf in T2 with assignments of the form x1 ← 1 and x2 ← b′ for some b′ ∈ Zm2 . In this
case, we change the content of the leaf ℓ in T0 in T ′ to x1 ← 1 and x2 ← b′ . The fact that
T ′ is space-optimal and hierarchical follows easily from properties (i) - (iii) of T , and it being
space-optimal and hierarchical. This completes the proof.

Acknowledgments
Authors would like to thank Gerth Stølting Brodal for bringing the problem to our attention,
and to Petr Gregor for giving a talk on space-optimal counters in our seminar, which motivated
this research.

References
[1] David A. Mix Barrington. Bounded-width polynomial-size branching programs recognize
exactly those languages in N C 1 . Journal of Computer and System Sciences, 38:150–164,
1989.
[2] Michael Ben-Or and Richard Cleve.
Computing algebraic formulas using a constant number of registers.
SIAM J. Comput., 21(1):54–58, 1992.
URL:
https://doi.org/10.1137/0221006, doi:10.1137/0221006.
[3] Prosenjit Bose, Paz Carmi, Dana Jansens, Anil Maheshwari, Pat Morin, and
Michiel H. M. Smid.
Improved methods for generating quasi-gray codes.
In Algorithm Theory - SWAT 2010, 12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, June 21-23, 2010. Proceedings,
pages 224–235, 2010.
URL: https://doi.org/10.1007/978-3-642-13731-0_22,
doi:10.1007/978-3-642-13731-0_22.
[4] Gerth Stølting Brodal, Mark Greve, Vineet Pandey, and Srinivasa Rao Satti. Integer representations towards eﬃcient counting in the bit probe model.
J. Discrete Algorithms, 26:34–44, 2014. URL: https://doi.org/10.1016/j.jda.2013.11.001,
doi:10.1016/j.jda.2013.11.001.
[5] Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loﬀ, and Florian Speelman. Computing with a full memory: catalytic space. In Symposium on Theory of Computing,
STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 857–866, 2014. URL:
http://doi.acm.org/10.1145/2591796.2591874, doi:10.1145/2591796.2591874.
[6] Richard Cleve. Methodologies for Designing Block Ciphers and Cryptographic Protocols.
PhD thesis, University of Toronto, April 1989.
[7] Martin Cohn. Aﬃne m-ary gray codes. Information and Control, 6(1):70–78, 1963.
26

[8] Don Coppersmith and Edna Grossman. Generators for certain alternating groups with
applications to cryptography. j-SIAM-J-APPL-MATH, 29(4):624–627, December 1975.
[9] C. Ding, D. Pei, and A. Salomaa. Chinese Remainder Theorem: Applications in Computing,
Coding, Cryptography. World Scientiﬁc Publishing Co., Inc., River Edge, NJ, USA, 1996.
[10] David S. Dummit and Richard M. Foote. Abstract Algebra. John Wiley & Sons, 2004.
[11] Tomáš Dvořák, Petr Gregor, and Václav Koubek.
Generalized gray codes
with prescribed ends.
Theor. Comput. Sci., 668:70–94, 2017.
URL:
https://doi.org/10.1016/j.tcs.2017.01.010, doi:10.1016/j.tcs.2017.01.010.
[12] Ivan Flores. Reﬂected number systems. IRE Transactions on Electronic Computers, EC5(2):79–82, 1956.
[13] Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, and Sven Skyum. Dynamic word problems. J. ACM, 44(2):257–271, 1997. URL: http://doi.acm.org/10.1145/256303.256309,
doi:10.1145/256303.256309.
[14] Michael L. Fredman. Observations on the complexity of generating quasi-gray codes.
SIAM J. Comput., 7(2):134–146, 1978.
URL: https://doi.org/10.1137/0207012,
doi:10.1137/0207012.
[15] Zachary Frenette. Towards the eﬃcient generation of gray codes in the bitprobe model.
Master’s thesis, University of Waterloo, Waterloo, Ontario, Canada, 2016.
[16] F. Gray.
Pulse code communication, 1953.
http://www.google.com/patents/US2632058.

US Patent 2,632,058.

URL:

[17] Petr Gregor and Torsten Mütze. Trimming and gluing gray codes. In 34th Symposium on
Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, pages 40:1–40:14, 2017. URL: https://doi.org/10.4230/LIPIcs.STACS.2017.40,
doi:10.4230/LIPIcs.STACS.2017.40.
[18] James T. Joichi, Dennis E. White, and S. G. Williamson. Combinatorial gray codes.
SIAM J. Comput., 9(1):130–141, 1980.
URL: https://doi.org/10.1137/0209013,
doi:10.1137/0209013.
[19] Donald E. Knuth. The Art of Computer Programming, Volume 4, Fascicle 2: Generating All
Tuples and Permutations (Art of Computer Programming). Addison-Wesley Professional,
2005.
[20] Serge Lang. Linear Algebra. Undergraduate Texts in Mathematics. Springer New York,
1987.
[21] Rudolf Lidl and Harald Niederreiter. Finite Fields. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2 edition, 1996. doi:10.1017/CBO9780511525926.
[22] H. M. Lucal. Arithmetic operations for digital computers using a modiﬁed reﬂected binary
code. IRE Transactions on Electronic Computers, EC-8(4):449–458, 1959.
[23] Torsten Mütze. Proof of the middle levels conjecture. Proceedings of the London Mathematical Society, 112(4):677–713, 2016.

27

[24] Torsten Mütze and Jerri Nummenpalo. Eﬃcient computation of middle levels gray codes.
In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September
14-16, 2015, Proceedings, pages 915–927, 2015.
[25] Torsten Mütze and Jerri Nummenpalo. A constant-time algorithm for middle levels gray
codes. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete
Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2238–
2253, 2017.
[26] Patrick K. Nicholson, Venkatesh Raman, and S. Srinivasa Rao. A survey of data
structures in the bitprobe model. In Space-Efficient Data Structures, Streams, and
Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, pages 303–318, 2013. URL: https://doi.org/10.1007/978-3-642-40273-9_19,
doi:10.1007/978-3-642-40273-9_19.
[27] M. Ziaur Rahman and J. Ian Munro.
Integer representation and counting in the bit probe model.
Algorithmica, 56(1):105–127, 2010.
URL:
https://doi.org/10.1007/s00453-008-9247-2, doi:10.1007/s00453-008-9247-2.
[28] Dana S. Richards.
Data compression and gray-code sorting.
Inf. Process.
Lett., 22(4):201–205, 1986. URL: https://doi.org/10.1016/0020-0190(86)90029-3,
doi:10.1016/0020-0190(86)90029-3.
[29] Carla Savage. A survey of combinatorial gray codes. SIAM review, 39(4):605–629, 1997.
[30] Victor Shoup. Searching for primitive roots in ﬁnite ﬁelds. Mathematics of Computation,
58:369 – 380, 1992.
[31] Igor Shparlinski. On ﬁnding primitive roots in ﬁnite ﬁelds. Theoretical Computer Science,
157(2):273 – 275, 1996.
[32] Igor Shparlinski. Finite Fields: Theory and Computation, volume 477 of Mathematics and
its Applications. Springer Netherlands, 1999.
[33] Igor E. Shparlinski. Finding irreducible and primitive polynomials. Applicable Algebra in
Engineering, Communication and Computing, 4(4):263–268, 1993.
[34] Andrew Chi-Chih Yao. Should tables be sorted? J. ACM, 28(3):615–628, 1981. URL:
http://doi.acm.org/10.1145/322261.322274, doi:10.1145/322261.322274.

28

