Tagged: Fun

Complete Word Tours

Suppose we were to take a finite alphabet \mathbb{A}_n of n letters, say \{ 0, 1, \ldots, n-1\}, and we considered all the possible ‘words’ of a given length. For instance, the worlds of length 2 are:

\{00, 01, \ldots, 0(n-1), 10, 11, \ldots, (n-1)(n-1)\}

and there are n^2 many of these. Let’s denote the set of length-m words using the alphabet \mathbb{A}_n by \mathbb{W}^m_n.

What I am interested in now is “For a given n and m, what is the minimum length string of letters I can write down and still be sure that every word in \mathbb{W}^m_n 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.

Example:

01100

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 \mathbb{W}^2_2 appears exactly once. We cannot delete a letter to make a shorter string without losing one of the words. Similarly,

0011101000

and

0201221100

are examples of optimal tours through \mathbb{W}^3_2 and \mathbb{W}^2_3 respectively, as they both have this property that each letter added after the first m adds a previously unseen word.

Notice I’ve introduced the terminology tour for any string \tau that contains all words in a given \mathbb{W}^m_n, with optimal tour being the tour \tau^m_n that is of minimum possible length for that m and n.

Continue reading

Sum-Product Cycles of Positive Integers Pt. 3

To recap, we are attempting to find general solutions to the system of n coupled Diophantine equations with the form:

x_1 + y_1 = x_2 y_2

x_2 + y_2 = x_3 y_3

\vdots

x_n + y_n = x_1 y_1 .

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 (i, j) is the (i - 1)(j - 1)-cycle given by

[(i, j)]_{Can} = [(i, j), (1, i+j), (1, i+j+1), \ldots, (1, ij-1)]

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.

Continue reading

Sum-Product Cycles of Positive Integers Pt. 2

Recall the sum-product n-cycle that we examined in this post. We seek simultaneous solutions to the coupled system of n Diophantine equations

x_1 + y_1 = x_2 y_2

x_2 + y_2 = x_3 y_3

\vdots

x_n + y_n = x_1 y_1.

We found some particular instances of complete descriptions of B_n, the set of equivalence classes of solutions (equivalence under commutation of the operations or of cyclic permutation of the indices i = 1, 2, \ldots, n). Now we seek a more powerful machinery with which to find and classify solutions.

Continue reading

Sum-Product Cycles of Positive Integers

Introduction

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 n) to a system of n 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 n – at least for positive integer solutions.

Let’s look at the prototypical equation we want to generalise:

a + b = ab \qquad a, b \in \mathbb{Z}^+.

Clearly the only viable solution to this is setting (a, b) = (2, 2) – 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 n-tuples of positive integers (x_1, x_2, \ldots, x_n) which satisfy

\sum_{i = 1}^n x_i = \prod_{i = 1}^n x_i.

((We observe immediately that the n-tuple (1, 1, \ldots, 1, 2, n) always works – but can you find how to generalise this to other n-tuples? What about those guaranteed to contain a certain subset of positive integers \{x_i, x_j, \ldots, x_k\}? What about finding the number of unique solutions for each n? You can read more about this in [1].))

The extension I will be looking at is the following: consider n many Diophantine equations of the form

x_1 + y_1 = x_2 y_2

x_2 + y_2 = x_3 y_3

\vdots

x_n + y_n = x_1 y_1.

Does such a system of equations always have a solution? How many solutions are there for a given n? What structure exists on the set of solutions? Clearly the solutions themselves are invariant under pair commutation ((x_i, y_i) \mapsto (y_i, x_i)) and under cyclic permutation of the indices (i \mapsto i + k (\mathrm{mod})_n). 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.

Definition 1

Let the n many coupled Diophantine equations of the above form be called the sum-product n-cycle, or just the n-cycle. Let A_n denote the set of n-tuples of pairs of positive integers which satisfy the n-cycle. That is,

A_n \subseteq ((\mathbb{Z}^+)^2)^n.

Let \Omega = S_2 \wr \mathbb{Z}_n denote the regular wreath product of S_n, the permutation group of two elements, and \mathbb{Z}_n, the group of integers modulo n. Furthermore let elements of \Omega act upon A_n with the primitive wreath action. We take the quotient space by this action,

B_n = A_n / \Omega,

to be our space of n-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 n-cycle is, and how it’s solved. Let’s look at some small-n solutions. Continue reading

The Pi Proof of Penzance

I was watching the Pirates of Penzance the other day and was reminded of a fantastic example of a constrained proof – a proof that \pi 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,

"And it is, it is, a glorious thing to be a mathematician"

“And it is, it is, a glorious thing to be a mathematician”

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