Suppose we were to take a finite alphabet of letters, say , and we considered all the possible ‘words’ of a given length. For instance, the worlds of length 2 are:
and there are many of these. Let’s denote the set of length- words using the alphabet by .
What I am interested in now is “For a given and , what is the minimum length string of letters I can write down and still be sure that every word in appears somewhere in it as a substring?”. Why might I be interested in such a thing? Because I really should be working on my PhD, that’s why.
contains every length-2 word of 2 letters, in order 01, 11, 10, 00. It’s of optimal length, too, because if we start with just ’01’ and successively add ‘1’, ‘0’, and ‘0’, we find that at every stage the newly added letter creates a new sub-word not previously seen, and so every element of appears exactly once. We cannot delete a letter to make a shorter string without losing one of the words. Similarly,
are examples of optimal tours through and respectively, as they both have this property that each letter added after the first adds a previously unseen word.
Notice I’ve introduced the terminology tour for any string that contains all words in a given , with optimal tour being the tour that is of minimum possible length for that and .
To recap, we are attempting to find general solutions to the system of coupled Diophantine equations with the form:
We have already found that a solution is either compound (the concatenation of two shorter solutions), or it is simple (no consecutive subset is a solution to any shorter cycle). We have a canonical simple cycle, which for any pair is the -cycle given by
As we shall see in this third (and final) post, the canonical cycle is very significant in the classification of simple solutions, and hence of all solutions.
Recall the sum-product -cycle that we examined in this post. We seek simultaneous solutions to the coupled system of Diophantine equations
We found some particular instances of complete descriptions of , the set of equivalence classes of solutions (equivalence under commutation of the operations or of cyclic permutation of the indices ). Now we seek a more powerful machinery with which to find and classify solutions.
So in this post I’m going to talk a bit about a nice little number-theoretic problem that has been rattling around in my head a bit over the last few weeks. I’m essentially looking at the solutions (for each integer ) to a system of coupled second-order Diophantine equations. The equations involved have a nice internal symmetry and I have a couple of theorems giving a complete classification of the solutions for each – at least for positive integer solutions.
Let’s look at the prototypical equation we want to generalise:
Clearly the only viable solution to this is setting – it’s a very strong condition for two natural numbers to satisfy. However, it is a very aesthetically pleasing equation, so we would like to consider some extensions, and indeed a couple present themselves immediately.
One possible extension, which I am not going to consider here, is to find -tuples of positive integers which satisfy
((We observe immediately that the -tuple always works – but can you find how to generalise this to other -tuples? What about those guaranteed to contain a certain subset of positive integers ? What about finding the number of unique solutions for each ? You can read more about this in .))
The extension I will be looking at is the following: consider many Diophantine equations of the form
Does such a system of equations always have a solution? How many solutions are there for a given ? What structure exists on the set of solutions? Clearly the solutions themselves are invariant under pair commutation () and under cyclic permutation of the indices (). This kind of structure – where we have both an overall permutation of blocks and an underlying, independent permutation within each block – is realisable as the action of a wreath product on our space of objects. Let’s formalise this.
Let the many coupled Diophantine equations of the above form be called the sum-product -cycle, or just the -cycle. Let denote the set of -tuples of pairs of positive integers which satisfy the -cycle. That is,
Let denote the regular wreath product of , the permutation group of two elements, and , the group of integers modulo . Furthermore let elements of act upon with the primitive wreath action. We take the quotient space by this action,
to be our space of -cycle solutions.
And let’s immediately disregard this formalism for the time being. We need to focus first on coming to grips with what an -cycle is, and how it’s solved. Let’s look at some small- solutions. Continue reading
I was watching the Pirates of Penzance the other day and was reminded of a fantastic example of a constrained proof – a proof that is irrational set to the tune of the Major General’s Song that was written by Kevin Wald. Having nothing better to do I decided to memorise it. I also really like it as a proof, it’s nifty, but also incredibly easy, you could easily make it an assignment for a first-year calculus course.
Here are the lyrics, written by Kevin Wald and available here (I also recommend checking out some of the other things on his site – I particularly liked Cole Porter does Indo-European).
That pi must be irrational, I claim, is demonstratable:
Assume that with a quotient of whole numbers it’s equatable
Say, m o’er n. Define $a_k$, by fiat dictatorial,
For every natural k to be one over k factorial
Times integral from naught to pi of (n times (t)(pi – t))
To power k, times sine (or for you Latin scholars, sinus) t,
dt. These a’s are *positive*, with *finite sum* (indeed, it e-
Quals integral exp(n times (t)(pi – t)) sin t dt).
Chorus: It’s integral exp(n times (t)(pi – t)) sin t dt!
It’s integral exp(n times (t)(pi – t)) sin t dt!
It’s integral exp(n times (t)(pi – t)) sin t dt, dt!
But integrate by parts — each a’s the sum of the preceding two
Times integers, $a_naught$ is 2, $a_1$’s 4n, thus leading to
(since *all* must then be integers) a contradiction statable,
And thus that pi’s irrational, you see, is demonstratable!
Chorus: Since *all the a’s are integers*, a contradiction’s statable,
And thus that pi’s irrational, we see, is demonstratable! Continue reading