The Restricted Table

The multiplication table problem asks: how many distinct products appear when you multiply all integers up to N? Erdős showed in 1955 that the answer is surprisingly small — most products in the N×N table are duplicates. Ford resolved the exact order of magnitude in 2008.

But what happens when you restrict which primes are allowed?

Fix a set Q of primes with a specific density δ among all primes. Count the integers up to x composed entirely of primes from Q, then ask: how many of these integers have a divisor in the interval (y, 2y]? This is the restricted multiplication table problem — counting the distinct entries that survive when you filter the prime factors.

The answer exhibits a phase transition at the critical density δ = 1/log 4.

Below this threshold, the restricted table behaves qualitatively differently from above it. The paper establishes the asymptotic order of magnitude across all density values, with explicit characterization of the behavior at the critical point. Ford’s 2008 result — the full, unrestricted case — corresponds to δ = 1 (all primes allowed). The restricted problem interpolates between sparse and dense, with a sharp transition separating two regimes.

Phase transitions in combinatorial number theory typically mark the boundary where a qualitative change in the structure of the integers occurs — not in their distribution, but in their multiplicative relationships. At δ = 1/log 4, something about the divisor structure of restricted integers changes character. The critical density is determined by the interaction between the prime restriction and the divisor geometry, not by either alone.