Miller CANT2025 MSTDPhaseTransition

Описание: Phase Transitions for Binomial Sets Under Linear Forms
Steven Miller, Williams College (joint work with Ryan Jeong)
slides: https://web.williams.edu/Mathematics/...
paper: https://arxiv.org/abs/2309.01801
Abstract: We generalize results on sum and difference sets of subsetS of $\mathbb{N}$ drawn from a binomial model. Given $A \subseteq \{0, 1,
\dots, N\}$, an integer $h \geq 2$, and a linear form $L: \mathbb{Z}^h \to \mathbb{Z}$ $$L(x_1, \dots, x_h)\ :=\ u_1x_1 + \cdots + u_hx_h,
\quad u_i \in \mathbb{Z}_{\neq 0} {\rm\ for\ all\ } i \in [h],$$ we study the size of $$L(A)\ =\ \left\{u_1a_1 + \cdots + u_ha_h : a_i \in A
\right\}$$ and its complement $L(A)^c$ when each element of $\{0, 1, \dots, N\}$ is independently included in $A$ with probability $p(N)$,
identifying two phase transitions. The first global one concerns the relative sizes of $L(A)$ and $L(A)^c$, with $p(N) = N^{-\frac{h-1}{h}}$
as the threshold. Asymptotically almost surely, below the threshold almost all sums generated in $L(A)$ are distinct and almost all possible
sums are in $L(A)^c$, and above the threshold almost all possible sums are in $L(A)$. Our asymptotic formulae substantially extends work of
Hegarty and Miller, resolving their conjecture. The second local phase transition concerns the asymptotic behavior of the number of distinct
realizations in $L(A)$ of a given value, with $p(N) = N^{-\frac{h-2}{h-1}}$ as the threshold and identifies (in a sharp sense) when the number
of such realizations obeys a Poisson limit. Our main tools are recent results on the asymptotic enumeration of partitions, Stein's method for
Poisson approximation, and the martingale machinery of Kim-Vu.