A circular sequence has no privileged starting point. The strings caba, abac, baca and acab can describe the same cycle, yet ordinary string comparison treats them as different. A useful canonical form is the lexicographically smallest rotation. Testing every rotation and sorting or comparing full strings can take quadratic work. Booth’s algorithm adapts prefix-failure reasoning so that one mismatch eliminates impossible starting positions and retains only a viable candidate. Mathematics matters because lexicographic order, borders and an elimination invariant prove that a circular object can be normalised in linear time.
The practical search question is not simply “what is this named method?” but “which mathematical structure makes the method work, what does it guarantee, and what evidence would show that it is a poor choice?” This article keeps those questions together so students can connect mathematics education with computing, engineering, data reasoning and careful everyday decisions without turning one technique into a career promise.
Quick navigation: Why it matters · Mechanism · Worked example · Deeper ideas · Investigations · Limits · Learning route · Parent guidance · FAQs · Sources
Why this mathematics matters
Mathematics is important here because it turns an apparently visual or computational trick into a chain of reasons. The representation tells us what information is kept. The equation or invariant explains each legal step. The complexity analysis describes the work. The boundary conditions say when a conclusion should not be trusted. That combination is a practical form of problem-solving literacy.
A strong learner should be able to move in both directions: from a real task to a mathematical model, and from a formal guarantee back to its real meaning. Naming an algorithm is not enough. The useful achievement is to explain why the next operation is valid, check a small instance independently, and notice which assumptions the implementation has added.
Source: Kellogg Booth’s 1980 paper “Lexicographically Least Circular Substrings”.
Primary or implementation reference: Theory of Computing Systems paper on lexicographically minimal rotation.
How the mechanism works
Represent every rotation as a length-n window in the doubled string s+s, but do not construct or compare all windows independently. Booth’s original linear-time method maintains a candidate starting index and a failure-function structure for the candidate’s matched prefix. As the scan advances, equal symbols extend the current border. At a mismatch, failure links test shorter borders; the comparison also reveals whether the current candidate or a later start is lexicographically worse. The worse starts are skipped because they share the already-compared prefix and cannot become minimum. Stop once enough doubled positions have been examined and return the surviving start modulo n.
For s of length n, rotation R_i is s[i..n−1]s[0..i−1]. Lexicographic order compares the first position at which two rotations differ. If R_i and R_j agree for ℓ positions and the next symbol of R_i is larger, then R_i is worse; the shared-prefix structure can also eliminate related starts inside that matched region. Failure links encode proper borders, allowing comparison state to fall back without rereading the whole prefix. Candidate advances and failure retreats are amortised across at most a constant multiple of n comparisons, so total time and auxiliary table space are O(n). Periodic strings may have several minimum start indices but the minimum rotation string is the same.
Keep a four-column notebook labelled object, rule, guarantee and caveat. In the first column name the inputs and stored state. In the second write one update precisely. In the third state what remains true after the update. In the fourth record a tie, approximation, domain restriction or hardware assumption. This routine prevents symbols from drifting away from their meaning.
Worked example and core calculations
Let s=bbaaccaadd, with indices 0 to 9. Its doubled form is bbaaccaaddbbaaccaadd. Any rotation beginning with b, c or d loses immediately to a rotation beginning with a, so only starts 2 and 3 remain initially plausible. Compare R2=aaccaaddbb with R3=accaaddbba: the first symbols tie, but the second symbols are a and c, so R2 is smaller and start 3 is eliminated. The later a at index 6 gives R6=aaddbbaacc; it ties R2 at the first two a symbols, then d is larger than c, so it also loses. The minimum rotation is aaccaaddbb, starting at index 2. Booth’s failure links organise these eliminations without materialising all ten rotations.
How to audit the calculation
- Recompute every intermediate value directly from the definition.
- Keep labels, indices, signs, units and normalisation visible.
- Test a case with a known exact answer.
- State tie rules, random seeds, tolerances and boundary conventions.
- Compare with a slower transparent baseline or trusted implementation.
- Separate agreement of numbers from suitability of the real-world model.
Small examples are not childish; they are diagnostic instruments. A five-line trace can reveal a reversed inequality, a missing scale factor or an inconsistent label convention before a large dataset hides the same error behind plausible output.
Four deeper ideas
Canonicalisation turns rotation equality into ordinary equality
If two cyclic strings use the same alphabet order and orientation, their minimum rotations can be compared directly as representatives.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
Did you know? Periodicity creates several valid starting indices
For s=abab, starts 0 and 2 produce the same minimum rotation abab. An API must say whether it returns the first, any or all minimum starts.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
Failure links preserve useful prefix evidence
The idea is related to KMP: a mismatch need not erase every character already shown equal.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
Alphabet order is part of the answer
Uppercase rules, Unicode collation, locale and token encodings can change which rotation is lexicographically least.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
Twelve practical investigations
1. Ten-character example
Repeat bbaaccaadd. Compare surviving a-starts.
What the mathematics reveals: Shared prefixes eliminate whole candidate ranges. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Keep original indices visible. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
2. Periodic string
Use abab. List minimum starts 0 and 2.
What the mathematics reveals: Canonical value can be unique while index is not. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: State the tie policy. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
3. All equal symbols
Use aaaa. Run the implementation.
What the mathematics reveals: Every start is equivalent. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Avoid an infinite fallback loop. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
4. Single symbol
Use z. Return index zero.
What the mathematics reveals: The smallest nonempty cycle is trivial. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Test n=1 explicitly. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
5. Empty input
Use an empty string. Apply the API contract.
What the mathematics reveals: Mathematics leaves a convention choice. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Do not take modulo zero. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
6. Reversal case
Compare abcd with dcba cycles. Normalise both orientations if required.
What the mathematics reveals: Rotation and dihedral equivalence differ. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Do not add reversal silently. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
7. Unicode form
Use composed and decomposed accents. Normalise first.
What the mathematics reveals: Code-point equality can differ from visual equality. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Record the normalisation form. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
8. Case-insensitive order
Fold case consistently. Recompute the representative.
What the mathematics reveals: Comparison rules shape the canonical form. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Locale can alter case mapping. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
9. Token cycle
Use a sequence of labels rather than characters. Supply a total comparator.
What the mathematics reveals: The method applies to ordered symbols. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Object identity needs stable labels. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
10. Polygon boundary code
Encode a cyclic turn sequence. Normalise its starting edge.
What the mathematics reveals: Circular descriptions gain a canonical start. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Orientation and geometric tolerance remain separate. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
11. Naive baseline
Enumerate all small rotations. Compare returned value.
What the mathematics reveals: A quadratic oracle checks small instances. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Do not benchmark only random strings. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
12. Property testing
Rotate random strings before normalising. Expect the same canonical value.
What the mathematics reveals: Rotation invariance is a powerful property. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Retain seeds and tie rules. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
Limits and misconceptions
Booth’s algorithm answers a precise one-directional rotation problem. It does not automatically treat reversed cycles as equivalent; necklaces that identify reflection as well as rotation need a second orientation check. An empty string requires a declared convention. Periodic strings can have multiple minimum indices. Lexicographic order must be stable and total, which is not automatic for locale-sensitive human text. Unicode normalisation should precede comparison when visually equivalent sequences may have different code points. Canonical forms help equality testing but do not prove that two graphs, molecules or polygons are isomorphic unless the chosen circular encoding itself is complete and invariant. A standard library implementation may use Duval or another linear method instead.
Five misconceptions to challenge
- The algorithm sorts all rotations: It eliminates candidates without materialising every rotation.
- A circular string always has one minimum start: Periodic strings can have several.
- Rotation equality includes reversal: Reflection is a separate equivalence.
- Lexicographic minimum is independent of encoding: Alphabet and collation choices affect it.
- A shared canonical string proves any represented objects are identical: Only a complete representation justifies that conclusion.
Another broad misconception is that advanced mathematics automatically creates intelligence, admission, income or employment. It does not. Deliberate study can strengthen modelling, abstraction, calculation and explanation, while real pathways also depend on interests, communication, domain knowledge, opportunities and circumstances outside one topic.
A learning route for students
Move from a visible trace to a symbolic rule, then to code and critique. For every step below, prepare three pieces of evidence: a correct hand example, a boundary or failure case, and a short explanation using the relevant invariant. Do not advance merely because software returned a number.
Step 1: Enumerate circular rotations
Begin with the smallest non-trivial instance that lets you enumerate circular rotations. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 2: Compare strings lexicographically
Begin with the smallest non-trivial instance that lets you compare strings lexicographically. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 3: Identify periodic ties
Begin with the smallest non-trivial instance that lets you identify periodic ties. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 4: Trace failure links
Begin with the smallest non-trivial instance that lets you trace failure links. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 5: State the candidate invariant
Begin with the smallest non-trivial instance that lets you state the candidate invariant. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 6: Prove rotation invariance
Begin with the smallest non-trivial instance that lets you prove rotation invariance. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 7: Analyse linear amortised work
Begin with the smallest non-trivial instance that lets you analyse linear amortised work. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 8: Define an alphabet order
Begin with the smallest non-trivial instance that lets you define an alphabet order. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 9: Separate rotation from reflection
Begin with the smallest non-trivial instance that lets you separate rotation from reflection. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 10: Test against exhaustive enumeration
Begin with the smallest non-trivial instance that lets you test against exhaustive enumeration. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
A four-week practice plan
- Week 1 — vocabulary and diagrams: define each object, redraw the mechanism and reproduce the worked example.
- Week 2 — equations and manufactured tests: derive the key relation and test inputs with known answers.
- Week 3 — implementation and evidence: use a trusted library, record parameters and compare with a transparent baseline.
- Week 4 — transfer and critique: apply the method to a new context, report limits and identify when a different method is better.
Guidance for parents and educators
Ask “what stays true?” and “what could make this conclusion fail?” before asking for speed. Invite the student to draw the input and output, estimate the result and locate the first step that disagrees with a reference. These prompts reveal conceptual understanding more clearly than memorised terminology.
Advanced enrichment should sit beside secure school foundations in algebra, functions, geometry, statistics and computational thinking. It need not accelerate a student into a fixed career identity. A healthy goal is curiosity with discipline: the learner becomes comfortable reading unfamiliar notation, checking an example, revising a model and communicating uncertainty.
Evidence prompts for a useful conversation
- Which quantity is observed and which is inferred?
- Which step saves work, and why is it allowed?
- Is the claim exact, approximate, probabilistic or empirical?
- What units and conventions are in use?
- Which input makes the method struggle?
- What simple baseline could check the answer?
- What would count as evidence that the parameters are poor?
Mini-project assessment
A strong mini-project contains the original question, a small reproducible dataset, a hand-worked example, code or a spreadsheet trace, at least one boundary test, a comparison with a baseline, and a paragraph on limits. Assess the reasoning trail as well as the final output. Repairing a model after a surprising result is valuable mathematical progress.
Six evidence checks for a finished project
Check 1: Enumerate circular rotations
Ask the student to demonstrate how to enumerate circular rotations without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 2: Compare strings lexicographically
Ask the student to demonstrate how to compare strings lexicographically without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 3: Identify periodic ties
Ask the student to demonstrate how to identify periodic ties without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 4: Trace failure links
Ask the student to demonstrate how to trace failure links without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 5: State the candidate invariant
Ask the student to demonstrate how to state the candidate invariant without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 6: Prove rotation invariance
Ask the student to demonstrate how to prove rotation invariance without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Frequently asked questions
What does Booth’s algorithm find?
The starting index of a lexicographically minimum rotation.
What is a string rotation?
Moving a prefix to the end while preserving circular order.
Why double the string?
Every rotation becomes a length-n window.
What is the runtime?
O(n).
Can several starts be minimum?
Yes, for periodic strings.
Does it handle reversal equivalence?
Not by itself.
Is it related to KMP?
Yes; the classical method adapts failure-function reasoning.
What about Unicode text?
Define normalisation and collation first.
Why is canonicalisation useful?
It lets cyclic representations be compared through a consistent start.
What should students know first?
Strings, indices, prefixes, modulo arithmetic and lexicographic order.
Useful next reading and sources
Source: Kellogg Booth’s 1980 paper “Lexicographically Least Circular Substrings”.
Source: Theory of Computing Systems paper on lexicographically minimal rotation.
Related eduKateSG reading: Knuth–Morris–Pratt prefix functions.
Related eduKateSG reading: Boyer–Moore search and text skips.
Related eduKateSG reading: Aho–Corasick multi-pattern automata.
Read sources with a question in mind: which definition, theorem, default or limitation is being supported? An authoritative link is useful evidence, but it does not replace a worked calculation or a clear statement of how the source applies to the example.
A cheerful final thought
Mathematics becomes friendlier when every symbol has a job and every claim has a boundary. Start small, make the state visible, test the awkward case, and celebrate the moment when a pattern becomes explainable. That is the practical benefit of learning mathematics: not certainty about every future, but a growing ability to ask better questions and build trustworthy answers.