Bounds on the Zero-Error List-Decoding Capacity
of the q/(q − 1) Channel
Siddharth Bhandari and Jaikumar Radhakrishnan

arXiv:1802.08396v1 [] 23 Feb 2018

Tata Institute of Fundamental Research
Homi Bhabha Road
Mumbai 400005, INDIA
Email: {siddharth.bhandari, jaikumar}@tifr.res.in

Abstract—We consider the problem of determining the zero-error
list-decoding capacity of the q/(q − 1) channel studied by Elias
(1988). The q/(q − 1) channel has input and output alphabet
consisting of q symbols, say, X = {x1 , x2 , . . . , xq }; when the
channel receives an input x ∈ X , it outputs a symbol other than
x itself. Let n(m, q, ℓ) be the smallest n for which there is a code
C ⊆ X n of m elements such that for every list w1 , w2 , . . . , wℓ+1
of distinct code-words from C, there is a coordinate j ∈ [n]
that satisfies {w1 [j], w2 [j], . . . , wℓ+1 [j]} = X . We show that for
ǫ < 1/6, for all large q and large enough m, n(m, q, ǫq ln q) ≥
Ω(exp (q 1−6ǫ /8) log2 m).
The lower bound obtained by Fredman and Komlós (1984) for
perfect hashing implies that n(m, q, q − 1) = exp(Ω(q)) log 2 m;
similarly, the lower bound obtained by Körner (1986) for nearlyperfect hashing implies that n(m, q, q) = exp(Ω(q)) log2 m.
These results show that the zero-error list-decoding capacity of
the q/(q − 1) channel with lists of size at most q is exponentially
small. Extending these bounds, Chakraborty et al. (2006) showed
that the capacity remains exponentially small even if the list size
is allowed to be as large as 1.58q. Our result implies that the
zero-error list-decoding capacity of the q/(q −1) channel with list
size ǫq for ǫ < 1/6 is exp (Ω(q 1−6ǫ )). This resolves the conjecture
raised by Chakraborty et al. (2006) about the zero-error listdecoding capcity of the q/(q − 1) channel at larger list sizes.

I. I NTRODUCTION
We study the zero-error-list-decoding capacity of the q/(q −1)
channel. The input and output alphabet of this channel are
a set of q symbols, namely X = {x1 , x2 , . . . , xq }; when the
symbol x ∈ X is input, the output symbol can be anything
other than x itself. We wish to design good error correcting
codes for such a channel. For the q/(q − 1) channel it is
impossible to recover the message without error if the code
has at least two code-words: in fact, no matter how many
letters are used for encoding, for every set of up to (q − 1)
input code-words, one can construct an output word that
is compatible with all of them. It is, however, possible to
design codes where on receiving an output word from the
channel, one can narrow down the input message to a set of
size at most (q − 1)—that is, we can list-decode with lists
of size (q − 1). Such codes have rate exponentially small in q.

Definition I.1 (Code, Rate). A code C ⊆ {x1 , . . . , xq }n
is an ℓ-list-decoding-code for the q/(q − 1) channel, if
for every output word σ ′ ∈ X n , we have {σ ∈ X n :
the input word σ is compatible with σ ′ } ≤ ℓ. Let n(m, q, ℓ)
be the smallest n such that there exists an ℓ-list-decoding code
for the q/(q − 1) channel with m code-words. The zero-errorlist-of-ℓ-rate of C, |C| = m, is given by n1 log2 (m/ℓ), and
the list-of-ℓ-capacity of the q/(q − 1) channel, denoted by
cap(q, ℓ), is the least upper bound on the attainable zero-errorlist-of-ℓ-rate across all ℓ-list-decoding-codes.
The list-of-2-capacity of the 3/2 channel was studied by
Elias [1], who showed that 0.08 ≈ log2 (3)−1.5 ≤ cap(3, 2) ≤
log2 (3) − 1 ≈ 0.58. For the 4/3 channel, Dalai, Guruswami
and Radhakrishnan [2] showed that cap(4, 3) ≤ 6/19 ≈
0.3158, improving slightly on an earlier upper bound of 0.3512
shown by Arikan [3]; it was shown by Körner and Marton [4]
that cap(4, 3) ≥ (1/3) log2 (32/29) ≈ 0.0473. For general
q, one can obtain the following upper bound using a routine
probabilistic argument.
Proposition I.1. n(m, q, q − 1) = exp(O(q)) lg m.
This implies that the cap(q, q − 1) = exp(−O(q)). So for
each fixed q we do have codes with positive rate, but the
rate promised by this construction goes to zero exponentially with q. Fredman and Komlós [5] showed that this
exponential deterioration is inevitable; Körner showed that
cap(q, q) = exp(−Ω(q)). On the other hand, it can be
shown that cap(q, ⌈q ln q⌉) = 1/q, and that for all functions
ℓ : Z → Z we have cap(q, ℓ(q)) ≥ 1/q. Thus, the list-of-ℓcapacity of the q/(q − 1) channel cannot be better than 1/q
unless ℓ is allowed to grow with m.
We thus have the following situation. The list-of-ℓ-rate of
any code reaches the optimal value of 1/q when the listsize is about q ln q; however, the list-of-(q − 1) (as well as
list-of-q) rate is exponentially small in q. It is interesting,
therefore, to study the trade-off between the list size and
the rate, and determine how the rate changes from inverse
polynomial in q to exponentially small in q. Chakraborty,
Radhakrishnan, Raghunathan and Sasatte [6] addressed this
question and showed the following.
Theorem I.2. For every ǫ > 0, there is a δ > 0 such that

for all large q and large enough m, we have n(m, q, (η −
ǫ)q) ≥ exp(δq) log2 m, where η = e/(e − 1) ≈ 1.58. Thus,
cap(q, (η − ǫ)q) = exp(−Ω(q)).
We show the following.
Theorem I.3 (Result). For every ǫ
<
1/6,
for all large q and large enough m, we have
n(m, q, ǫq ln q) ≥ Ω(exp (q 1−6ǫ /8) log2 m). Thus, for
all ǫ < 1/6, cap(q, ǫq ln q) = exp(−Ω(q 1−6ǫ )).
This establishes both parts of the conjecture of Chakraborty
et al. which states the following.
Conjecture I.1. (a) For all constants c > 0, there is a
constant α, such that for all large m, we have n(m, q, cq) ≥
exp (αq) log2 m.
(b) For all functions ℓ(q) = o(q log2 q) and all large m, we
have n(m, q, ℓ(q)) ≥ q ω(1) log2 m.
A. Overview of our approach
We extend the approach of Chakraborty et al., which in turn
was based on the approach used by Fredman and Komlós [5]
to obtain lower bounds on the size of families of perfect
hash functions. To describe our adaptation of this approach,
it will be convenient to reformulate the problem using matrix
terminology.
Consider C ⊆ X n with m code-words. We can build an m×n
matrix C = (cij : i = 1, . . . , m and j = 1, . . . , n) (we use
the name C both for the code and the associated matrix) by
writing the code-words as rows of the matrix (the order does
not matter): so cij = k iff the j-th component of the i-th codeword is xk ∈ X . Then, C is an ℓ-list-decoding code iff the
matrix has the following property: for every choice R of ℓ + 1
rows, there is a column h such that {crh : r ∈ R} = X . In this
reformulation, n(m, q, ℓ) is the minimum n so that there exists
a matrix with this property. We refer to such a matrix as an
ℓ-list-decoding matrix. Furthermore, instead of writing crh we
write h(r); indeed, in the setting of hash families (originally
considered by Fredman and Komlós), the columns correspond
to hash functions that assign a symbol in X to each row-index
in [m].
We can now describe the approach of Chakraborty et al. Fix a
list-size ℓ = αq. Suppose there is an ℓ-list decoding matrix C
with n = exp(βq) log2 m columns. We wish to show that if
β is small then the matrix cannot have the required property;
that is, we can find a set R of ℓ + 1 rows for which h(R) is
a proper subset of [q] for every column h. To exhibit such a
set R we will proceed in stages. In the first stage, we pick
a subset R1 of q − 2 rows at random. Consider a column h.
What can we expect? We expect to see a good number of
collisions, where the same symbol appears in column h at
two different rows in R1 . In fact, we expect h(R) to contain
only about q(1 − 1/e) elements. By appealing to standard
results (e.g., McDiarmid’s inequality), we may conclude that
with probability exponentially close to 1 (that is, of the form
1 − exp(−γq)), h(R) is unlikely to have significantly more

elements. So we might settle on a choice of R, so that h(R)
deviates significantly (say by ǫq for some small ǫ) for at most
exp(−γq) exp(βq) log2 m columns. If the original β is chosen
to be much smaller than γ, this number is an exponentially
small fraction of log2 m.
The key idea now is to make these exceptional columns
ineffective. We do this by focusing our attention on a reduced
number of rows. For each exceptional column, we pick the
symbol that appears most often in that column, and restrict
attention to those rows that have this symbol in the exceptional
column. This depletes the number of rows by a factor at 1/q
for each exceptional column; after we do this sequentially for
all the exp(−(γ − β)q) log2 m ≪ log2 m rows, we will be
left with m′ rows, where log2 m′ = Ω(log2 m). We may
now add more rows to our existing list R1 . If we choose
these from the set of m′ rows, we are in no danger from
the exceptional columns; in the other columns R1 spans about
q(1 − 1/e) symbols, so we can add to R1 about q/e rows R2
(picked from the m′ -rows) and still ensure that in no column
h, we are in danger of h(R1 ∪ R2 ) becoming X . It is clear
that we can carry this approach further, e.g., by picking R2
randomly, expecting a significant number of internal collisions,
making the exceptional columns ineffective, focusing attention
on a smaller but still significant number of rows, etc., then
picking R3 from the rows that survive, and so on. In fact,
Chakraborty et al. derived Theorem I.2 using precisely this
approach.
In this paper, we follow the approach outlined above but
implement the idea more precisely. Before we describe our
contribution it will be useful to pin-point where the calculations in Chakraborty et al. were sub-optimal. We argued
above that after R1 is picked, we expect to span only about
q(1 − 1/e) symbols in a given column h. What about after
R2 is picked? R1 ∪ R2 contains a total of q + q/e rows: if
all symbols in column h appeared with the same frequency
(and continued to do so in the m′ rows after the exceptional
columns were eliminated), then we should expect h(R1 ∪ R2 )
to span about (q + q/e)(1 − exp(1 + 1/e)) symbols. Notice
that this is roughly the expected number of distinct coupons
collected in the classical coupon collector problem after q+q/e
attempts. Unfortunately, there are technical difficulties that
arise in claiming that this number will be reflected in our
process because (i) R1 and R2 are not picked independently,
and (ii) even if the symbols appeared with the same frequency
initially, they may not do so after we focus on a depleted
set of rows. Faced with these difficulties, Chakraborty et al.
settled for less. Instead of matching the bound suggested by
the coupon collector problem, when analysing the expected
size of h(R1 ∪ R2 ), they estimated h(R2 ) separately and
bounded |h(R1 ∪ R2 )| by |h(R1 )| + |h(R2 )|, thereby ignoring
h(R1 ∩ R2 ). The loss in precision resulting from the use of
this union bound increases as the number of phases increases.
Indeed, when the coupon collector process is carried in phases
by picking sets R1 , R2 , . . . , Rt for a large t, progress in
collecting coupons is retarded more by collisions across sets

(because for some i 6= j, h(Ri ) and h(Rj ) have elements in
common) than by collisions within some h(Ri ). By neglecting
collisions across phases, and by failing to track the coupon
collector process closely, the argument in Chakraborty et al.
were unable to push the list size in Theorem I.2 beyond
e/(e − 1).

What is new?: We attempt to track the progress of the coupon
collector faithfully. Instead of the set R1 of size q − 2 that was
picked earlier, we pick an ensemble (a collection of sets) R1
of sets of size q − 2. Similarly, in the later steps we will pick
ensembles R2 , R3 , . . .. However, in the end we pick one set
Ri from each of the ensembles Ri respectively, and assemble
our list of rows: R1 ∪ R2 ∪ · · · ∪ Rt . That this process is more
effective in bounding |h(R1 ∪ R2 ∪ . . . ∪ Rt )| will be formally
verified in later sections. For now, let us qualitatively see how
it helps in bounding |h(R1 ∪ R2 )|. We pick R1 at random:
if the number of sets in the ensemble is large enough (we
will set it to be exp(Θ(q))), then it should reflect a random
set of rows that was obtained by picking rows independently
(q − 2)-times from the set of all rows. Fix a choice for R2 , the
set to be picked at the second stage. Consider X = |h(R1 ∪
R2 )| where R1 is picked uniformly from the ensemble R1 ;
let Y = |h(R1 ∪ R2 )|, where R1 is picked uniformly from
the set of all rows. Then, we expect X and Y to have similar
distribution. So, we proceed as follows. We pick an ensemble
R1 at random. If for a certain column h, the ensemble R1
fails to deliver a good sample, we will need to make that
column ineffective as before. Further, if some set in R1 spans
a significantly larger number of symbols in some column, we
will again make that column ineffective. After this, we pick R2
from the remaining rows. We expect it to not only have a good
number of internal collisions but also be such that |h(R1 ∪
R2 )| and |h(R1 ∪ R2 )| (where the set R2 is chosen uniformly
from the available rows) are similar in expectation. Now, since
we ensured that the ensemble R1 was good for column h, a
random choice of R1 from the ensemble will deliver a value
of |h(R1 ∪ R2 )| that, with high probability, can be bounded
by the number of distinct coupons picked up at the same stage
by the coupon collector; in particular, it accounts for symbols
common to h(R1 ) and h(R2 ). The outline above illustrates
the advantages of picking an ensemble instead of committing
to just one randomly chosen set. However, a large ensemble
comes with its drawbacks. We need to ensure that no set in the
ensemble spans too many elements in any column, or rather,
we need to eliminate any column where some set spans many
elements. This forces a more drastic reduction in the number
of rows than before (that is, now m′ when compared with
m is much smaller than in the calculation in [6]). Thus, it is
important to keep the sizes of the ensembles small. The tradeoff between these opposing concerns needs to be handled with
some care. The argument is presented in detail below.

II. P ROOF

OF THE

R ESULT

In what follows we assume that q is a large natural number
and m → ∞.
We will need the following concentration result due to McDiarmid (1989).
Lemma II.1 (McDiarmid). Let X1 , X2 , . . . , Xn be independent random variables where each Xk takes values in a finite
set A. Let f : An → R be such that |f (x) − f (y)| ≤ c
whenever x and y differ in only one coordinate. Let Y =
f (X1 , X2 , . . . , Xn ); then, for all t > 0,


−2t2
Pr[E[Y ] − Y ≥ t], Pr[Y − E[Y ] ≥ t] ≤ exp
.
nc2
Let C be an ℓ-list-decoding-code for the q/(q−1) channel with
ℓ < q ln q/6. As mentioned in the introduction, we will view
C as an m×n matrix with entries from [q]. In other words, the
rows are indexed by code-words and the columns are indexed
by hash functions. Let wt P
be a function from [q] to {0, 1};
for A ⊆ [q], let wt(A) := a∈A wt(a). Let R be a random
variable taking values in P([m]). Sometimes we use R to also
refer to the distribution of this random variable.
Following the idea mentioned in the introduction, we intend to
keep an ensemble R of sets of rows such that when we pick
a new set of rows R2 from a depleted number of rows m′ ,
we not only observe the correct number of internal collisions
within R2 but also observe the correct number of collision
between members of R and R2 . This motivates the following
definition.
Definition II.1 (Sampler). We say that an ensemble R =
(R1 , R2 , . . . , RL ), where each Ri ⊆ [m], is a (γ, δ)sampler for R wrt column h if (A1 , A2 , . . . , AL ) :=
(h(R1 ), h(R2 ), . . . , h(RL )) satisfies ∀wt : [q] → {0, 1}


h
i
Pr
wt(Aj ) − E wt(h(R)) ≥ γq ≤ exp (−δq).
j∈u [L]

The definition makes provision for all functions wt, because
it tries to anticipate the appropriate internal collisions (see
Lemma II.2) with very little advance knowledge of what the
distribution on [q] looks like in column h after a large number
of rows have been discarded.
Let π : S → [0, 1] be a probability mass function on a
finite set S. Let k ≥ 1, and let X1 , X2 , . . . , Xk be independent random variables each distributed according to π.
Then, let π {k} denote the probability mass function of the
set {X1 , X2 , . . . , Xk }.
For distributions A and B on P([m]), let A ∨ B be the
distribution of S ∪ T where S ∼ A and T ∼ B, with S
and T chosen independently. The following lemma will be
the main workhorse for our argument.
Lemma II.2 (Ensemble Composition Lemma). Let R be
a distribution on P([m]) and let D be a distribution on
[m]. Let R be a (γ, δ)-sampler for R wrt a column h; let

(R1 , R2 , . . . , Rs ) be obtained by taking s independent samples
from the ensemble R. Similarly, let R′ = (R1′ , R2′ , . . . , Rs′ ) be
obtained by taking s independent samples according to R′ ∼
D{tq} where t < 1. Let γ ′ , δ ′ > 0 be such that δ ≤ 2(γ ′ )2 /t
and δ > δ ′ Let s = exp(δ −δ ′ )q, γ
e = γ +γ ′ , δe = δ −δ ′ . Then,
′
with probability 1 − 12 exp (−δ q) over the random choices,
the composed ensemble
e := R1 ∪ R1′ , R2 ∪ R2′ , . . . , Rs ∪ Rs′ )
R

e
of cardinality s, is a (e
γ , δ)-sampler
for R ∨R′ wrt the column
h, and furthermore ∀i ∈ [s],
h
i
h(Ri ∪ Ri′ ) − E h(R ∨ R′ ) ≤ e
γ q.
(1)

Note that this ensemble is generated according to the product
s
distribution (R ∨ R′ ) .



Proof. Fix f : [q] → {0, 1} and let µf := E f (h(R ∪ R′ )) ;
similarly, for R′ ⊆ [m] let µf (R′ ) := ER f (h(R ∪ R′ )) .
First, we bound the probability that when R′ is chosen
according to R′ , it fails to have µf (R′ ) close to µf . Using
McDiarmid’s inequality over the tq primitive choices for R′ ,
we have




−2(γ ′ )2 q 2
′
′
Pr
|µ
(R
)
−
µ
|
≥
γ
q
≤
2
exp
f
f
R′ ∼R′
tq


−2(γ ′ )2 q
= 2 exp
. (2)
t

Now, let wt : [q] → 0, 1 be defined by wt(x) = f (x) if
x 6∈ h(R′ ) and wt(x) = 0 otherwise. Then, for R ⊆ [m], we
have, f (h(R ∪ R′ )) = f (h(R′ )) + wt(h(R)). Therefore (note
here R′ is fixed and R varies randomly in R),


Pr
f (h(R ∪ R′ )) − µf (R′ ) ≥ γq
R∈u R




= Pr
wt(h(R)) − E wt(h(R)) ≥ γq
R∈u R

and since R is a (γ, δ)-sampler wrt R, we have




Pr
wt(h(R)) − E wt(h(R)) ≥ γq ≤ exp(−δq).
R∈u R

Thus,

h

i
′
′
f
(h(R
∪
R
))
−
µ
≥
(γ
+
γ
)q
≤
f
R∈u R,R ∼R′
i
h
|µf − µf (R′ )| ≥ γ ′ q +
Pr
R∈u R,R′ ∼R′
h
i
Pr ′ ′ µf (R′ ) − f (h(R ∪ R′ )) ≥ γq
R∈u R,R ∼R


h
i
−2(γ ′ )2 q
+ exp −δq ≤ 3 exp(−δq). (3)
≤ 2 exp
t
Pr ′

(We used δ ≤ 2(γ ′ )2 /t to justify the last inequality.) Let ∆ :=
3 exp(−δq), the quantity on the right in (3). By taking f to be
the all-1’s function, we conclude from (3) that for each i with


probability at least 1 − ∆, h(Ri ∪ Ri′ ) − E |h(R ∨ R′ )| ≤
(γ + γ ′ )q.

Now,
f (h(Ri ∪ Ri′ )) = h(Ri ) ∪ h(Ri′ ) , and µf =

E |h(R ∨ R′ )| . Now, by a union bound over the s choices
for i, we obtain




Pr ∃i ∈ [s], h(Ri ∪ Ri′ ) − E h(R ∨ R′ ) ≥ (γ + γ ′ )q
e
R

≤ ∆s ≤ 3 exp(−δ ′ q).

(4)

This establishes (1).
It remains to establish our first claim that whp the ensemble
e
picked according to (R ∨ R′ )s is a (e
γ , δ)-sampler
for R ∨ R′ .
Fix f : [q] → {0, 1}. Now, (3) implies that for each i ∈
[s], the probability that |f (h(Ri ∪ Ri′ )) − µf | ≥ (γ + γ ′ )q
is exponentially
for
 small in q.′ Then, the tail probabilities

Ps
′
Y :=
i=1 I |f (h(Ri ∪ Ri )) − µf | ≥ (γ + γ )q can be
bounded by considering Bin(s, ∆). Therefore,
e
Pr [Y > exp (−δq)s]
e
R


s
e
≤
(∆)exp (−δq)s
e
exp (−δq)s
e
exp (−δq)s
e
≤ (e exp (δq)∆)
≤ 9 exp (−δ ′ q).

(5)

(We need to take a union bound against the 2q possible
functions f : [q] → {0, 1}: by changing s to qs we may
easily establsih this.) By (4) and (5), the probability that our
e
ensemble fails to be a (e
γ , δ)-sampler,
with γ
e = γ + γ ′ and
′
δe = δ − δ , or fails to satisfy (1) is at most 12 exp (−δ ′ q).

Let us recall the template of our argument. At any stage we
will have an ensemble of sets of rows, say R, and a universe
U ⊆ [m] to choose sets of rows from to add to R. We will
add a specific number of randomly chosen sets of rows of a
particular size from U and then declare those columns bad
where the modified R deviates from its expected behaviour.
Consider a set R ∈ R: we want to say that the couponcollector process at |R| probes into [q] is the gold standard for
good behaviour, i.e., no set in R will have expansion more
than the coupon-collector at the same stage. The expected
number of elements that the coupon-collector process picks
up after a i.i.d. uniform probes into [q] is approximately
q (1 − exp(−a/q)): we will denote this as µcc
q (a). So, we need
the following lemma, which is proved in the appendix.
Lemma II.3 (Phased Coupon Collector). Let a1 , a2 , . . . , ak
be positive integers; let a = a1 + a2 + · · · + ak ,
and let π1 , π2 , . . . , πk be probability mass functions. Let
A1 , A2 , . . . , Ak be independent random variables taking val{a }
ues in P([q]), where Ai ∼ πi i . Suppose a ≤ ǫq ln q and
ǫ
k ≤ eq for some ǫ < 1/3, then,
E[|A1 ∪ A2 ∪ · · · ∪ Ak |] ≤ q (1 − exp(−a/q)) + o(q 1−ǫ )
1−ǫ
= µcc
).
q (a) + o(q

Our next target is to understand the number of iterations we
wish to perform, i.e., the number of times we need to enlarge

the sizes of the sets surviving the ensemble R so that the list
size hits the target of ǫq ln q, where ǫ < 1/6. At the first stage
we will pick up sets of rows of size about ℓ1 = q, and expect
the image size to be close to µcc
q (ℓ1 ); we then prune out the
exceptional columns. In the next stage, we pick sets of size
about ℓ2 = q − µcc
q (ℓ1 ) and expect the combined image size
to be close to µcc
q (ℓ1 + ℓ2 ). Hence, in the third iteration we
pick sets of size close to ℓ3 = q − µcc
q (ℓ1 + ℓ2 ), and so on
for the subsequent iterations. P
We are interested in the list size
k
after k iterations, i.e, ℓ≤k := i=1 ℓi . We have the following
proposition, which is proved in the appendix.
Proposition
II.4. Let ℓ1 = q, and for i ≥ 1 let ℓi+1 = q −
Pi
ǫ
µcc
q (
j=1 ℓj ). Suppose k = eq for some ǫ < 1, then, ℓ≤k ≥
ǫq ln q.
Proof. (The series {ℓ≤k } tends to q ln q.)
Finally, we need a lemma where we glue all the steps mentioned in the introduction. At each iteration k, we maintain an
ensemble Rk satisfying the requisite properties.
We call a distribution D on P([m]) a (g1 , . . . , gk )-phased
{g }
{g }
{g }
coupon collector distribution if D = D1 1 ∨D2 2 . . .∨Dk k
where each Di is a probability mass function on [m]. The
following lemma tracks how the parameters change with each
iteration.
Lemma II.5 (Iteration Lemma). Let k ≤ q ǫ for some
ǫ < 1/5. Let γ = γ ′ = q −2ǫ /2 and δ ′ = q −5ǫ /4. Assume
n ≤ exp (δ ′ q) log2 m/(48 · q ǫ log2 q). Then, there exists a
partition H1 (k) ⊔ H2 (k) of the columns of C, a universe of
rows Uk ⊆ [m], an ensemble Rk = (R1 , R2 , . . . RLk ), integers (g1 , . . . , gk ) and a (g1 , . . . , gk )-phased coupon collector
distribution Dk such that:
a g1 = q − 2, and gi+1 = q − µcc
q (gi ) − (i + 1)γq − 2
b ∀i ∈ [Lk ], |Ri | = g≤k ≥ ℓ≤k − 2k − k 2 γq/2
c ∀h ∈ H2 (k), ∀i ∈ [Lk ], |h(Ri ∪ Uk )| ≤ q − 1
d ∀h ∈ H1 (k), Rk is a ((k + 1)γ, γ 2 − kδ ′ )-sampler for
Dk wrt h
e ∀h ∈ H1 (k), ∀i ∈ [Lk ] |h(Ri )| − E [h(Dk )] ≤ (k +
1)γq
f log2 |Uk | ≥ log2 m − k log2 q · 24 exp (−δ ′ q)n.
Proof. We will use induction on k. For k = 1 we have g1 =
q − 2. We use Lemma II.2 with R being the constant ∅, and
R = {∅}. Clearly, R is a (γ, γ 2 )-sampler for R. Let D be the
uniform distribution over [m] and let R′ = (R1′ , R2′ , . . . , Rs′ )
be obtained by taking s = exp ((γ 2 − δ ′ )q) independent
samples according to R′ ∼ D{q−2} . So, D1 = D{q−2} . For
a fixed column h we have the following: with probability
1 − 12 exp (−δ ′ q) over the random choices, the composed
ensemble
e = R1′ , R2′ , . . . , Rs′ )
R

e is a (2γ, γ 2 − δ ′ )-sampler for R′ wrt
is good wrt h, i.e., R
the column h, and furthermore ∀i ∈ [s],
h
i
h(Ri′ ) − E h(R′ ) ≤ 2γq.

Hence, on expectation only 12 exp (−δ ′ q)n columns are bad.
Therefore, with probability at least 1/2 at most 24 exp (−δ ′ q)n
columns are bad. Also, the probability of an Ri′ ∈ R′ having
size less than q − 2 (because some two of our q − 2 choices of
rows picked the same row) is at most q 2 /m. Thus, by the union
bound the probability of (b) not holding is at most s · q 2 /m
e which
which is less than 1/2. Therefore, there is choice of R,
1
′
we call R , such that at most 24 exp (−δ q)n columns are bad
and (b) holds. The set of bad columns is H2 (1) and the set of
good columns is H1 (1). Then, clearly (d) and (e) are true.

Let H2 (1) = {h1 , . . . , hb } where b ≤ 24 exp (−δ ′ q)n and
WLOG assume that 1 is the most frequent symbol in h1 .
Retain only those rows in U that correspond to the symbol
1 in h1 . Call this pruned universe U ′ : we have ensured that so
long as we add rows to Ri ∈ R1 only from U ′ , the image size
in h1 is at most h1 (R) + 1 ≤ q − 1. Thus, by taking a multiplicative hit of at most 1/q we have rendered h1 ineffective.
 b
Iterating this over H2 (1) we take a multiplicative hit of 1q .
Hence, we obtain a universe U ′ , which will be U1 , such that
log2 |U ′ | = log2 |U1 | ≥ log2 m − 24 exp (−δ ′ q)n log2 q. This
establishes (c) and (f). This establishes the claims for k = 1;
the induction step in general is similar.
Now, as our IH let us assume that for (k − 1) we have
the partition H1 (k − 1) ⊔ H2 (k − 1), Uk−1 ⊆ [m], Rk−1 ,
integers (g1 , . . . , gk−1 ) and Dk−1 such that (a) through (f)
are satisfied. Then, we repeat the above argument. We have
gk = q − µcc
q (gk−1 ) − kγq − 2. We use Lemma II.2 for
h ∈ H1 (k − 1) with R being Dk−1 , and R = Rk−1
which is a (kγ, γ 2 − (k − 1)δ ′ )-sampler for Dk−1 wrt h. Let
(R1 , . . . , Rs ) be obtained by s = exp (γ 2 − kδ ′ ) independent
samples from Rk−1 . Let D be the uniform distribution over
Uk−1 and let R′ = (R1′ , R2′ , . . . , Rs′ ) be obtained by taking
s independent samples according to R′ ∼ D{gk } . We let
Dk = Dk−1 ∨ D{gk } . For a fixed column h we have the
following: wp 1 − 12 exp (−δ ′ q) over the random choices, the
composed ensemble
e = R1 ∪ R1′ , R2 ∪ R2′ , . . . , Rs ∪ Rs′ )
R

e is a ((k + 1)γ, γ 2 − kδ ′ )-sampler for
is good wrt h, i.e., R
Dk wrt h, and furthermore ∀i ∈ [s],
h
i
h(Ri ∪ Ri′ ) − E h(Dk ) ≤ (k + 1)γq.

Hence, on expectation only 12 exp (−δ ′ q)n columns of
H1 (k − 1) are bad. Therefore, with probability at least 1/2
at most 24 exp (−δ ′ q)n columns of H1 (k − 1) are bad. Also,
e having size less than g≤k
the probability of an Ri ∪ Ri′ ∈ R
cc
(because some two of our q − µq (gk−1 ) − kγq − 2 choices of
rows for Ri′ picked the same row of collided with some row in

Ri ) is at most (q ln q)2 /|Uk−1 |. Thus, by the union bound the
probability of (b) not holding is at most s · (q ln q)2 /|Uk−1 |
e which
which is less than 1/2. Therefore, there is choice of R,
k
′
we call R , such that at most 24 exp (−δ q)n columns of
H1 (k−1) are bad and (b) holds. Combining these bad columns
with H2 (k−1) we obtain H2 (k) and the columns not in H2 (k)
form the set H1 (k) = H2 (k). Then, clearly (d) and (e) are
true.
Let H2 (k) \ H2 (k − 1) = {h1 , . . . , hb } where b ≤
24 exp (−δ ′ q)n and WLOG assume that 1 is the most frequent
symbol in h1 . Retain only those rows in Uk−1 that correspond
to the symbol 1 in h1 . Call this pruned universe U ′ : this
pruning ensures that so long as we add rows to Ri ∈ Rk
only from U ′ , the image size in h1 is at most q − 1. Thus, by
taking a multiplicative hit of at most 1/q we have rendered h1
ineffective. Iterating this over H2 (k) we take a multiplicative
 b
hit of 1q . Hence, we obtain a universe U ′ , which will
be Uk , such that log2 |U ′ | = log2 |Uk | ≥ log2 |Uk−1 | −
24 exp (−δ ′ q)n log2 q ≥ log2 m − k log2 q · 24 exp (−δ ′ q)n.
Together with property (c) of Uk−1 this establishes (c) and
(f). This completes the induction step.
Proof of Theorem I.3 (main result of the paper). Fix an ǫ′ <
1/6 and let C be an ǫ′ q ln q-list-decoding-code for the q/(q−1)
channel. Choose λ ≪ ǫ′ and let ǫ = ǫ′ +λ. Let q be sufficiently
′
large so that k = q ǫ ≥ eq ǫ +λ/2 . We will appeal to Lemma II.5
(with k and ǫ) and assume that n ≤ exp (δ ′ q) log2 m/(48 ·
q ǫ log2 q). Then, by choosing a set of rows R in the ensemble Rk and using (b) and Proposition II.4 we obtain that
|R| ≥ ǫ′ q ln q. However, using (c) we have that for all columns
h ∈ H2 (k), |h(R)| ≤ q − 1. Also, using (e) and Lemma II.3
we obtain that for all h ∈ H1 (k), |h(R)| < q. This is a contradiction and hence n > exp (δ ′ q) log2 m/(48 · q ǫ log2 q) or for
′
sufficiently large q we have n > Ω(exp (q 1−6ǫ /8) log2 m).
We note that it is possible by a more careful analy′
sis to improve the bound of Ω(exp (q 1−6ǫ /8) log2 m) to
1−4ǫ′
Ω(exp (q
/8) log2 m) in which case we may apply the
bound till a list size of q ln q/4. This bound is obtained by
modifying Lemma II.5 to accommodate γ ′ and δ ′ which vary
across the induction steps and being more scrupulous about
the argument in the preceding paragraph.

ACKNOWLEDGEMENTS
We are grateful to Prahladh Harsha for the numerous detailed
discussions that led to the result reported in this paper, and also
for proof-reading it. We also thank Ramprasad Saptharishi for
his help with Lemma II.3.
R EFERENCES
[1] P. Elias, “Zero error capacity under list decoding,” IEEE Transactions on
Information Theory, vol. 34, no. 5, pp. 1070–1074, Sep 1988.

[2] M. Dalai, V. Guruswami, and J. Radhakrishnan, “An improved bound on
the zero-error list-decoding capacity of the 4/3 channel,” in 2017 IEEE
International Symposium on Information Theory, ISIT 2017, Aachen,
Germany, June 25-30, 2017, 2017, pp. 1658–1662. [Online]. Available:
https://doi.org/10.1109/ISIT.2017.8006811
[3] E. Arikan, “An upper bound on the zero-error list-coding capacity,” IEEE
Transactions on Information Theory, vol. 40, no. 4, pp. 1237–1240, Jul
1994.
[4] J. Korner and K. Marton, “New bounds for perfect hashing
via information theory,” European Journal of Combinatorics,
vol. 9, no. 6, pp. 523 – 530, 1988. [Online]. Available:
http://www.sciencedirect.com/science/article/pii/S0195669888800489
[5] M. L. Fredman and J. Komlós, “On the size of separating systems
and families of perfect hash functions,” SIAM Journal on Algebraic
Discrete Methods, vol. 5, no. 1, pp. 61–68, 1984. [Online]. Available:
https://doi.org/10.1137/0605009
[6] S. Chakraborty, J. Radhakrishnan, N. Raghunathan, and P. Sasatte,
“Zero error list-decoding capacity of the q/(q-1) channel,” in FSTTCS
2006: Foundations of Software Technology and Theoretical Computer
Science, 26th International Conference, Kolkata, India, December
13-15, 2006, Proceedings, 2006, pp. 129–138. [Online]. Available:
https://doi.org/10.1007/11944836_14

A PPENDIX
Proof of Lemma II.3. Consider a constant λ ≪ ǫ. For i =
1, 2, . . . , k, let Bi be the set of q 1−2ǫ−λ elements of [q] taking
the topmost values in πi . Let B = B1 ∪ B2 ∪ · · · ∪ Bk ; note
that |B| ≤ kq 1−2ǫ−λ = o(q 1−ǫ ). Then, E[|A1 ∪ A2 ∪ . . . Ak |]
is at most
!
k
X
Y
ai
.
(1 − πi (x))
|B| +
1−
x6∈B

i=1

Now, for x 6∈ B, we have πi (x) ≤ 1/q 1−2ǫ−λ , and

1 − πi (x) ≥ exp −πi (x)/ 1 − πi (x)

≥ exp −πi (x) 1 + 2/q 1−2ǫ−λ .

Then, by the AM-GM inequality we have the upper-bound


X
ai πi (x) .
|B| + q − q exp −(1 + 2/q 1−2ǫ−λ )(1/q)
i,x

Our 
claim
follows
from
P
√
exp −(1 + 2/ q)(1/q) i,x ai πi (x)
o(1/q 1−2ǫ ) ≥ exp (−a/q) − o(q 1−ǫ )/q.

≥

this
because
exp(−a/q) −

Proof of Proposition II.4. Suppose ℓ≤i ∈ [jq, (j + 1)q] for
some j ≥ 0, then, ℓi+1 ≥ q/ej+1 . Therefore, the number of i’s
for which ℓ≤i ∈ [jq, (j + 1)q] ≤ ej+1 . Suppose ℓ≤k < ǫq ln q,
then as a contradiction we have
k < e + e2 + · · · + eǫ ln q ≤ eq ǫ .

