Large Sidon Subsets and Pair-Sum Multiplicities of Distinct Multinomial Coefficients

Abstract

For a positive integer $n$, let ${\mathcal{M}}_n$ be the set of distinct multinomial coefficient values $n!/(p_1!\cdots p_t!)$, where $(p_1,\dots ,p_t)$ ranges over the integer partitions of $n$. We study two complementary aspects of the additive structure of ${\mathcal{M}}_n$: the maximum cardinality $s(n)$ of a Sidon subset and the multiplicities of unordered pair sums in the full set. A product embedding, strongly Sidon subsets, and estimates for prime partitions give \[ \liminf_{n\to\infty}\frac{\log(s(n)/n)\log\log n}{\sqrt{\log n}}\geq\fracπ{\sqrt{3}}. \] Long arithmetic progressions and separated copies yield a complementary lower bound $2/(3\sqrt{3})$ for the normalized Sidon defect. Writing $r_n(t)$ for the number of unordered representations $t=x+y$ with $x,y\in {\mathcal{M}}_n$, we study the collision excess $C(n)$, the number $D(n)$ of multiply represented sums, the maximum multiplicity $\mu (n)$, and the cumulative profile $T(n,k)$. We prove \[ \liminf\frac{C(n)}{n^2\log n}\geq\frac18,\qquad \liminf\frac{D(n)}{n^{3/2}\sqrt{\log n}}\geq\frac{4}{3\sqrt{3}},\qquad \liminf\frac{μ(n)}{\sqrt{n\log n}}\geq\frac12. \] We also obtain a scaled lower envelope for the full profile, an additive-energy bound, stabilization with respect to the number of variables, and an explicit family of trinomial collisions. Exact Sidon values through $n=16$, the lower bound $s(17)\ge 89$, and pair-sum statistics through $n=20$ are reported with reproducible computational material.

arXiv comment24 pages; ancillary computational material. Substantially expanded version incorporating results on pair-sum multiplicities, cumulative representation profiles, additive energy, variable-number stabilization, and trinomial collision families, following the recommendation of the arXiv moderators