Extremal densities for forbidden configurations in $S$-smooth numbers

1. Problem Statement

The paper investigates an extremal combinatorial problem within the set of $S$-smooth numbers.

• Definitions: Let $S = \{p_1, \dots, p_r\}$ be a finite set of distinct primes ($r \ge 2$). The set of $S$-smooth numbers, denoted $M(S)$, consists of all integers of the form $p_1^{a_1} \cdots p_r^{a_r}$ where $a_i \ge 0$.
• The Forbidden Configuration: The problem seeks to find the maximum size of a subset $A \subseteq M(S) \cap [1, X]$ that contains no set of the form $\{n, p_1n, \dots, p_rn\}$. In the exponent space (logarithmic coordinates), this corresponds to avoiding a "unit corner" $\{a, a+e_1, \dots, a+e_r\}$ in a weighted lattice simplex.
• Key Functions:
  • $\Psi_S(X)$: The counting function of $S$-smooth numbers up to $X$.
  • $F_S(X)$: The maximum size of a subset of $M(S) \cap [1, X]$ avoiding the forbidden configuration.
  • $f_S(k)$: The maximum size of a subset of the first $k$ $S$-smooth numbers avoiding the configuration.
  • $G_S(N)$: The analogous problem on the full interval $[1, N]$ (including non-smooth numbers).

2. Methodology

The author employs a combination of combinatorial arguments, analytic number theory, and geometric interpretations.

• Geometric Mapping: The problem is mapped from multiplicative integers to a weighted lattice simplex $\Sigma_S(u) = \{ (a_1, \dots, a_r) \in \mathbb{Z}_{\ge 0}^r : \sum a_i \log p_i \le u \}$. The forbidden configuration $\{n, p_1n, \dots, p_rn\}$ corresponds exactly to a "unit corner" in this lattice.
• Lower Bound (Modular Coloring): A coloring argument is used. The author defines a coloring $\chi: \mathbb{Z}_{\ge 0}^r \to \mathbb{Z}/(r+1)\mathbb{Z}$ via $\chi(a) \equiv \sum i a_i \pmod{r+1}$. Lemma 3.1 proves that every unit corner contains exactly one point of each color. By removing the smallest color class, a valid subset is obtained, yielding a lower bound of $\frac{r}{r+1}$ of the total volume.
• Upper Bound (Shift Identity): An identity involving backward shifts of sets is derived. By analyzing the intersection of a set $A$ with its shifts $A^{(i)}$, the author establishes an exact relation between the size of $A$, the size of the simplex, and boundary terms. This proves the upper bound matches the lower bound asymptotically.
• Decomposition for Full Intervals: To solve the problem on $[1, N]$ (including non-smooth numbers), the author uses a unique decomposition $n = md$ where $d \in M(S)$ and $(m, P_S)=1$. This allows the problem to be split into disjoint components, each isomorphic to an $S$-smooth problem, facilitating the derivation of the density constant $\alpha_S$.
• Recursive Computation: The paper utilizes recursive formulas for the "reciprocal tail" (sum of reciprocals of $S$-smooth numbers greater than $X$) to compute explicit bounds for the density constants.

3. Key Results

A. Asymptotic Formulas for $S$-Smooth Numbers

Theorem 1.1 establishes the asymptotic behavior of the extremal function:
$$F_S(X) = \frac{r}{r+1}\Psi_S(X) + O_S((\log X)^{r-1})$$
Equivalently, for the first $k$ smooth numbers:
$$f_S(k) = \frac{r}{r+1}k + O_S(k^{(r-1)/r})$$
This confirms that the maximum density of a configuration-free set within $S$-smooth numbers is exactly $\frac{r}{r+1}$.

B. Density Constant for the Full Interval

Corollary 1.2 addresses the problem on the full interval $[1, N]$. It proves the existence of a density constant $\alpha_S$ such that:
$$G_S(N) = \alpha_S N + O_S((\log N)^r)$$
The constant is explicitly represented as a convergent series:
$$\alpha_S = c_S \sum_{k \ge 1} \frac{\Delta f_S(k)}{d_k^{(S)}}$$
where $c_S = \prod_{p \in S} (1 - 1/p)$, $d_k^{(S)}$ is the $k$-th $S$-smooth number, and $\Delta f_S(k) \in \{0, 1\}$ indicates whether the $k$-th smooth number can be added to an optimal set.

C. Computable Bounds

Corollary 1.3 provides nested computable bounds $L_{S,N} \le \alpha_S \le U_{S,N}$. The width of these intervals is determined by the reciprocal tail of $S$-smooth numbers, allowing $\alpha_S$ to be computed to arbitrary precision.

D. Rationality and Periodicity

Proposition 1.4 presents a counter-intuitive result regarding rational reciprocal sums. It shows that for $|S| \ge 2$, there exists a binary sequence $(c_k)$ such that $\sum c_k / d_k^{(S)}$ is rational, yet the sequence $(c_k)$ is not eventually periodic. This demonstrates that rationality in this context does not imply periodicity, unlike in standard base-$b$ expansions.

E. The Classical Case $S=\{2, 3\}$

For the specific case of 3-smooth numbers (avoiding $\{n, 2n, 3n\}$), the paper:

• Recovers the Graham–Spencer–Witsenhausen constant $\alpha = \alpha_{\{2,3\}}$.
• Derives an explicit tail formula for the error term.
• Proposition 6.2: Proves that there is no nested optimal family of sets. That is, one cannot construct a sequence of optimal sets $A_1 \subset A_2 \subset \dots$ where $A_k$ is optimal for the first $k$ numbers. The structure of optimal sets changes non-monotonically as $k$ increases.

4. Significance and Contributions

1. Resolution of Asymptotics: The paper settles the asymptotic density of forbidden configurations in multiplicative semigroups, generalizing previous results known for specific small sets of primes.
2. Explicit Constants: It moves beyond existence proofs to provide explicit series representations and recursive algorithms for calculating the density constants $\alpha_S$.
3. Structural Insights: The discovery that optimal sets for $S=\{2,3\}$ do not form a nested family challenges intuitive assumptions about the stability of extremal structures in combinatorial number theory.
4. Number Theoretic Connections: The work bridges extremal combinatorics with the distribution of smooth numbers and the properties of reciprocal sums, revealing deep connections between lattice geometry and multiplicative number theory.
5. Computational Framework: By providing recursive formulas for reciprocal tails, the paper offers a practical method for high-precision numerical computation of these density constants, which was previously difficult.

In summary, Veselinov's work provides a comprehensive framework for understanding the density of sets avoiding multiplicative progressions within smooth numbers, offering both rigorous asymptotic proofs and computable tools for specific cases.