The Secret of the Raffle Function (epic proof) - Numberphile

Key Concepts:

• Raffle Function (r(n)): The number of tickets with the number 'n' written on them in an infinite raffle where the sum of tickets with divisors of 'n' equals 'n'.
• Natural Number: A positive integer (1, 2, 3, 4...).
• Divisor: A number that divides another number evenly.
• Prime Power Factorization: Expressing a number as a product of prime numbers raised to certain powers.
• Arithmetic Function: A function whose input is a natural number and whose output is a real or complex number.
• Multiplicative Function: An arithmetic function f(n) where f(a*b) = f(a) * f(b) for all co-prime numbers a and b.
• Co-prime (Relatively Prime): Two numbers that share no common divisors other than 1.
• Strongly Multiplicative Function: An arithmetic function f(n) where f(a*b) = f(a) * f(b) for all natural numbers a and b.
• Constant Function: A function that always returns the same value, regardless of the input.
• Zero Function: A constant function that always returns 0.
• One Function (Iota Function): A constant function that always returns 1.
• Epsilon Function: A function that returns 1 if the input is 1, and 0 otherwise.
• Dirichlet Product (Dirichlet Convolution): An operation on two arithmetic functions f and g, denoted by (f * g)(n) = Σ f(d)g(n/d), where the sum is over all divisors d of n.
• Sum Function (S_f(n)): A function derived from another function f(n) by summing the values of f(d) for all divisors d of n. S_f(n) = Σ f(d)
• Identity Function: A function that returns the same value as its input (f(x) = x).
• Mobius Function (μ(n)): The Dirichlet inverse of the iota function. It is 1 if n=1, (-1)^k if n is a product of k distinct primes, and 0 if n has a squared prime factor.
• Mobius Inversion Formula: A formula that expresses an arithmetic function in terms of its sum function using the Mobius function.
• Square-Free Number: A number that is not divisible by any perfect square other than 1.
• Euler's Totient Function (φ(n)): The number of positive integers less than or equal to n that are relatively prime to n.

1. The Raffle Function and Its Definition

• The video introduces the "raffle function," denoted as r(n), which represents the number of tickets with the number 'n' written on them in a hypothetical infinite raffle.
• The key rule governing this raffle is that for any number 'n', the sum of the number of tickets bearing the divisors of 'n' must equal 'n' itself.
• Example: For n=6, the divisors are 1, 2, 3, and 6. Therefore, r(1) + r(2) + r(3) + r(6) = 6.
• Example: For n=4, the divisors are 1, 2, and 4. Therefore, r(1) + r(2) + r(4) = 4.
• The central question is whether every number will be represented in the raffle, and if so, how many tickets will bear that number.

2. Exploring the Raffle Function with Simple Numbers

• The video starts by evaluating the raffle function for small natural numbers to identify patterns.
• r(1) = 1, because 1 is only divisible by itself.
• r(2) = 1, because r(1) + r(2) = 2, and r(1) = 1.
• r(3) = 2, because r(1) + r(3) = 3, and r(1) = 1.
• r(4) = 2, because r(1) + r(2) + r(4) = 4, and r(1) = 1, r(2) = 1.
• r(5) = 4, because r(1) + r(5) = 5, and r(1) = 1.
• r(6) = 2, derived from the initial example.
• A pattern emerges: for prime numbers 'p', r(p) = p - 1.

3. The Multiplicative Property Hypothesis

• The video explores the possibility that the raffle function is multiplicative, meaning r(a*b) = r(a) * r(b) if 'a' and 'b' are co-prime.
• Example: r(6) = 2, and r(2) * r(3) = 1 * 2 = 2, supporting the hypothesis.
• Example: r(10) = 4, and r(2) * r(5) = 1 * 4 = 4, further supporting the hypothesis.
• The multiplicative property is proven for the case where n is the product of two distinct primes, p and q. The divisors of pq are 1, p, q, and pq. Therefore, r(1) + r(p) + r(q) + r(pq) = pq. Since r(1) = 1, r(p) = p-1, and r(q) = q-1, it follows that r(pq) = pq - (p-1) - (q-1) - 1 = (p-1)(q-1) = r(p)r(q).
• However, the raffle function is not strongly multiplicative, as r(4) ≠ r(2) * r(2).

4. Arithmetic Functions and Multiplicativity

• The video introduces the concept of arithmetic functions, which are functions that take natural numbers as input and return real or complex numbers.
• Multiplicative functions are a subset of arithmetic functions that satisfy the property f(a*b) = f(a) * f(b) for co-prime numbers 'a' and 'b'.
• Strongly multiplicative functions satisfy this property for all natural numbers 'a' and 'b'.
• Examples of multiplicative functions:
  • τ(n) (tau of n): the number of divisors of n.
  • σ(n) (sigma of n): the sum of the divisors of n.
• Constant functions (f(n) = c) are only multiplicative if c = 0 or c = 1. The constant function 1 is also called the iota function.

5. Operations on Functions: Dirichlet Product

• The video introduces the Dirichlet product (or Dirichlet convolution), a special type of multiplication for arithmetic functions.
• The Dirichlet product of two functions f and g is defined as (f * g)(n) = Σ f(d)g(n/d), where the sum is taken over all divisors 'd' of 'n'.
• The epsilon function (ε(n)) is defined as 1 if n = 1 and 0 otherwise. It acts as the identity element for the Dirichlet product, meaning (f * ε)(n) = f(n).
• The sum function of f, denoted S_f(n), is defined as the sum of f(d) over all divisors d of n. This can be expressed as S_f(n) = (f * ι)(n), where ι is the iota function (the constant function 1).

6. Chains of Functions and the Sum Function

• The video explores how different functions are related through the sum function and Dirichlet product.
• S_ε(n) = ι(n) (the sum function of the epsilon function is the iota function).
• S_ι(n) = τ(n) (the sum function of the iota function is the number of divisors function).
• S_id(n) = σ(n) (the sum function of the identity function is the sum of divisors function).
• A crucial finding is that S_r(n) = id(n) (the sum function of the raffle function is the identity function). This is a restatement of the original definition of the raffle function.

7. Dirichlet Inverse and the Mobius Function

• The video discusses the concept of a Dirichlet inverse. The Dirichlet inverse of a function f is a function f^-1 such that (f * f^-1)(n) = ε(n).
• The Mobius function (μ(n)) is defined as the Dirichlet inverse of the iota function (ι). Therefore, (μ * ι)(n) = ε(n).
• The Mobius function takes on three values:
  • μ(1) = 1
  • μ(n) = (-1)^k if n is a product of k distinct primes (square-free).
  • μ(n) = 0 if n is not square-free (i.e., it has a squared prime factor).

8. Mobius Inversion Formula and Solving for the Raffle Function

• The Mobius inversion formula is used to isolate the raffle function. Since (r * ι)(n) = id(n), convolving both sides with the Mobius function gives (μ * (r * ι))(n) = (μ * id)(n).
• Using the associative property of the Dirichlet product, this becomes ((μ * ι) * r)(n) = (μ * id)(n).
• Since (μ * ι)(n) = ε(n), we have (ε * r)(n) = (μ * id)(n).
• Finally, since (ε * r)(n) = r(n), we get r(n) = (μ * id)(n). This means the raffle function is the Dirichlet product of the Mobius function and the identity function.

9. The Raffle Function is Multiplicative and Equal to Euler's Totient Function

• Since the Mobius function and the identity function are both multiplicative, their Dirichlet product (the raffle function) is also multiplicative.
• This allows the raffle function to be expressed as a product over prime powers: r(n) = n * Π (1 - 1/p), where the product is taken over all distinct prime divisors 'p' of 'n'.
• This formula is recognized as Euler's totient function (φ(n)), which counts the number of positive integers less than or equal to 'n' that are relatively prime to 'n'.
• Therefore, the raffle function is equal to Euler's totient function: r(n) = φ(n).

10. Applying the Formula and Conclusion

• The video applies the derived formula to calculate r(42) and r(2024).
• r(42) = 42 * (1 - 1/2) * (1 - 1/3) * (1 - 1/7) = 12.
• r(2024) = 2024 * (1 - 1/2) * (1 - 1/11) * (1 - 1/23) = 880.
• The video concludes by emphasizing that the original problem, which seemed complex, was solved by enlarging the problem to the multiplicative land, exploring properties of arithmetic functions, and using the Mobius inversion formula. The raffle function, initially defined in a convoluted way, turned out to be a well-known function: Euler's totient function.

Main Takeaways:

• The video demonstrates a powerful problem-solving technique: enlarging a problem to a more general setting (in this case, the world of multiplicative functions) to gain insights and find a solution.
• The Dirichlet product and the Mobius inversion formula are powerful tools for working with arithmetic functions.
• The raffle function, initially presented as a mysterious concept, is equivalent to Euler's totient function, highlighting the interconnectedness of mathematical concepts.