AI summary by TwinMind
The Frobenius Problem (and numerical semigroups) - Numberphile
Numberphile
18m 54s
Introduction to Numerical Semigroups
- Definition: Fancy name for something very simple
- Basic example: Numbers 2 and 3
- Can write every number starting with 2 using multiples of 2 plus multiples of 3
- Examples: 4 = 2×2, 5 = 2+3, 6 = 3+3, 7 = 2+2+3
Two-Number Case: 3 and 5
- Gaps identified: 1, 2, 4, 7 cannot be represented
- Can generate: 3, 5, 6 (3+3), 8 (3+5), 9 (3+3+3), 10 (5+5), 11 (3+3+5)
- Pattern continues forever for relatively prime integers
- Counter-example: 2 and 4 only generate even numbers (miss 1, 3, 5, 7...)
- Relatively prime definition: No prime number divides both
- 3 and 5 are relatively prime
- 2 and 4 are not (both divisible by 2)
Sylvester's Theorem
- Historical context: JJ Sylvester's contribution
- Theorem statement: For relatively prime positive integers a and b, starting from certain point every number can be written as combination of a's and b's
- Formula for starting point: (a-1) × (b-1)
- Examples:
- 2 and 3: starts at 2
- 3 and 5: starts at 8 (2×4)
- Frobenius number: (a-1)(b-1) - 1
- No number smaller than (a-1)(b-1) can be guaranteed representable
Three-Number Problem and Open Questions
- Three relatively prime numbers a, b, c: magic number X exists but unknown
- No one knows formula for smallest X (conductor)
- Frobenius number problem: major unsolved problem
- Literature includes:
- Upper/lower bounds research
- Vladimir Arnold wrote 3 papers on subject
- Connected to continued fractions
- Example calculation 4, 6, 7:
- Upper bound: 3×6 = 18
- Can generate: 8, 10, 11, 12, 13
- Frobenius number: 9 (biggest ungeneratable)
- No polynomial formula exists for three numbers
- Algorithm exists but no closed formula
- Situation worsens with more numbers (4, 37, 562...)
Chicken McNuggets Connection
- Same mathematical problem
- Example: Ordering 43 McNuggets using available pack sizes
Systematic Approach: Multiplicity and Residues
- Multiplicity: smallest number in generating set
- Key insight: Must get every residue mod multiplicity
- Example with 3 and 5:
- Multiplicity = 3
- Track residues: 5 has residue 2, 6 has residue 0, 8 has residue 2, 9 has residue 0, 10 has residue 1
- Once all residues (0, 1, 2) obtained, generation complete
- Frobenius number = (last residue position) - multiplicity = 10 - 3 = 7
Kunz's Coordinate System
- Ernst Kunz's systematic classification
- Each semigroup gets coordinates in space
- Semigroup (3,5): coordinates (10, 5) - first appearances of residues 1 and 2
- Semigroup (3,7): coordinates (7, 14) - first appearances of residues 1 and 2
- Dimension = multiplicity - 1
- Called "Apéry set" or "upper set" (after French mathematician)
- More systematic than working with generating sets
Group Theory Foundation
- Multiplication by relatively prime number creates permutation
- Example: multiply by 7 modulo 5
- 0→0, 1→2, 2→4, 3→1, 4→3
- All residues appear exactly once
- General principle: relatively prime multiplication gives all residues
- Cannot get same residue twice (would violate relative primeness)
Sylvester's Theorem Proof Sketch
- Example: 5 and 7, conductor should be 4×6 = 24, Frobenius number = 23
- Track residue appearances:
- 5 gives residue 0
- 7 gives residue 2
- 14 gives residue 4
- 21 gives residue 1
- 28 gives residue 3
- All 5 residues obtained by position 28
- 23 definitely not in semigroup (otherwise 28 wouldn't be first residue 3)
- Any number > 23 has known residue, can be generated by adding multiple of 5 to earlier number
- Generalizes to prove Sylvester's theorem for any a, b
Advanced Applications: Riemann Surfaces
- Riemann surface: donut-like surface with holes
- Genus = number of holes (e.g., genus 3 = 3 holes)
- Complex analytic functions defined on surface
- Weierstrass points: special points with different pole behavior
- Weierstrass semigroup: possible pole orders at these points
- Open question: which semigroups can occur as Weierstrass semigroups
- Historical confusion:
- 1890s: question posed
- Early proof claimed not all semigroups occur (wrong)
- Definitive text claimed all semigroups occur (also wrong)
- 1980s: Ragnar Buchweitz produced counterexample semigroup
- Proof by exhibition using Riemann-Roch theorem constraints
