Counting Polynomials via Galois Actions on Root Subsets

1. Problem Statement

The paper addresses a central problem in probabilistic Galois theory: estimating the number of monic integer polynomials of a fixed degree $n$ and height at most $H$ whose Galois group, acting on the roots, is isomorphic to a specific prescribed permutation group $(G, \Omega)$.

Let $B_n(H)$ be the set of monic integer polynomials of degree $n$ with height $\le H$. The size of this set is asymptotically $(2H)^n$. The goal is to bound the cardinality of the subset:
$$B(H; G, \Omega) := \{f \in B_{|\Omega|}(H) : (G_f, \Omega_f) \cong (G, \Omega)\}$$
where $G_f$ is the Galois group of the splitting field of $f$, and $\Omega_f$ is the set of roots.

Context:

• Hilbert's Irreducibility Theorem implies that for the symmetric group $S_n$, almost all polynomials have Galois group $S_n$.
• Van der Waerden's Conjecture (proven up to constants by Bhargava) states that the number of polynomials with Galois group not isomorphic to $S_n$ is $O(H^{n-1})$.
• Bhargava's Previous Work: For specific families of groups (e.g., primitive non-elemental groups), Bhargava established bounds of the form $O(H^{c\sqrt{n}(\log n)^2})$.
• The Gap: The existing bounds for specific families of permutation groups (particularly wreath products and $k$-homogeneous groups) were not optimal. This paper aims to provide significantly sharper upper bounds for these families.

2. Methodology

The author employs a strategy that reduces the counting of polynomials with a complex Galois action to the counting of polynomials with simpler Galois actions. The approach consists of three main steps:

A. Construction of Invariant Families (Group Theory)

The core theoretical innovation is the construction of a family of subsets $\Lambda \subset \mathcal{P}(\Omega)$ (the power set of the roots) that satisfies two properties:

1. Stability: $\Lambda$ is closed under the action of $G$ (i.e., if $A \in \Lambda$ and $\sigma \in G$, then $\sigma(A) \in \Lambda$).
2. Faithfulness: The action of $G$ on $\Lambda$ is faithful.
3. Isomorphism: The action $(G, \Lambda)$ is isomorphic to a simpler, known transitive action (e.g., the action of $G$ on $[m]$ or a smaller wreath product).

The paper proves specific lemmas (Section 2) establishing such families for:

• Primitive Wreath Products: Mapping the action on $r$-tuples of $k$-subsets to an action on a product space.
• $k$-Homogeneous Groups: Mapping the action on $k$-subsets to the action on single elements $[m]$.
• $k$-Transitive Groups: Mapping the action on $k$-tuples to the action on single elements.
• Regular Actions: Mapping the regular action to the minimal faithful permutation degree $\mu(G)$.

B. Splitting Field Factorization (Algebraic Number Theory)

Using the family $\Lambda$, the author decomposes the splitting field $K_f$ of a polynomial $f$.

• For each orbit $\Lambda^{(\ell)}$ of $\Lambda$, let $A_\ell$ be a representative subset.
• The fixed field $E_\ell = K_f^{\text{Stab}_G(A_\ell)}$ is generated by the coefficients of the polynomial $\prod_{\alpha \in A_\ell} (x - \alpha)$.
• Key Insight: The height of these coefficients is bounded by a power of the original height $H$. Specifically, if $|A_\ell| = k$, the height of the generator is roughly $H^{k/|\Omega| \cdot |\Lambda^{(\ell)}|}$.
• Consequently, $K_f$ is the compositum of fields $K_{q_\ell}$, where $q_\ell$ are polynomials associated with the simpler actions $(G_\ell, \Lambda^{(\ell)})$.

C. Counting Reduction

The paper utilizes Proposition 3.4, which states that if the splitting field $K_f$ can be generated by a compositum of fields arising from polynomials $q_1, \dots, q_s$ with heights $H_\ell(H)$, then:
$$|B(H; G, \Omega)| \ll H^{1+\epsilon} \prod_{\ell=1}^s |B(H_\ell(H); G_\ell, \Lambda^{(\ell)})|$$
This reduces the problem of bounding $|B(H; G, \Omega)|$ to bounding the number of polynomials for the simpler groups $G_\ell$.

3. Key Contributions and Results

The paper provides new upper bounds for $|B(H; G, \Omega)|$ that are asymptotically sharper than previous results (specifically Bhargava's bounds) for large $H$ and $n$.

Theorem 1.1: Primitive Wreath Product Actions

• Setup: $G \le S_m \wr S_r$ acting on $\Omega_P(m, r, k)$ (primitive non-elemental groups).
• Previous Bound: $O(H^{c\sqrt{n}(\log n)^2})$.
• New Bound:
  $$|B(H; G, \Omega)| \ll H^{r(\binom{m}{k} + r - 1) + 1 + \epsilon}$$
• Significance: For $r > 1$, the exponent is roughly $n^{1/r} \log n$, which is significantly smaller than the previous $\sqrt{n}$ bound when $r$ is large.

Theorem 1.2: $k$-Homogeneous Actions

• Setup: $G \le S_m$ acting transitively on $k$-subsets $\binom{[m]}{k}$.
• Previous Bound: $O(H^{c \binom{m}{k}^{1/2} (\log \binom{m}{k})^2})$.
• New Bound:
  $$|B(H; G, \binom{[m]}{k})| \ll H^{mk + 1 + \epsilon}$$
• Significance: The new bound depends linearly on $m$ (in the exponent base) rather than the square root of the binomial coefficient. For $k \ge 2$, this is a substantial improvement.

Theorem 1.3: $k$-Transitive Actions

• Setup: $G \le S_m$ acting on $k$-tuples of distinct elements $[m]_k$.
• Previous Bound: $O(H^{(m)_k - 1})$ (where $(m)_k$ is the falling factorial).
• New Bound:
  $$|B(H; G, [m]_k)| \ll H^{m + 1 + \epsilon}$$
• Significance: Reduces the exponent from roughly $m^k$ to $m$. This is a dramatic improvement, showing that the number of such polynomials is much smaller than previously thought.

Theorem 1.4: Regular Actions

• Setup: $(G, \Omega)$ is a regular permutation group.
• Previous Bound: $O(H^{\frac{3|G|}{11} + 1.164})$.
• New Bound:
  $$|B(H; G, \Omega)| \ll H^{\mu(G) + 1 + \epsilon}$$
  where $\mu(G)$ is the minimal faithful permutation degree of $G$.
• Significance: Since $\mu(G)$ is often much smaller than $|G|$ (and specifically smaller than $\frac{3|G|}{11}$ for most groups), this provides a tighter bound. For example, for $S_m$ acting regularly on itself (degree $m!$), the bound drops from $O(H^{m!/11})$ to $O(H^{m+1})$.

4. Significance

• Refinement of Probabilistic Galois Theory: The results refine our understanding of the distribution of Galois groups. They demonstrate that for specific "structured" groups (like wreath products or $k$-transitive groups), the probability of a random polynomial having such a group is even lower than previously estimated.
• Methodological Advancement: The technique of reducing complex Galois actions to simpler ones via invariant subsets of roots is a powerful new tool. It bypasses the need for direct counting of fields by leveraging the structure of the permutation representation.
• Optimality: The bounds obtained are close to the trivial bound $H^{\text{degree} + 1}$ for the underlying simpler actions, suggesting that the "cost" of the specific Galois structure is minimized to the degree of the minimal faithful representation.
• Applications: These bounds are crucial for algorithms that rely on the rarity of specific Galois groups and for understanding the arithmetic statistics of number fields.

In summary, Ben-Porath successfully generalizes and sharpens the bounds for counting polynomials with specific Galois groups by introducing a structural reduction method that links the complexity of the Galois action to the minimal faithful permutation degree of the group.