Elementary symmetric polynomials and a potentially injective family of maps on partitions

1. Problem Statement

The paper investigates the injectivity properties of a family of maps, denoted as $pre_k$, acting on the set of integer partitions. These maps are derived from the $k$-th elementary symmetric polynomial, $e_k$.

Given a partition $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_\ell)$, the map $pre_k(\lambda)$ produces a new partition whose parts are all possible products of $k$ distinct parts of $\lambda$. Specifically, the multiset of parts of $pre_k(\lambda)$ is:
$$\{ \lambda_{i_1} \lambda_{i_2} \cdots \lambda_{i_k} \mid 1 \le i_1 < i_2 < \dots < i_k \le \ell \}$$
If $\ell < k$, the image is the empty partition.

The central problem addresses two conjectures proposed by Ballantine, Beck, and Merca regarding the injectivity of these maps:

• Conjecture 1.1: $pre_2$ is injective on the set of partitions of $n$ (denoted $P(n)$).
• Conjecture 1.2: For $k \ge 3$, $pre_k$ is injective on the subset of $P(n)$ consisting of partitions with at least $k$ parts.

The authors aim to verify, disprove, or refine these conjectures and explore the structural relationships between different $pre_k$ maps.

2. Methodology

The authors employ a combination of combinatorial construction, algebraic manipulation, and lattice-based analysis:

• Counterexample Construction: To disprove Conjecture 1.2, the authors construct infinite families of distinct partitions that map to the same image under $pre_k$. They utilize parameterized partitions involving primes and specific integer sequences to generate collisions.
• Algebraic Linking: The authors establish a duality between $pre_k$ and $pre_{\ell-k}$ (where $\ell$ is the number of parts in the partition). By analyzing the product of all parts in the image partitions, they derive conditions under which injectivity of one map implies injectivity of its "complementary" map.
• Lattice of Parts Analysis: For the proof of injectivity of $pre_2$ on partitions with 4, 5, and 6 parts, the authors adopt and extend the "lattice of parts" approach. This involves setting up systems of equations based on the equality of products of parts ($\lambda_i \lambda_j = \mu_i \mu_j$) and analyzing the ratios between corresponding parts of two partitions $\lambda$ and $\mu$ assumed to have the same image.
• Divisor Counting: To estimate the size of the image of $pre_2$, the authors analyze the factorization properties of $n+1$ and relate the number of divisors $\tau(n+1)$ to the number of distinct partitions in the image.

3. Key Contributions and Results

A. Disproof of Conjecture 1.2

The authors prove that Conjecture 1.2 is false.

• Theorem 1.3: For any $k \ge 3$, there exist infinitely many integers $n$ such that $pre_k$ is not injective on partitions of $n$ with exactly $k$ parts.
• Construction: They provide an explicit infinite family of pairs of partitions. For example, for $k=3$, the partitions $(6, 6, 1)$ and $(9, 2, 2)$ both map to the partition $(36)$ under $pre_3$. They generalize this to an infinite family $(q(1+m(p-1)), 1+m(q-1), p, 1, \dots)$ and $(p(1+m(q-1)), 1+m(p-1), q, 1, \dots)$ for primes $p > q$.

B. Refinement of the Conjecture

Recognizing that partitions with different numbers of parts naturally map to images with different numbers of parts (since $\binom{\ell}{k}$ is strictly increasing for fixed $k$), the authors propose a modified conjecture:

• Conjecture 1.4: For $k \ge 3$, $pre_k$ is injective on partitions of $n$ with $j$ parts, for each $j \ge k+1$.

C. Inter-relationships between Maps

The authors establish a symmetry in injectivity:

• Theorem 1.5: If $pre_k$ is injective on partitions of $n$ with $\ell$ parts, then $pre_{\ell-k}$ is also injective on the same set.
• Implication: This allows the authors to deduce injectivity for higher $k$ values based on known results for lower $k$ values. For instance, since $pre_2$ is injective on partitions with 5 and 6 parts, it follows that $pre_3$ is injective on 5-part partitions and $pre_4$ is injective on 6-part partitions.

D. Proof of Injectivity for $pre_2$ (Small Partitions)

While Conjecture 1.1 ($pre_2$ injectivity) was recently proven by others using different methods, the authors provide alternative proofs using the lattice approach for specific cases:

• Theorem 1.6: The map $pre_2$ is injective on partitions of $n$ with four, five, and six parts.
• Method: By assuming $pre_2(\lambda) = pre_2(\mu)$, they derive a ratio $k = \lambda_i / \mu_i$ and use the sum constraint ($\sum \lambda_i = \sum \mu_i = n$) to show that $k$ must equal 1, implying $\lambda = \mu$.

E. Lower Bounds for the Image Size

The authors investigate the cardinality of the image of $pre_2$, denoted $pre_2(n)$.

• Theorem 1.7: They derive a lower bound for the number of partitions of $n$ in the image of $pre_2$:
  $$pre_2(n) \ge \begin{cases} \frac{\tau(n+1)}{2} & \text{if } n+1 \text{ is not a perfect square} \\ \frac{\tau(n+1)+1}{2} & \text{if } n+1 \text{ is a perfect square} \end{cases}$$
  where $\tau(m)$ is the number of divisors of $m$. This result is based on the observation that factorizations of $n+1$ correspond to specific partitions in the image.

4. Significance

• Resolution of Open Problems: The paper definitively settles the question of whether $pre_k$ is injective for partitions with exactly $k$ parts (the answer is no for $k \ge 3$), correcting the scope of the original conjectures.
• Structural Insight: By linking $pre_k$ and $pre_{\ell-k}$, the authors shift the perspective from studying maps in isolation to viewing them as a cohesive family, offering a more efficient path to proving injectivity for specific parameters.
• Methodological Advancement: The alternative proofs for $pre_2$ injectivity on 4–6 parts demonstrate the utility of the "lattice of parts" approach, potentially paving the way for extending these proofs to larger numbers of parts (a current open problem).
• Quantitative Analysis: The lower bounds on the image size provide new quantitative data on the density of these maps, suggesting that the image is significantly larger than previously thought for composite $n+1$.

5. Open Problems

The paper concludes by posing three open problems:

1. Finite vs. Infinite Non-injectivity: Are there only finitely many $n$ for which $pre_3$ is injective on 3-part partitions? (Data suggests non-injectivity for all $n > 18$).
2. Extension of Proofs: Can the lattice analysis used for 4–6 parts be extended to partitions with more than six parts?
3. Uniqueness: Does there exist any $n \ge 1$ such that $pre_2(n) = 1$ (i.e., the image contains only one partition)?