Advanced Topics · Lesson 11

Cross-Borders

From one word to a pair

So far we studied borders of a single word. Many arguments — especially counting arguments — need the same idea between two words.

A border of a single word is the special case where the two ends belong to the same word; a cross-border is a shared bridge between the end of the first word and the start of the second.

The cross-borders are "ab". The shortest is "ab".

Here ab is a cross-border of (abab, abba): it ends abab and it begins abba. The word ab is also a border of abab — cross-borders reuse the suffix/prefix machinery you already know.

The shortest cross-border

The cross-borders are "001". The shortest is "001".

Both 0 and 001 are cross-borders of (001001, 00111). The shortest is 0.

Just as the shortest border of a single word has special structure, the shortest cross-border is always unbordered — it can never be “bridged again” from within.

A guided proof

The following theorem is the standard reason the shortest cross-border is useful: it gives a canonical, primitive bridge between two words.

Let’s prove it step by step. Suppose $x$ is the shortest cross-border of $(u, v)$ .

Theorem: The shortest cross-border of a pair (u, v) is unbordered.

Step 1
Suppose, for contradiction, that x is bordered. Let y be a nonempty proper border of x. Where does y sit inside x?
Step 2
Step 3
Step 4
Step 5

This argument is the template for several counting proofs: whenever two words share a shortest bridge, that bridge is primitive, and counting can treat it as an irreducible atom.

Counting pairs with no cross-border

Cross-borders matter most in counting. Let $C_{k} (n)$ be the number of ordered pairs $(u, v)$ of length- $n$ words over a $k$ -letter alphabet with no cross-border.

There are $k^{2 n}$ pairs in total. To subtract the pairs that do have a cross-border, classify each such pair by its shortest cross-border $x$ , which the theorem above guarantees is unbordered.

Fix an unbordered word $x$ of length $i$ . Write $u = u^{'} x$ and $v = x v^{'}$ , leaving $2 (n - i)$ free positions, so $k^{2 (n - i)}$ pairs have $x$ as a cross-border. Crucially, every such pair has shortest cross-border exactly $x$ : a cross-border shorter than $i$ would lie entirely inside $x$ and would be a border of $x$ , which is impossible because $x$ is unbordered. So the shortest cross-border partitions the pairs with a cross-border, and

C_{k} (n) = k^{2 n} - \sum_{i = 1}^{n} u_{k} (i) k^{2 (n - i)}

where $u_{k} (i)$ counts the unbordered words of length $i$ (Nielsen recurrence). For binary words:

C_{2} (1) = 4 - 2 = 2 C_{2} (2) = 16 - 2 \cdot 4 - 2 = 6 C_{2} (3) = 64 - 2 \cdot 16 - 2 \cdot 4 - 4 = 20

The formula works only because the classification uses the shortest cross-border. Classifying by an arbitrary cross-border would overcount: a pair with several cross-borders would be counted once per cross-border, and a non-shortest cross-border need not be unbordered, so the clean $u^{'} x, x v^{'}$ decomposition would break down. The shortest cross-border is the canonical, primitive bridge — exactly why we proved it is unbordered.

Practice

Order the borders

Arrange the borders of 1111 in increasing length. Pick each in order.

Classify unbordered words

Classify each word: unbordered or bordered?

Select the shortest border

Select the shortest border of 11101 on the word below.

Count the pairs with no cross-border

How many ordered pairs (u, v) of length 7 over a 2-letter alphabet have no cross-border?

Practice this topic →Every quiz from this lesson, at four difficulties.