Here is a quick post to record a combinatorial game that I think might be of interest, but I don’t have time to think about seriously now.
When Person A plays Person B on the online chess server on which I spend far too much time, the server looks to see who has the longest run of consecutive games as black, and chooses that person to be white. Ties are broken randomly. This is a simple but effective rule: for instance it guarantees that in a series of games, the players alternate colours.
Now suppose a team of people want to manipulate the server into giving one of their members a long run of consecutive games as white. (This would of course be strictly against the server policies.) How big must the team be to guarantee that some member gets 
A quick look at the small cases reveals the answer. With three people, having arbitrary past histories (this matters below), A plays B and the black player, B say, then plays C. If B is white, then when A plays B again, either A or B establishes a run of two games as white. If B is black (for instance this always happens if C has had a run of two black games), then when A plays C, either A or C gets the same run. Note that in the first case, A never plays C, but instead plays B twice.
With four people, we use the strategy above to give A a run of two white games, and then using B, C, D, give B say, another run of two white games. Now when A and B play, a run of three white games is established. Continuing inductively we see that 
One might also ask for the analogous result where multiple games between the same people are not allowed. If the aim is instead to maximize the number of games as white, then we obtain the combinatorial game where the ‘Picker’ picks an edge of the complete graph 
Returning to the original setting where we care about runs of white games, this shows that the Chooser can guarantee the longest run is at most the maximum out-degree, namely 
I’ll end with two natural questions suggested by this quick analysis.
Question 1
Let 
Question 2
As Question 1, but now each edge may only be picked once.
For the first in the case of the complete graph, the analysis above shows that the Picker can force a run of length
Posted by mwildon 
, such as the familiar Euclidean space 
, or (my answer) an indeterminately large space over a finite field: 
? Or perhaps the most important vector spaces you meet are function spaces, in which case you might be imagining Hilbert space, with or without a preferred orthonormal basis. Yet other answers are possible: someone working in cryptography might think of 
. Quite possibly, I’ve missed your preferred example completely. Or maybe your brain just doesn’t work this way, and all you think about is the abstract definition of vector spaces and your immediate associations are to the main theorems you use when working with them. Anyway, my point is that we don’t think about vector spaces ‘in isolation’: instead they come with a bundle of implicit associations that are deeply shaped by our education and day-to-day experience.
then the more accurate 
. This is reflected in the 
is tiny compared to 
and 
should seem only a tiny bit smaller than
. 
and 
are ‘tiny’, 
and 
are ‘huge’ and 
and 
sit somewhere in the middle. To give some hint of the most surprising part of this, interpret 
, so 
), and since 
, will run for a finite length of time and then return the correct answer. 
be the solid 
be the 
. 
. For instance, 
is the one-point compactification of 
with two regions of equal height shaded.
and 
by 
. Choose 
. Then since 
is orthogonal to the gradient of the sphere at 
, to first order, if we increase the height 
from 
then we must decrease the second coordinate 
from 
. This is shown in the diagram below.
between the lines of latitude of height between 
) the product of 
and the circumference of the line of latitude at height 
to 
for the surface area of the sphere; as expected this is also the surface area of the enclosing cylinder of radius 
, by the argument just given, the arclength at height 
. Therefore in the one-point compactification of Lineland (a place one might feel is already insular enough), from the god’s perspective (considering slices with varying 
), and almost no-one lives on the equation (
).
-dimensional sphere of radius 
. By dimensional analysis, its surface area is 
for some constant 
. (A complete proof of this using only elementary calculus is given in Exercise 1 of the problem sheet.) In particular, we see that when 
using colours red then blue then black.
random samples from 
, taking (left) 
coordinates and (right) 
coordinates. Note that almost no points have a coordinate more than 
(in absolute value). Moreover, since the expected value of each 
is 
, we find most of the mass at 
.
then it is almost certain that most of the 
are very small. 
through the origin, and get a similar conclusion. 
be independent identically distributed normal random variables each with mean 
and variance 
. Then 
normalized to have length 
.) Moreover, ![\mathbb{E}[X_1^2 + \cdots + X_n^2] = 1](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BE%7D%5BX_1%5E2+%2B+%5Ccdots+%2B+X_n%5E2%5D+%3D+1&bg=ffffff&fg=333333&s=0 "\mathbb{E}[X_1^2 + \cdots + X_n^2] = 1")
, and, using that ![\mathrm{Var}[X_i^4] = 3/n^2](https://s0.wp.com/latex.php?latex=%5Cmathrm%7BVar%7D%5BX_i%5E4%5D+%3D+3%2Fn%5E2&bg=ffffff&fg=333333&s=0 "\mathrm{Var}[X_i^4] = 3/n^2")
, we get![\displaystyle \mathrm{Var}[X_1^2 + \cdots + X_n^2] = n \frac{3}{n^2} + n(n-1) \frac{1}{n^2} - 1 = \frac{2}{n}.](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Cmathrm%7BVar%7D%5BX_1%5E2+%2B+%5Ccdots+%2B+X_n%5E2%5D+%3D+n+%5Cfrac%7B3%7D%7Bn%5E2%7D+%2B+n%28n-1%29+%5Cfrac%7B1%7D%7Bn%5E2%7D+-+1+%3D+%5Cfrac%7B2%7D%7Bn%7D.&bg=ffffff&fg=333333&s=0 "\displaystyle \mathrm{Var}[X_1^2 + \cdots + X_n^2] = n \frac{3}{n^2} + n(n-1) \frac{1}{n^2} - 1 = \frac{2}{n}.")
is a random variable then ![\displaystyle \mathbb{P}\bigl[|Z-\mathbb{E}Z| \ge c\bigr] \le \frac{\mathrm{Var} Z}{c^2},](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Cmathbb%7BP%7D%5Cbigl%5B%7CZ-%5Cmathbb%7BE%7DZ%7C+%5Cge+c%5Cbigr%5D+%5Cle+%5Cfrac%7B%5Cmathrm%7BVar%7D+Z%7D%7Bc%5E2%7D%2C&bg=ffffff&fg=333333&s=0 "\displaystyle \mathbb{P}\bigl[|Z-\mathbb{E}Z| \ge c\bigr] \le \frac{\mathrm{Var} Z}{c^2},")
is at most 
which tends to 
. Therefore we can, with small error, neglect the normalization and regard 
as a uniformly chosen point on 
. By Markov’s inequality, that if ![\mathbb{P}[Z > a\mathbb{E}Z] < 1/a](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BP%7D%5BZ+%3E+a%5Cmathbb%7BE%7DZ%5D+%3C+1%2Fa&bg=ffffff&fg=333333&s=0 "\mathbb{P}[Z > a\mathbb{E}Z] < 1/a")
, the probability that 
(or equivalently, 
) is at most 
, and the probability that 
(or equivalently, 
with 
) is at most 
. Since 
. I think this makes the counter-intuitive conclusion of the previous subsection even starker.
is the surface area of 
. Since 
and 
, the volume 
of 
is
for 
we get 
. Hence 
(is there a quick way to see this?), and the proportion of the cube ![[-1,1]^{2m}](https://s0.wp.com/latex.php?latex=%5B-1%2C1%5D%5E%7B2m%7D&bg=ffffff&fg=333333&s=0 "[-1,1]^{2m}")
occupied by the ball 
is 
of length 
he decodes it as the message in bijection with the nearest codeword in 
. If 
then reliable communication is impossible and if 
then we can immediately reduce to the case 
by flipping all bits in a received word. We therefore assume that 
, where 
is the binary entropy function. That is, given any 
, provided 
such that when 
(uniformly for every codeword). We outline a proof later.
bits per second. Since 
, provided 
. In other words, Alice and Bob can communicate reliably at a rate of up to 
million bits per second.
positions, where these positions are chosen by an adversary to be as inconvenient as possible. Nearest neighbour decoding always succeeds if and only if the minimum distance of the code is at least 
. 
is negligible. Therefore a binary code with minimum distance 
, in which the number of flipped bits is always 
, and these bits are chosen adversarially.
be? Let 
, let
is a binary code of length 
and minimum distance at least 
for all 
.) Since each 
, we find that
of a binary code 
. By the bound above, if 
) we have 
then 
: the code consists of a vanishing small proportion of 
or more, fast communication in the Hamming model is impossible. 
is sent over the binary symmetric channel with crossover probability 
is received, while 
, it is not appreciably closer to any other codeword 
. I claim that this situation is possible because 
is sent, exactly 
.) By the Law of Large Numbers, this is a good approximation to binomially distributed errors, and it is routine using standard estimates (Chebychev’s Inequality is enough) to modify the proof below so it works for the original channel. 
and let 
, where 
codewords 
uniformly at random from 
be the probability (in the probability space of the toy binary symmetric channel) that when 
is sent, the received word is decoded incorrectly by nearest neighbour decoding. In the toy binary symmetric channel, the received word 
that when 
with 
within distance 
are all themselves random variables, defined in the probability space of the random choice of code.
is the volume (i.e. number of words) in the Hamming ball of radius 
. We can model words in this ball as the output of a random source that emits the bits 
and 
, so we expect to be able to compress its 
. Correspondingly,
, the probability 
is smaller than 
, provided 
for all 
remaining codewords. 
is replaced with 
for 
becomes effective, giving another constraint that also apparently contradicts Shannon’s Noisy Coding Theorem. There is however one interesting difference: in 
there are 
words at distance 
above as the key length of the block cipher DES. This cipher is no longer in common use because a determined adversary knowing (as is usually assumed) some plaintext/cipher pairs can easily try all 
possible keys and so discover the key. Even back in 2008, an 
DES keys every second, giving 
days for an exhaustive search. 
and 
. In 
basic operations, strongly suggesting that 
calculations. Thus in a computational sense, 
and 
are effectively infinite. 
. The Chinese supercomputer 
operations per second. A modern Intel chip has AES encryption as a primitive instruction, and can encrypt at 
keys every second, requiring 
days to exhaust over 
keys. Therefore 
, extending the definition in the natural way to all integers 
on the integers such that 
is true if and only if 
and 
is true if and only if 
mod 
. 
; 
. We check this in Haskell using its very helpful ‘list-comprehension’ syntax; again this is very close to the analogous mathematical notation for sets.
to be true (for all 
to be true if and only if 
, we have 
and 
. 
defined by 
, ubiquitous in Haskell code. We now ask: is there a Haskell function
above show that such a function would, at a stroke, make most mathematicians unemployed. Fortunately for us, Turing’s solution to the 
, but instead on the 
. We think of the 
representing 
and the bitstream 
representing
:
. For example, the odd 
is shown by thick lines.
-partitions and, as an application, give a short motivated proof of the 
partitions of 
with at most three parts, namely 
has two columns of length 1, and one each of lengths 2 and 3. It is counted in the coefficient of 
, obtained when we expand the geometric series by choosing 
(two columns of length 1) from 
(one column of length 2) from 
(one column of length 3) from 
in the generating function with 
. Since the coefficient of 
above is 
with 
. (I like to see this by mentally removing the first row: the remaining diagram then has a column of size 
th largest part is strictly more than the 
th largest part for all 
are enumerated by
be a poset with partial order 
. A 
.
with the usual order then 
is the sequence of values of a 
. Thus, by removing any initial zeros and reversing the sequence, ![[(4,2,1)] = \{(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(3,1)\}](https://s0.wp.com/latex.php?latex=%5B%284%2C2%2C1%29%5D+%3D+%5C%7B%281%2C1%29%2C%281%2C2%29%2C%281%2C3%29%2C%281%2C4%29%2C%282%2C1%29%2C%282%2C2%29%2C%283%2C1%29%5C%7D&bg=ffffff&fg=333333&s=0 "[(4,2,1)] = \{(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(3,1)\}")
and 
. This is shown diagramatically below.
![[(4,2,1)]](https://s0.wp.com/latex.php?latex=%5B%284%2C2%2C1%29%5D&bg=ffffff&fg=333333&s=0 "[(4,2,1)]")
such that that the rows and columns are weakly increasing when read left to right and top to bottom. For example, three of the 
are shown below
, so now 
, ordered by 
, 
. Comparing 
and 
, we divide the 
, and those with 
. The first class satisfy 
. Suppose that 
in the order on 
, in which case we say the labelling is natural for 
, or 
, in which case we say the labelling is strict for 
-partition is then an order preserving function 
is a covering relation and
;
.
or 
for each comparable pair 
. If we drop the restriction that 
-partitions, and it is not hard to see that in fact the definitions are equivalent. If feels most intuitive to me to state the definition as above.
denote the set of 
as in the example above, then the 
, the partitions with 
where 
is the total order refining 
where
and if 
and 
.) 
is in both 
and 
. Choose 
incomparable under 
. From 
we get 
we get 
. Therefore 
. Now using the labelling for the first time, we may suppose without loss of generality that 
, a contradiction. 
and 
are 
and 
is a poset, 
-partition is a function 
then 
in one-line form as 
. Recall that 
has a descent in position 
if 
.
, 
, 
. The total order 
of 
, with no descents. The total order 
corresponds under 
swapping 
.
be a total order refining 
and consider the elements 
of 
and 
. In any 
-partition 
, with strict inequality required if and only if 
. Therefore, using the total order 
, i.e. the function 
, we require 
for all 
in the permutation 
corresponding under 
appears left of 
whenever 
be a labelling. Then, using the labelling 
is the set of all functions 
such that 
above correspond to partitions whose 
th largest part is strictly more than their 
th largest part (which might be zero), and so are enumerated by
extensions of the partial order on ![[3,2]](https://s0.wp.com/latex.php?latex=%5B3%2C2%5D&bg=ffffff&fg=333333&s=0 "[3,2]")
, 
with descent sets 
, 
and comajor indices 
can be replaced with 
above.
enumerates partitions with at most 
). 
th largest part for all 
are enumerated in this sense by
be the number of compositions with 
is the number of descents of 
![\displaystyle \sum_{r=0}^\infty [r]_q^k t^r = \frac{\sum_\pi q^{\mathrm{maj}(\pi)} t^{\mathrm{des}(\pi)+1}}{(1-t)(1-qt)\ldots (1-q^k t)}](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Csum_%7Br%3D0%7D%5E%5Cinfty+%5Br%5D_q%5Ek+t%5Er+%3D+%5Cfrac%7B%5Csum_%5Cpi+q%5E%7B%5Cmathrm%7Bmaj%7D%28%5Cpi%29%7D+t%5E%7B%5Cmathrm%7Bdes%7D%28%5Cpi%29%2B1%7D%7D%7B%281-t%29%281-qt%29%5Cldots+%281-q%5Ek+t%29%7D&bg=ffffff&fg=333333&s=0 "\displaystyle \sum_{r=0}^\infty [r]_q^k t^r = \frac{\sum_\pi q^{\mathrm{maj}(\pi)} t^{\mathrm{des}(\pi)+1}}{(1-t)(1-qt)\ldots (1-q^k t)}")
![[r]_q = (q^r-1)/(q-1) = 1 + q + \cdots + q^{r-1}](https://s0.wp.com/latex.php?latex=%5Br%5D_q+%3D+%28q%5Er-1%29%2F%28q-1%29+%3D+1+%2B+q+%2B+%5Ccdots+%2B+q%5E%7Br-1%7D&bg=ffffff&fg=333333&s=0 "[r]_q = (q^r-1)/(q-1) = 1 + q + \cdots + q^{r-1}")
.
of size ![[\lambda]](https://s0.wp.com/latex.php?latex=%5B%5Clambda%5D&bg=ffffff&fg=333333&s=0 "[\lambda]")
ordered by (the transitive closure of) 
be the sum of the 
largest parts of ![L : [\lambda] \rightarrow \{1,\ldots, k\}](https://s0.wp.com/latex.php?latex=L+%3A+%5B%5Clambda%5D+%5Crightarrow+%5C%7B1%2C%5Cldots%2C+k%5C%7D&bg=ffffff&fg=333333&s=0 "L : [\lambda] \rightarrow \{1,\ldots, k\}")
so that the boxes in row 
. (This labelling was seen for 
in the example at the end of the previous part.) Since this label is all-natural, the 
appears to the left of both 
and 
in the one-line form of 
and 
. Therefore, when we put 
in the box of 
in the one-line form of 
. Therefore defining 
, where the sum is over all 
. (Warning: this is the definition from page 4 of 
is the set of standard tableaux of shape 
correspond to the permutations 
![[(3,2)]](https://s0.wp.com/latex.php?latex=%5B%283%2C2%29%5D&bg=ffffff&fg=333333&s=0 "[(3,2)]")
labelled 
.![\displaystyle \sum_{n=0}^\infty |\mathrm{RPP}_\lambda(n)|q^n = \frac{1}{\prod_{(a,b)\in[\lambda]} (1-q^{h_{(a,b)}})}](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Csum_%7Bn%3D0%7D%5E%5Cinfty+%7C%5Cmathrm%7BRPP%7D_%5Clambda%28n%29%7Cq%5En+%3D+%5Cfrac%7B1%7D%7B%5Cprod_%7B%28a%2Cb%29%5Cin%5B%5Clambda%5D%7D+%281-q%5E%7Bh_%7B%28a%2Cb%29%7D%7D%29%7D&bg=ffffff&fg=333333&s=0 "\displaystyle \sum_{n=0}^\infty |\mathrm{RPP}_\lambda(n)|q^n = \frac{1}{\prod_{(a,b)\in[\lambda]} (1-q^{h_{(a,b)}})}")
is the hook-length of the box ![(a,b) \in [\lambda]](https://s0.wp.com/latex.php?latex=%28a%2Cb%29+%5Cin+%5B%5Clambda%5D&bg=ffffff&fg=333333&s=0 "(a,b) \in [\lambda]")
. We saw the special cases for the partitions 
above.![\displaystyle \frac{1}{\prod_{(a,b)\in[\lambda]} (1-q^{h_{(a,b)}})} = \frac{\sum_{t \in \mathrm{SYT}(\lambda)} q^{\mathrm{comaj}(t)}}{(1-q)\ldots (1-q^k)}.](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Cfrac%7B1%7D%7B%5Cprod_%7B%28a%2Cb%29%5Cin%5B%5Clambda%5D%7D+%281-q%5E%7Bh_%7B%28a%2Cb%29%7D%7D%29%7D+%3D+%5Cfrac%7B%5Csum_%7Bt+%5Cin+%5Cmathrm%7BSYT%7D%28%5Clambda%29%7D+q%5E%7B%5Cmathrm%7Bcomaj%7D%28t%29%7D%7D%7B%281-q%29%5Cldots+%281-q%5Ek%29%7D.&bg=ffffff&fg=333333&s=0 "\displaystyle \frac{1}{\prod_{(a,b)\in[\lambda]} (1-q^{h_{(a,b)}})} = \frac{\sum_{t \in \mathrm{SYT}(\lambda)} q^{\mathrm{comaj}(t)}}{(1-q)\ldots (1-q^k)}.")
![[r]_q = (1-q^r)/(1-q)](https://s0.wp.com/latex.php?latex=%5Br%5D_q+%3D+%281-q%5Er%29%2F%281-q%29&bg=ffffff&fg=333333&s=0 "[r]_q = (1-q^r)/(1-q)")
and ![[k]!_q = [k]_q \ldots [1]_q](https://s0.wp.com/latex.php?latex=%5Bk%5D%21_q+%3D+%5Bk%5D_q+%5Cldots+%5B1%5D_q&bg=ffffff&fg=333333&s=0 "[k]!_q = [k]_q \ldots [1]_q")
, we have![\displaystyle \sum_{t \in \mathrm{SYT}(\lambda)} q^{\mathrm{comaj}(t)} = \frac{[k]!_q}{\prod_{(a,b) \in [\lambda]} [h_{(a,b)}]_q}.](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Csum_%7Bt+%5Cin+%5Cmathrm%7BSYT%7D%28%5Clambda%29%7D+q%5E%7B%5Cmathrm%7Bcomaj%7D%28t%29%7D+%3D+%5Cfrac%7B%5Bk%5D%21_q%7D%7B%5Cprod_%7B%28a%2Cb%29+%5Cin+%5B%5Clambda%5D%7D+%5Bh_%7B%28a%2Cb%29%7D%5D_q%7D.&bg=ffffff&fg=333333&s=0 "\displaystyle \sum_{t \in \mathrm{SYT}(\lambda)} q^{\mathrm{comaj}(t)} = \frac{[k]!_q}{\prod_{(a,b) \in [\lambda]} [h_{(a,b)}]_q}.")
to get![\displaystyle |\mathrm{SYT}(\lambda)| = \frac{k!}{\prod_{(a,b) \in [\lambda]} h_{(a,b)}}.](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%7C%5Cmathrm%7BSYT%7D%28%5Clambda%29%7C+%3D+%5Cfrac%7Bk%21%7D%7B%5Cprod_%7B%28a%2Cb%29+%5Cin+%5B%5Clambda%5D%7D+h_%7B%28a%2Cb%29%7D%7D.&bg=ffffff&fg=333333&s=0 "\displaystyle |\mathrm{SYT}(\lambda)| = \frac{k!}{\prod_{(a,b) \in [\lambda]} h_{(a,b)}}.")
in which two subsets are connected if and only if they intersect. 
to the evident interest of several potential students — and their parents, I had at most the outline of a fiddly solution that piled row operations on half-remembered determinantal identities.
be the nonempty subsets of 
matrix whose 
entry is
sets not having 
sets having 
for 
is the 
matrix with first column all zero and then 
to its right, and 
is the 
all-ones matrix. For example,
and zero row in 
are shown in bold. 
. We shall show, by induction on 
if 
. The 
matrix 
can be seen as a submatrix of 
above; computing the determinant as a sum over the 
, as required.
zeros (from the top row of 
) followed by 
). By row operations subtracting this row from each of the rows below, we obtain
. Therefore deleting this row and column, we find that
. Therefore 
can be computed explicitly: labelling rows and columns by subsets of 
is the complement of 
in 
of the poset of subsets of 
be the set of all subsets of 
be an infinite field. The vector space 
with basis 
on 
with 
. Let 
be the set of 
be the block of 
sending a 
has irreducible character canonically labelled by the partition 
. (Since 
has 
integer eigenvalues whose multiplicities are the dimensions of the 
. Varying 
, are the Catalan Numbers.
by the Specht modules 
, 
and 
one can show that the eigenvalues are 
, 
and 
, respectively. Computational data suggests that in general the eigenvalue associated to the partition 
is 
; probably this can be proved by a generalization of the filtration argument. (But maybe there is a better approach just using character theory.) Since the unique trivial submodule is spanned by the sum of all 
is simply the number of 
, namely 
.
be the generalization of the Putnam matrix where the entry remains zero for disjoint subsets, and if 
then the entry is 
. For example, 
is
, and 
is shown below, with rows and columns labelled 
, 
, 
, 
, 
, 
and 
to 
shown above. When 
is written as a sum over the 
permutations of the collection of non-empty subsets of 
, each summand factorizes as a product over the disjoint cycles in the corresponding permutation. If 
is such a cycle then the power of 
is 
(taking 
), and similarly the power of 
is 
. Clearly these are the same. Moreover, by the identity
,
. Therefore the determinant of the matrix a homogeneous polynomial in 
of degree 
. Since swapping 
, 
and 
. Therefore the determinant factorizes into homogeneous polynomials in 
(also degree 
and replace 
without losing any information. (This turns out to be the most convenient form for computation because, using MAGMA at least, it is fast to compute determinants of matrices whose coefficients lie in the single variable polynomial ring ![\mathbb{Q}[\tau]](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BQ%7D%5B%5Ctau%5D&bg=ffffff&fg=333333&s=0 "\mathbb{Q}[\tau]")
but much slower if the coefficients lie in ![\mathbb{Q}[\alpha,\beta,\tau]](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BQ%7D%5B%5Calpha%2C%5Cbeta%2C%5Ctau%5D&bg=ffffff&fg=333333&s=0 "\mathbb{Q}[\alpha,\beta,\tau]")
.) The determinants for small 
and for odd primes ![f_p \in \mathbb{Z}[\tau]](https://s0.wp.com/latex.php?latex=f_p+%5Cin+%5Cmathbb%7BZ%7D%5B%5Ctau%5D&bg=ffffff&fg=333333&s=0 "f_p \in \mathbb{Z}[\tau]")
of degree 
by 
. (The definition becomes uniform on changing 
.) For instance 
and
are
has degree 
in every case where it is defined, and that 
for all 
, for which 
. Assuming that this behaviour continues, and that 
always has exponent 
, let 
be the generalization of the Putnam matrix where if 
. When 
and 
for 
, the determinants are given by specializing the matrix above by 
, 
and 
, and so they are obtained from the factorizations in 
, 
for 
, 
, 
, 
, 
, 
. 
for each 
. For instance the matrix for 
is 
denotes 
denotes 
are 
in which the entries of the representing matrices are polynomials of a fixed degree in the four entries of each 
be the natural representation of 
itself is a polynomial representation of degree 
with basis 
is a polynomial representation of degree 
is a quotient of 
. More generally, any polynomial representation of degree 
. Observe that there is a linear isomorphism 
defined by 
on 
sends 
to 
, moving each factor one to the right (with wrap around). This gives some motivation for introducing the Schur algebra 
, defined to be the algebra of linear endomorphisms of the polynomial representation 
to the sum of all the pure tensors 
such that 
for at least one 
is 
-dimensional, and, since the image of 
recording how many elements were removed. This case is unusual in that the Schur algebra element comes from a single matrix in 
, as would be required for the Putnam matrix. Passing to the Schur algebra replaces the infinite dimensional algebra 
with probabilities 
, respectively. Let 
-tuple of symbols is then 
. Shannon’s Source Coding Theorem (or First Main Theorem, or Noiseless Coding Theorem) states that, given 
, provided 
that can be used to encode all 
. Let 
be the probabilities of the 
be least such that 
. Equivalently, 
is least such that 
. Another algorithmic construction is given by the proof of the sufficiency of the Kraft–McMillan inequality on page 17 of Welsh Codes and cryptography. (The same proof is indicated, rather less clearly in my view, on the 
be the probability space of symbols produced by the source. Let 
be a random symbol produced by the source. Then 
is a random variable. Summing over the ![\mathbb{E}[\log p(X)] = \sum_{i=1}^m \mathbb{P}[X=i] \log p(i) = \sum_{i=1}^m p(i) \log p(i) = -h](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BE%7D%5B%5Clog+p%28X%29%5D+%3D+%5Csum_%7Bi%3D1%7D%5Em+%5Cmathbb%7BP%7D%5BX%3Di%5D+%5Clog+p%28i%29+%3D++%5Csum_%7Bi%3D1%7D%5Em+p%28i%29+%5Clog+p%28i%29+%3D+-h&bg=ffffff&fg=333333&s=0 "\mathbb{E}[\log p(X)] = \sum_{i=1}^m \mathbb{P}[X=i] \log p(i) = \sum_{i=1}^m p(i) \log p(i) = -h")
is the entropy already seen. While straightforward, and giving some motivation for considering ![\mathbb{P}[\log p(X) = \log p(i)] = p(i)?](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BP%7D%5B%5Clog+p%28X%29+%3D+%5Clog+p%28i%29%5D+%3D+p%28i%29%3F&bg=ffffff&fg=333333&s=0 "\mathbb{P}[\log p(X) = \log p(i)] = p(i)?")
. (One further thing, that I certainly will not even dare to mention in my course, is that, by the formal definition of a random variable, 
, and so 
is a composition of two functions; in Example 2.3.1 of Goldie and Pinch Communication Theory the authors remark that forming such compositions is a ‘characteristic feature of information theory, not found elsewhere in probability theory’.) 
be a random ![P_r : \mathcal{M}^r \rightarrow [0,1]](https://s0.wp.com/latex.php?latex=P_r+%3A+%5Cmathcal%7BM%7D%5Er+%5Crightarrow+%5B0%2C1%5D&bg=ffffff&fg=333333&s=0 "P_r : \mathcal{M}^r \rightarrow [0,1]")
be defined by
is the probability that the first 
. Consider the random variable 
. By the displayed equation above,
. Hence, by the weak law, given any 
,![\displaystyle \mathbb{P}\Bigl[ -\frac{\log P_r\bigl( (X_1, \ldots, X_r) \bigr)}{r} \not\in (h-\eta, h+\eta) \Bigr] \rightarrow 0](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Cmathbb%7BP%7D%5CBigl%5B+-%5Cfrac%7B%5Clog+P_r%5Cbigl%28+%28X_1%2C+%5Cldots%2C+X_r%29+%5Cbigr%29%7D%7Br%7D+%5Cnot%5Cin+%28h-%5Ceta%2C+h%2B%5Ceta%29+%5CBigr%5D+%5Crightarrow+0&bg=ffffff&fg=333333&s=0 "\displaystyle \mathbb{P}\Bigl[ -\frac{\log P_r\bigl( (X_1, \ldots, X_r) \bigr)}{r} \not\in (h-\eta, h+\eta) \Bigr] \rightarrow 0")
. By taking 
, we obtain a subset 
of 
such that (a)![\mathbb{P}[(X_1,\ldots, X_r) \in \mathcal{T}] > 1 - \eta](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BP%7D%5B%28X_1%2C%5Cldots%2C+X_r%29+%5Cin+%5Cmathcal%7BT%7D%5D+%3E+1+-+%5Ceta&bg=ffffff&fg=333333&s=0 "\mathbb{P}[(X_1,\ldots, X_r) \in \mathcal{T}] > 1 - \eta")
then
then the most likely message is 
and the least likely is 
; unless the distribution is uniform, both are atypical when 
. Indeed, the proof of the AEP for memoryless sources on page 80 of Welsh Codes and cryptography takes this as the definition of ‘typical’ and uses the Central Limit Theorem to replace the weak law so that ‘about’ can be made precise.
is typical then 
![\begin{aligned} 1 &\ge \mathbb{P}[(X_1,\ldots, X_r) \in \mathcal{T}] \\ &= \sum_{(x_1,\ldots, x_r) \in \mathcal{T}} P_r\bigl( (x_1, \ldots, x_r) \bigr) \\ &\ge |\mathcal{T}| 2^{-r(H+ \eta)}.\end{aligned}](https://s0.wp.com/latex.php?latex=%5Cbegin%7Baligned%7D+1+%26%5Cge+%5Cmathbb%7BP%7D%5B%28X_1%2C%5Cldots%2C+X_r%29+%5Cin+%5Cmathcal%7BT%7D%5D+%5C%5C+%26%3D+%5Csum_%7B%28x_1%2C%5Cldots%2C+x_r%29+%5Cin+%5Cmathcal%7BT%7D%7D+P_r%5Cbigl%28+%28x_1%2C+%5Cldots%2C+x_r%29+%5Cbigr%29+%5C%5C+%26%5Cge+%7C%5Cmathcal%7BT%7D%7C+2%5E%7B-r%28H%2B+%5Ceta%29%7D.%5Cend%7Baligned%7D&bg=ffffff&fg=333333&s=0 "\begin{aligned} 1 &\ge \mathbb{P}[(X_1,\ldots, X_r) \in \mathcal{T}] \\ &= \sum_{(x_1,\ldots, x_r) \in \mathcal{T}} P_r\bigl( (x_1, \ldots, x_r) \bigr) \\ &\ge |\mathcal{T}| 2^{-r(H+ \eta)}.\end{aligned}")
. We may therefore encode all the typical messages using codewords of length 
. For the atypical messages we make no attempt at efficiency, and instead encode them using binary words of length 
for some 
, avoiding the prefixes already used for the typical words. Thus the code has (at most) two distinct lengths of codewords, and the expected length of a codeword is at most
;
.
is stationary if 
and 
have the same distribution for all 
and 
, and ergodic if with probability 
. Here is (one version of) the relevant result. Throughout let 
.
. Provided 
such that 
such that ![\mathbb{P}\bigl[d\bigl(f(S_1,\ldots, S_r), (S_1,\ldots, S_r)\bigr) > Dr\bigr] < \epsilon](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BP%7D%5Cbigl%5Bd%5Cbigl%28f%28S_1%2C%5Cldots%2C+S_r%29%2C+%28S_1%2C%5Cldots%2C+S_r%29%5Cbigr%29+%3E+Dr%5Cbigr%5D+%3C+%5Cepsilon&bg=ffffff&fg=333333&s=0 "\mathbb{P}\bigl[d\bigl(f(S_1,\ldots, S_r), (S_1,\ldots, S_r)\bigr) > Dr\bigr] < \epsilon")
.
, a random word emitted by the source can be encoded by a codeword in 
bits. Therefore each bit is correct with probability at least 
. By sending the number of a codeword we may therefore compress the source by a factor of 
, for every 
. Note that we assume 
, since if a bit error probability exceeding 
, so instead I claimed that one could compress by a factor of 
. The argument I had in mind was that by the AEP (or Shannon's Noiseless Coding Theorem) one can represent the typical words emitted by the source using all binary words of length 
. Then compress to 
bits by thinking of these binary words as emitted by an unbiased source, using the special case of the theorem above when 
. The problem is that decoding gives a bitwise error probability of 
on the binary words of length 
is minimized, subject to the constraint that the expectation of 
is 
.
. As a warm up, we use such codewords to prove the theorem in this special case.
and let 
be the probability that a codeword 
, chosen uniformly at random from 
. Since 
. Standard bounds show that
codewords uniformly at random, then the expected number of codewords within distance 
be as in the statement of the theorem above. Let 
say, can also be made less than 
such that, for this code, 
. Thus at least 
of all words in 
are within distance 
, the right construction in general would be to take such words and construct random codewords by randomly flipping 
and 
. Then flipping bits at random gives codewords of average weight 
be of weight 
. Then 
, and to pick a random code from words of this weight so that the expectated number of codewords close to 
, we could take 
as required. But because we are stuck in the bigger space of words of weight 
, we require a larger 
and 
is constant, a good — although maybe not very intuitive — way to do this is to choose the probabilities ![\mathbb{P}[X=\alpha|Y=\beta]](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BP%7D%5BX%3D%5Calpha%7CY%3D%5Cbeta%5D&bg=ffffff&fg=333333&s=0 "\mathbb{P}[X=\alpha|Y=\beta]")
to maximize 
, consistent with the requirements that if ![\mathbb{P}[Y=1] = q](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BP%7D%5BY%3D1%5D+%3D+q&bg=ffffff&fg=333333&s=0 "\mathbb{P}[Y=1] = q")
then ![(1-q)\mathbb{P}[X=0|Y=0] + q\mathbb{P}[X=0|Y=1] = p](https://s0.wp.com/latex.php?latex=%281-q%29%5Cmathbb%7BP%7D%5BX%3D0%7CY%3D0%5D+%2B+q%5Cmathbb%7BP%7D%5BX%3D0%7CY%3D1%5D+%3D+p&bg=ffffff&fg=333333&s=0 "(1-q)\mathbb{P}[X=0|Y=0] + q\mathbb{P}[X=0|Y=1] = p")
![(1-q)\mathbb{P}[X=1|Y=0] + q\mathbb{P}[X=0|Y=1] \le D.](https://s0.wp.com/latex.php?latex=%281-q%29%5Cmathbb%7BP%7D%5BX%3D1%7CY%3D0%5D+%2B+q%5Cmathbb%7BP%7D%5BX%3D0%7CY%3D1%5D+%5Cle+D.&bg=ffffff&fg=333333&s=0 "(1-q)\mathbb{P}[X=1|Y=0] + q\mathbb{P}[X=0|Y=1] \le D.")
![\mathbb{P}[X=1|Y=0] = \frac{D+p-q}{2(1-q)},\ \mathbb{P}[X=0|Y=1] = \frac{D+q-p}{2q}](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BP%7D%5BX%3D1%7CY%3D0%5D+%3D+%5Cfrac%7BD%2Bp-q%7D%7B2%281-q%29%7D%2C%5C+%5Cmathbb%7BP%7D%5BX%3D0%7CY%3D1%5D+%3D+%5Cfrac%7BD%2Bq-p%7D%7B2q%7D&bg=ffffff&fg=333333&s=0 "\mathbb{P}[X=1|Y=0] = \frac{D+p-q}{2(1-q)},\ \mathbb{P}[X=0|Y=1] = \frac{D+q-p}{2q}")
.
. Since ![H(X|Y) = (1-q) h(\mathbb{P}[X=1|Y=0]) + qh(\mathbb{P}[X=0|Y=1])](https://s0.wp.com/latex.php?latex=H%28X%7CY%29+%3D+%281-q%29+h%28%5Cmathbb%7BP%7D%5BX%3D1%7CY%3D0%5D%29+%2B+qh%28%5Cmathbb%7BP%7D%5BX%3D0%7CY%3D1%5D%29&bg=ffffff&fg=333333&s=0 "H(X|Y) = (1-q) h(\mathbb{P}[X=1|Y=0]) + qh(\mathbb{P}[X=0|Y=1])")
, substituting from the equations above gives a formula for 
.
and 
cancel, and one is left with the factoring quadratic
and both flip probabilities are 
, when ![\mathbb{P}[X=1|Y=0]=(D-Dp-p^2)/(1+D-3p)](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BP%7D%5BX%3D1%7CY%3D0%5D%3D%28D-Dp-p%5E2%29%2F%281%2BD-3p%29&bg=ffffff&fg=333333&s=0 "\mathbb{P}[X=1|Y=0]=(D-Dp-p^2)/(1+D-3p)")
and ![\mathbb{P}[X=0|Y=1]=p](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BP%7D%5BX%3D0%7CY%3D1%5D%3Dp&bg=ffffff&fg=333333&s=0 "\mathbb{P}[X=0|Y=1]=p")
. In the first solution the second derivative satisfies
, so the space of codewords is smaller than the space of source words. The extreme value is 
. Again this is somewhat intuitive: the minimum mutual information consistent with a distortion of 
probability distribution. But note that the distortion is applied to codewords, rather than words emitted by the source. (A related remark is given at the end of this post.)
and needed in the proof below.
and 
and the flip probabilities from 
and 
. The extreme value is 
.
, a condition equivalent to 
. In the example above 
and (by complete chance) ![\mathbb{P}[X=1|Y=0] = 0](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BP%7D%5BX%3D1%7CY%3D0%5D+%3D+0&bg=ffffff&fg=333333&s=0 "\mathbb{P}[X=1|Y=0] = 0")
and ![\mathbb{P}[X=0|Y=1] = \frac{1}{3}](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BP%7D%5BX%3D0%7CY%3D1%5D+%3D+%5Cfrac%7B1%7D%7B3%7D&bg=ffffff&fg=333333&s=0 "\mathbb{P}[X=0|Y=1] = \frac{1}{3}")
. The extreme value is 
.
as in the statement of the theorem. Choose codewords 
independently and uniformly at random from the binary words of length 
. Let 
. By the bounds above, the probability that a codeword of weight 
. 
and 
, we have 
. The end of the proof is therefore as before. 
source words of weight 
of the form 
is linear. If
and that 
is the width of 
. The keystream generated by 
is the sequence 
, where each 
for 
is defined recursively by
is close to the hardware implementation of an LFSR: fill 
and then repeatedly step by putting the sum of the bits 
for each 
into the rightmost register, shifting the other registers to the left. (In hardware, these bits would be ‘tapped’ by physical wires.) The keystream can be read off from the rightmost register. This interpretation makes it clear that an LFSR of width 
such that 
. One way to find 
, the matrix (acting on column vectors) representing 
. Thus 
if and only if 
divides 
. This may seem concise written here, but in practice it takes well over a lecture to remind students of matrices, find the matrix representing 
annihilates a power series 
if 
is a polynomial.
generates the keystream 
of period 
. The corresponding power series is
. But since 
for 
, it is also annihilated by 
. Correspondingly,
. Indeed, the coefficient of 
in the product is 
, and so 
is a polynomial of degree at most 
. Hence the period of 
such that 
. (This is equivalent to the condition found before by taking reciprocal polynomials.) 
, we claim that the equation 
defines a corresponding keystream. To avoid the need to define inverses in the ring of power series, let’s agree to interpret this equation as equivalent to
.
; clearly these equations have a unique solution. In particular, there is a keystream such that 
. (This holds even if the LFSR is not invertible.) It’s obvious that 
is annihilated only by the multiples of 
. In the invertible case we have seen that ![\mathbb{F}_2[x]](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BF%7D_2%5Bx%5D&bg=ffffff&fg=333333&s=0 "\mathbb{F}_2[x]")
-module is generated by 
. The period of the keystream for 
is therefore the period of 
of the LFSR of width 
and is annihilated by
. I plan to get students to find these taps by the slow method of solving the linear equations 
is a natural fit for the annihilator method. It is also clearly best for the Berlekamp—Massey algorithm.)
. I then showed that the keystreams of maximum possible period 
came from the LFSRs whose minimal polynomial is primitive. Of course most, quite reasonably, didn’t know what ‘primitive’ meant, but they could see Mathematica did, and that there was some underlying pattern related to the factorization of the minimal polynomial.![\mathbb{F}_2[X]](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BF%7D_2%5BX%5D&bg=ffffff&fg=333333&s=0 "\mathbb{F}_2[X]")
-module is ![\mathbb{F}_2[X]/\langle X^\ell + \sum_{t \in T} X_{\ell - t}\rangle.](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BF%7D_2%5BX%5D%2F%5Clangle+X%5E%5Cell+%2B+%5Csum_%7Bt+%5Cin+T%7D+X_%7B%5Cell+-+t%7D%5Crangle.&bg=ffffff&fg=333333&s=0 "\mathbb{F}_2[X]/\langle X^\ell + \sum_{t \in T} X_{\ell - t}\rangle.")
![\mathbb{F}_2[X]/\langle f_T(X) \rangle](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BF%7D_2%5BX%5D%2F%5Clangle+f_T%28X%29+%5Crangle&bg=ffffff&fg=333333&s=0 "\mathbb{F}_2[X]/\langle f_T(X) \rangle")
. When 
with 
, let 
. Thus the sequence 
starts 
. ![g(X) \in \mathbb{F}_2[X]](https://s0.wp.com/latex.php?latex=g%28X%29+%5Cin+%5Cmathbb%7BF%7D_2%5BX%5D&bg=ffffff&fg=333333&s=0 "g(X) \in \mathbb{F}_2[X]")
be an irreducible polynomial of degree ![\mathbb{F}_2[X]/g(X)](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BF%7D_2%5BX%5D%2Fg%28X%29&bg=ffffff&fg=333333&s=0 "\mathbb{F}_2[X]/g(X)")
.
. The orbits of ![\mathbb{F}_2[X]/g(X)^r](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BF%7D_2%5BX%5D%2Fg%28X%29%5Er&bg=ffffff&fg=333333&s=0 "\mathbb{F}_2[X]/g(X)^r")
not contained in the unique maximal ideal ![g(X)\mathbb{F}_2[X]/g(X)^r](https://s0.wp.com/latex.php?latex=g%28X%29%5Cmathbb%7BF%7D_2%5BX%5D%2Fg%28X%29%5Er&bg=ffffff&fg=333333&s=0 "g(X)\mathbb{F}_2[X]/g(X)^r")
have size 
and there are 
of them.
be the complement of the maximal ideal. By hypothesis, 
is divisible by 
. Since 
if and only if 
. Therefore 
in its action on 
then 
mod 
mod 
, the number of orbits is as claimed. ![\mathbb{F}_2[X]/g(X)^e](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BF%7D_2%5BX%5D%2Fg%28X%29%5Ee&bg=ffffff&fg=333333&s=0 "\mathbb{F}_2[X]/g(X)^e")
have sizes 
for 
. If 
then the number of orbits of size 
is 
. Suppose that 
we have 
and the count of orbits of size 
and 
orbits of size ![g(X)^{d-1} \mathbb{F}_2[X]/g(X)^d](https://s0.wp.com/latex.php?latex=g%28X%29%5E%7Bd-1%7D+%5Cmathbb%7BF%7D_2%5BX%5D%2Fg%28X%29%5Ed&bg=ffffff&fg=333333&s=0 "g(X)^{d-1} \mathbb{F}_2[X]/g(X)^d")
isomorphic to the finite field 
. Then 
, 
and the orbits of 
; 
; 
; 
, where the semicolons indicate the split according to 
. 
be the irreducible factorization of its feedback polynomial. Then the multiset of orbit sizes of 
, as given by the previous theorem.
, we see that the bitwise product of keystreams of invertible LFSRs with taps 
on keys 
is obtained by a linear operation (namely multiplication) on the tensors obtained by iterating 
, starting with 
. Define the set 
so that 
is the set of taps for an LFSR generating the product keystream.
and 
be roots of the feedback polynomials for 
. Hence the characteristic polynomial of 
for 
and 
. It follows that the feedback polynomial for the LFSR generating the product keystream has roots 
for the same 
. 
are coprime, the fields 
and 
together generate 
and so
.
and 
for the invertible full-period LFSRs with taps 
and 
has period 
. A computer algebra calculation shows that the minimal polynomial of 
is
,
. In this case the LFSR has minimal possible width, so the same set of taps is given by applying the Berlekamp–Massey algorithm to the product keystream. 
product are that 
for any 
for any 
, defined to be the set of taps of the LFSR of minimal width producing the product keystream, starting with the standard keys as above. In general the width will be smaller than 
: for example, this is the case whenever 
. It shares these nice features, and maybe deserves closer investigation, even though the general behaviour appears quite wild.
