Examples in which the size of the alphabet ($\geq 2$) used for an encoding matters

Question

Let $\Sigma$ be an alphabet, ie a nonempty finite set. A string is any finite sequence of elements (characters) from $\Sigma$. As an example, $ \{0, 1\}$ is the binary alphabet and $0110$ is a string for this alphabet.

Usually, as long as $\Sigma$ contains more than 1 element, the exact number of elements in $\Sigma$ doesn't matter: at best we end up with a different constant somewhere. In other words, it doesn't really matter if we use the binary alphabet, the numbers, the Latin alphabet or Unicode.

Are there examples of situations in which it matters how large the alphabet is?

The reason I'm interested in this is because I happened to stumble upon one such example:

For any alphabet $\Sigma$ we define the random oracle $O_{\Sigma}$ to be an oracle that returns random elements from $\Sigma$, such that every element has an equal chance of being returned (so the chance for every element is $\frac{1}{|\Sigma|}$).

For some alphabets $\Sigma_1$ and $\Sigma_2$ - possibly of different sizes - consider the class of oracle machines with access to $O_{\Sigma_1}$. We're interested in the oracle machines in this class that behave the same as $O_{\Sigma_2}$. In other words, we want to convert an oracle $O_{\Sigma_1}$ into an oracle $O_{\Sigma_2}$ using a Turing machine. We will call such a Turing machine a conversion program.

Let $\Sigma_1 = \{ 0, 1 \}$ and $\Sigma = \{ 0, 1, 2, 3 \}$. Converting $O_{\Sigma_1}$ into an oracle $O_{\Sigma_2}$ is easy: we query $O_{\Sigma_1}$ twice, converting the results as follows: $00 \rightarrow 0$, $01 \rightarrow 1$, $10 \rightarrow 2$, $11 \rightarrow 3$. Clearly, this program runs in $O(1)$ time.

Now let $\Sigma_1 = \{ 0, 1 \}$ and $\Sigma = \{ 0, 1, 2 \}$. For these two languages, all conversion programs run in $O(\infty)$ time, ie there are no conversion programs from $O_{\Sigma_1}$ to $O_{\Sigma_2}$ that run in $O(1)$ time.

This can be proven by contradiction: suppose there exists a conversion program $C$ from $O_{\Sigma_1}$ to $O_{\Sigma_2}$ running in $O(1)$ time. This means there is a $d \in \mathbb{N}$ such that $C$ makes at most $d$ queries to $\Sigma_1$.

$C$ may make less than $d$ queries in certain execution paths. We can easily construct a conversion program $C'$ that executes $C$, keeping track of how many times an oracle query was made. Let $k$ be the number of oracle queries. $C'$ then makes $d-k$ additional oracle queries, discarding the results, returning what $C$ would have returned.

This way, there are exactly $|\Sigma_1|^d = 2^d$ execution paths for $C'$. Exactly $\frac{1}{|\Sigma_2|} = \frac{1}{3}$ of these execution paths will result in $C'$ returning $0$. However, $\frac{2^d}{3}$ is not an integer number, so we have a contradiction. Hence, no such program exists.

More generally, if we have alphabets $\Sigma_1$ and $\Sigma_2$ with $|\Sigma_1|=n$ and $|\Sigma_2|=k$, then there exists a conversion program from $O_{\Sigma_1}$ to $O_{\Sigma_2}$ if and only if all the primes appearing in the prime factorisation of $n$ also appear in the prime factorisation of $k$ (so the exponents of the primes in the factorisation doesn't matter).

A consequence of this is that if we have a random number generator generating a binary string of length $l$, we can't use that random number generator to generate a number in $\{0, 1, 2\}$ with exactly equal probability.

I thought up the above problem when standing in the supermarket, pondering what to have for dinner. I wondered if I could use coin tosses to decide between choice A, B and C. As it turns out, that is impossible.

Answer 1

There are some examples in formal language theory where 2-character and 3-character alphabets give qualitatively different behaviors. Kozen gives the following nice example (paraphrased):

Let the alphabet be $\Sigma$ = {1,..,k} with the standard numerical ordering, and define sort(x) to be the permutation of the word x in which the letters of x appear in sorted order. Extend sort(A) = { sort(x) | x $\in$ A }, and consider the following claim:

If A is context-free then sort(A) is context-free.

This claim is true for k = 2, but false for k $\ge$ 3.

Answer 2

Dinur's proof of the PCP theorem relies heavily on the manipulation of the alphabet size.

Specifically, the overall structure of the proof is an iterative application of a graph powering technique a logarithm in the graph size number of times. On each iteration, the graph is pre-processed into a regular expanding graph, amplified by a power (which blows up the alphabet size), and then a PCP composition is applied (turning each constraint over a large alphabet into a system of constraints over a small alphabet).

The implicit goal of the process is to find a way to re-use the amplification step until the UNSAT value becomes a constant fraction (proving the PCP theorem). The key point is that unless the alphabet size is pulled back each time, the resulting graph is not what is needed for the final reduction.

Answer 3

The requirements of your example are quite strict. If you relax it to only require that the conversion works in $O(1)$ in expectation. It is possible to sample uniformly from $\{0,1,2\}$ using, in expectation, a constant number of coin tosses.

I am not an expert on this but one nice example were the size of the alphabet does matter are coding and succinct data structures. Imagine you want to represent a message over the alphabet $\{0,1,2\}$ in the alphabet $\{0,1\}$ (e.g. to store it in your binary computer). You want to minimize the space required but at the same time, you want to be able to read and write individual characters of the message fast (let's say in $O(1)$). Problems like this have been studied for quite some time now. The recent paper by Dodis, Patrascu, and Thorup on it, and the references therein, should be a good point to start.

Answer 4

In error correcting codes, it is possible that there is a fundamental difference between binary codes and codes over larger alphabets in that the Gilbert Varshamov examples for codes which correct a fraction of errors (which are essentially greedy or random examples) are believed by some to be tight in the binary case and are known to be not tight over a large alphabet via algebraic-geometry codes. This led some to speculate that the standard definition of error correcting codes for a large alphabet is not the right analog of binary error correcting codes.

Answer 5

I've encountered an interesting case in my own research of small differences in alphabet size making dramatic differences in the resulting theory. A rough description of the problem of learning probabilistic circuits is the following: a learner can override gates of a hidden circuit and observe the resulting output, and the goal is to produce a "functionally equivalent" circuit. For boolean circuits, whenever a gate has "influence" on the output, one can isolate an influential path from that gate to the output of the circuit. For circuits of alphabet size $\ge 3$ this becomes no longer the case -- namely, there are circuits who have gates with large influence on the output value, but no influence along any one path to the output! We found this result quite surprising.

The result is somewhat technical, but if you're interested, you can contrast Lemma 8 with Section 4.1 for relevant the theorem statements.