Examples in which the size of the alphabet ($\geq 2$) used for an encoding matters 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&#39;$ that executes $C$, keeping track of how many times an oracle query was made. Let $k$ be the number of oracle queries. $C&#39;$ 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&#39;$. Exactly $\frac{1}{|\Sigma_2|} = \frac{1}{3}$ of these execution paths will result in $C&#39;$ 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.
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.