0:005:45

Recursos

Resumen

Take any piece of a typical totient preimage and say how the paper counts it, and why that gives each totient value exactly one count. That one move explains where V(x) ~ (x/log x) · G_m · A(1;θ) comes from and why V(cx)/V(x) → c.

The problem

Different integers can have the same totient: φ(7) = φ(9) = φ(14) = φ(18) = 6 [0:00]. That means counting values is not counting integers [0:09]. The prime number theorem gives a floor of about x/log x. Ford's 1998 estimate pins V(x) down only up to a bounded factor e^{O(1)}. A bounded factor cannot decide the Erdős–Hall question of whether V(cx)/V(x) → c [0:29].

The result and where it comes from

V(x) is asymptotic to x/log x times Ford's scale G_m times A(1;θ) [0:53]. Here θ ∈ [0,1) is a phase, and A lies between two positive constants. A is a uniform limit of coefficients A_H built from finite arithmetic data, and its definition never uses V.

Write a preimage as p₀ · p₁⋯p_R · p_{R+1}⋯p_L · a, with the primes in decreasing order and cuts at R = m − H and L = m − P [1:48]:

  • p₀ (largest prime): counted by the prime number theorem. This is where the weight 1/d comes from.
  • Prefix p₁…p_R: the double logarithms lie in Ford's simplex, so this part is counted by volume (the sand of the beach).
  • Tail p_{R+1}…p_L, a: for fixed H these primes stay bounded, so they are kept exact (the boulders).

Why each value counts once

  • The prefix is unique [2:43]. Take two tuples with the same value. Go to the first index where their primes differ and cancel the common part. What remains is an equation between products of shifted primes. The layered comparison of Maier–Pomerance and Ford compares these products one layer at a time, with a sieve on only two or three linear forms. Collisions add up to at most ε_H times the scale, and ε_H → 0. Note that this is uniqueness of the prefix, not of the whole preimage.
  • Tails are combined by a union [3:46]. Each tail witness allows a region of prefix points. When two witnesses share a totient d, adding their volumes counts the overlap twice. The correct quantity is the volume of the union [4:14]. An intersection imposes the larger threshold at each coordinate, so inclusion–exclusion gives formula (2.8): an alternating sum over subsets T with max D inside an exponential.
  • Fixed dilation [4:49]. The paper counts the same representations at x and at x/c, with every parameter formed from x. Subtracting leaves only error terms that vanish, so no continuity of A is needed.

Rule to keep: sort the preimage. Count the largest prime with the prime number theorem, count the long prefix by volume (made unique by comparison), and count the short tail exactly through a union [5:16].

Counting totient values: Ford's asymptotic refined

OpenAI Math Preprints

Clase 50 / 100

Ver clases